[问题描述] 建立一棵二叉树,并对其进行三种遍历(先序、中序、后序)操作,输出三种遍历结果,同时算法求解此二叉树的高度和叶子数目。 [基本要求] 从键盘接受树结点序列输入(先序序列输入),以二叉链表作为存储结构建立二叉树。 [测试数据] ABC##DE#G##F###(测试数据是先序序列输入树结点,“#”代表空结点,测试树如下图)建立一棵二叉树,并对其进行三种遍历(先序、中序、后序)操作,输出三种遍历结果,同时算法求解此二叉树的高度和叶子数目。 [基本要求] 从键盘接受树结点序列输入(先序序列输入),以二叉链表作为存储结构建立二叉树。 [测试结果] 先序遍历序列:ABCDEGF 中序遍历序列:CBEGDFA 后序遍历序列:CGEFDBA 二叉树高度为5 叶子数目为3
时间: 2024-02-25 16:58:47 浏览: 133
好的,根据你的要求,以下是 Python 代码实现:
```python
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def build_tree(preorder):
if not preorder:
return None
val = preorder.pop(0)
if val == '#':
return None
root = Node(val)
root.left = build_tree(preorder)
root.right = build_tree(preorder)
return root
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]
def get_height(root):
if not root:
return 0
return max(get_height(root.left), get_height(root.right)) + 1
def get_leaf_count(root):
if not root:
return 0
if not root.left and not root.right:
return 1
return get_leaf_count(root.left) + get_leaf_count(root.right)
if __name__ == '__main__':
preorder = list(input().strip())
root = build_tree(preorder)
print('先序遍历序列:{}'.format(''.join(preorder_traversal(root))))
print('中序遍历序列:{}'.format(''.join(inorder_traversal(root))))
print('后序遍历序列:{}'.format(''.join(postorder_traversal(root))))
print('二叉树高度为{}'.format(get_height(root)))
print('叶子数目为{}'.format(get_leaf_count(root)))
```
输入测试数据 `ABC##DE#G##F###` 后,程序输出:
```
先序遍历序列:ABCDEGF
中序遍历序列:CBEGDFA
后序遍历序列:CGEFDBA
二叉树高度为5
叶子数目为3
```
其中,`build_tree()` 函数用于建立二叉树,`preorder_traversal()`、`inorder_traversal()` 和 `postorder_traversal()` 分别用于进行先序、中序和后序遍历,`get_height()` 函数用于求二叉树的高度,`get_leaf_count()` 函数用于求二叉树的叶子数目。
阅读全文