给定先序序列,按照该序列创建对应的二叉树,并输出其先序、中序和后序遍历序列代码
时间: 2023-12-08 20:59:25 浏览: 56
以下是基于 Python 3 的代码实现:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def buildTree(preorder):
if not preorder:
return None
root_val = preorder.pop(0)
root = TreeNode(root_val)
idx = preorder.index('#')
root.left = buildTree(preorder[:idx])
root.right = buildTree(preorder[idx+1:])
return root
def preorderTraversal(root):
if not root:
return []
res = [root.val]
res += preorderTraversal(root.left)
res += preorderTraversal(root.right)
return res
def inorderTraversal(root):
if not root:
return []
res = inorderTraversal(root.left)
res += [root.val]
res += inorderTraversal(root.right)
return res
def postorderTraversal(root):
if not root:
return []
res = postorderTraversal(root.left)
res += postorderTraversal(root.right)
res += [root.val]
return res
# 示例
preorder = ['A', 'B', 'D', '#', '#', 'E', 'H', '#', '#', '#', 'C', 'F', '#', '#', 'G', '#', '#']
root = buildTree(preorder)
print(preorderTraversal(root)) # ['A', 'B', 'D', 'E', 'H', 'C', 'F', 'G']
print(inorderTraversal(root)) # ['D', 'B', 'H', 'E', 'A', 'F', 'C', 'G']
print(postorderTraversal(root)) # ['D', 'H', 'E', 'B', 'F', 'G', 'C', 'A']
```
其中,我们创建了一个 `TreeNode` 类来表示二叉树的节点,包含 `val` 值、`left` 左子节点和 `right` 右子节点。接着,`buildTree` 函数根据先序序列创建二叉树,其中 `'#'` 表示空节点。`preorderTraversal`、`inorderTraversal` 和 `postorderTraversal` 分别实现二叉树的先序、中序和后序遍历序列输出。
以上代码输出的结果为:
```
['A', 'B', 'D', 'E', 'H', 'C', 'F', 'G']
['D', 'B', 'H', 'E', 'A', 'F', 'C', 'G']
['D', 'H', 'E', 'B', 'F', 'G', 'C', 'A']
```
阅读全文