建立一棵二叉树。对此树进行前序遍历、中序遍历及后序遍历,输出遍历序列。
时间: 2023-04-27 20:04:50 浏览: 134
建二叉树并分别用先先序、中序和后序遍历,然后输出各遍历序列
5星 · 资源好评率100%
好的,我来回复您的问题。
建立一棵二叉树,需要先确定根节点,然后递归地构建左右子树。假设我们要建立如下的二叉树:
```
A
/ \
B C
/ \ \
D E F
```
其中,A为根节点,B和C为A的左右子节点,D和E为B的左右子节点,F为C的右子节点。
我们可以用如下的代码来表示这棵二叉树:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
# 构建二叉树
root = TreeNode('A')
root.left = TreeNode('B')
root.right = TreeNode('C')
root.left.left = TreeNode('D')
root.left.right = TreeNode('E')
root.right.right = TreeNode('F')
```
接下来,我们可以分别对这棵二叉树进行前序遍历、中序遍历和后序遍历。
前序遍历的顺序是:根节点 -> 左子树 -> 右子树。对于上面的二叉树,前序遍历的结果应该是:A -> B -> D -> E -> C -> F。我们可以用如下的代码来实现前序遍历:
```python
def preorder_traversal(root):
if root is None:
return []
res = [root.val]
res += preorder_traversal(root.left)
res += preorder_traversal(root.right)
return res
preorder = preorder_traversal(root)
print(preorder) # ['A', 'B', 'D', 'E', 'C', 'F']
```
中序遍历的顺序是:左子树 -> 根节点 -> 右子树。对于上面的二叉树,中序遍历的结果应该是:D -> B -> E -> A -> C -> F。我们可以用如下的代码来实现中序遍历:
```python
def inorder_traversal(root):
if root is None:
return []
res = inorder_traversal(root.left)
res += [root.val]
res += inorder_traversal(root.right)
return res
inorder = inorder_traversal(root)
print(inorder) # ['D', 'B', 'E', 'A', 'C', 'F']
```
后序遍历的顺序是:左子树 -> 右子树 -> 根节点。对于上面的二叉树,后序遍历的结果应该是:D -> E -> B -> F -> C -> A。我们可以用如下的代码来实现后序遍历:
```python
def postorder_traversal(root):
if root is None:
return []
res = postorder_traversal(root.left)
res += postorder_traversal(root.right)
res += [root.val]
return res
postorder = postorder_traversal(root)
print(postorder) # ['D', 'E', 'B', 'F', 'C', 'A']
```
希望我的回答能够帮助到您。如果您还有其他问题,可以随时问我哦。
阅读全文