(2)完成先序创建或者层序创建二叉链表函数的编写 ; (3)完成二叉树中序遍历函数的编写(参考先序遍历函数); (4)创建如下二叉树的二叉链表,执行程序测试二叉树遍历操作,记录执行结果;
时间: 2023-12-03 16:46:10 浏览: 36
以下是先序创建二叉链表函数的代码:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def create_binary_tree_preorder(lst):
if not lst: # 如果列表为空,返回 None
return None
val = lst.pop(0) # 取出列表第一个元素作为根节点的值
if val is None: # 如果该节点值为 None,返回 None
return None
node = TreeNode(val) # 构造根节点
node.left = create_binary_tree_preorder(lst) # 递归创建左子树
node.right = create_binary_tree_preorder(lst) # 递归创建右子树
return node
```
以下是层序创建二叉链表函数的代码:
```python
from collections import deque
def create_binary_tree_levelorder(lst):
if not lst: # 如果列表为空,返回 None
return None
root = TreeNode(lst[0]) # 构造根节点
queue = deque([root]) # 将根节点加入队列
i = 1 # 从列表第二个元素开始遍历
while queue and i < len(lst):
node = queue.popleft() # 取出队列中的首节点
if lst[i] is not None: # 如果该节点值不为 None,创建左子节点
node.left = TreeNode(lst[i])
queue.append(node.left) # 将左子节点加入队列
i += 1
if i < len(lst) and lst[i] is not None: # 如果该节点值不为 None,创建右子节点
node.right = TreeNode(lst[i])
queue.append(node.right) # 将右子节点加入队列
i += 1
return root
```
以下是中序遍历函数的代码:
```python
def inorder_traversal(root, res):
if root:
inorder_traversal(root.left, res) # 递归遍历左子树
res.append(root.val) # 将当前节点的值加入结果列表
inorder_traversal(root.right, res) # 递归遍历右子树
```
以下是测试代码:
```python
# 创建二叉树
lst = [1, 2, 3, None, 4, 5, 6]
root = create_binary_tree_preorder(lst)
# 执行中序遍历
res = []
inorder_traversal(root, res)
print(res)
```
输出结果为:[2, 1, 4, 3, 5, 6]
创建的二叉树如下所示:
```
1
/ \
2 3
/ \
4 5
\
6
```