假设二叉树的结点值是字符,根据输入的一棵二叉树的扩展先序遍历序列建立一棵以二叉链表表示的二叉树。对二叉树进行先序、中序和后序遍历操作,并输出遍历序列,观察输出的序列是否与逻辑上的序列一致。
时间: 2024-05-07 18:19:57 浏览: 109
二叉树_17281183_刘梦婷_splitns2_扩展先序序列_二叉树_
好的,我可以帮你实现这个功能。首先,我们可以通过扩展先序遍历序列建立二叉树,具体方法如下:
1. 读入当前结点的值。
2. 若当前结点的值为“#”,则返回空指针。
3. 若当前结点的值不为“#”,则新建一个结点,并将当前值存入该结点中。
4. 递归构建当前结点的左子树。
5. 递归构建当前结点的右子树。
6. 返回当前结点。
代码实现如下:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def build_tree(preorder):
if not preorder:
return None
val = preorder.pop(0)
if val == '#':
return None
node = TreeNode(int(val))
node.left = build_tree(preorder)
node.right = build_tree(preorder)
return node
```
接下来,我们可以分别实现二叉树的先序、中序和后序遍历,具体方法如下:
1. 先序遍历:先输出当前结点的值,再递归遍历左子树和右子树。
2. 中序遍历:先递归遍历左子树,再输出当前结点的值,最后递归遍历右子树。
3. 后序遍历:先递归遍历左子树和右子树,最后输出当前结点的值。
代码实现如下:
```python
def preorder_traversal(root):
if not root:
return []
return [root.val] + preorder_traversal(root.left) + preorder_traversal(root.right)
def inorder_traversal(root):
if not root:
return []
return inorder_traversal(root.left) + [root.val] + inorder_traversal(root.right)
def postorder_traversal(root):
if not root:
return []
return postorder_traversal(root.left) + postorder_traversal(root.right) + [root.val]
```
最后,我们可以使用以下代码来测试:
```python
preorder = ['1', '2', '#', '#', '3', '#', '#']
root = build_tree(preorder)
print(preorder_traversal(root))
print(inorder_traversal(root))
print(postorder_traversal(root))
```
输出结果为:
```
[1, 2, 3]
[2, 1, 3]
[2, 3, 1]
```
我们可以发现,输出的先序、中序和后序遍历序列与逻辑上的序列一致,说明代码实现正确。
阅读全文