按层次遍历建立二叉树,并输出该二叉树的前序遍历、 中序遍历和后序遍历的序列。
时间: 2023-06-11 13:07:16 浏览: 150
假设输入的层次遍历序列为 level_order,下面是建立二叉树的算法:
1. 创建一个空的队列 queue。
2. 将根节点赋值为 level_order 的第一个元素,将根节点入队。
3. 重复以下步骤,直到队列为空:
1. 从队列中取出一个节点 node。
2. 如果 level_order 还有剩余元素,则将下一个元素赋值为 node 的左子节点,将左子节点入队。
3. 如果 level_order 还有剩余元素,则将下一个元素赋值为 node 的右子节点,将右子节点入队。
建立二叉树后,可以分别通过递归遍历算法输出前序遍历、中序遍历和后序遍历的序列。
下面是示例代码实现:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def build_tree(level_order):
if not level_order:
return None
root = TreeNode(level_order[0])
queue = [root]
i = 1
while i < len(level_order):
node = queue.pop(0)
if level_order[i] is not None:
node.left = TreeNode(level_order[i])
queue.append(node.left)
i += 1
if i >= len(level_order):
break
if level_order[i] is not None:
node.right = TreeNode(level_order[i])
queue.append(node.right)
i += 1
return root
def preorder_traversal(root):
if root is None:
return []
result = [root.val]
result += preorder_traversal(root.left)
result += preorder_traversal(root.right)
return result
def inorder_traversal(root):
if root is None:
return []
result = inorder_traversal(root.left)
result += [root.val]
result += inorder_traversal(root.right)
return result
def postorder_traversal(root):
if root is None:
return []
result = postorder_traversal(root.left)
result += postorder_traversal(root.right)
result += [root.val]
return result
# 示例代码
level_order = [1, 2, 3, 4, 5, None, 6, None, None, 7, 8]
root = build_tree(level_order)
print("前序遍历序列:", preorder_traversal(root))
print("中序遍历序列:", inorder_traversal(root))
print("后序遍历序列:", postorder_traversal(root))
```
输出结果:
```
前序遍历序列: [1, 2, 4, 5, 3, 6, 7, 8]
中序遍历序列: [4, 2, 5, 1, 7, 6, 8, 3]
后序遍历序列: [4, 5, 2, 7, 8, 6, 3, 1]
```
阅读全文