建立一棵二叉树,并对其进行三种遍历(先序、中序、后序)操作,输出三种遍历结果,同时算法求解此二叉树的高度和叶子数目。 [基本要求] 从键盘接受树结点序列输入(先序序列输入),以二叉链表作为存储结构建立二叉树。
时间: 2024-02-22 10:59:34 浏览: 65
好的,我来为您演示如何实现这个问题。
首先,我们需要定义一个二叉树的节点类,包括节点的值、左子树和右子树。代码如下:
```python
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
```
然后,我们需要根据用户从键盘输入的先序序列建立二叉树。具体来说,我们可以使用递归的方式,对于每个节点,先读入其值,然后分别建立其左子树和右子树。代码如下:
```python
def build_tree():
value = input("请输入节点的值(输入#表示空节点):")
if value == '#':
return None
node = TreeNode(value)
node.left = build_tree()
node.right = build_tree()
return node
```
接着,我们来实现三种遍历操作。先序遍历的代码如下:
```python
def pre_order_traversal(node):
if node:
print(node.value, end=' ')
pre_order_traversal(node.left)
pre_order_traversal(node.right)
```
中序遍历的代码如下:
```python
def in_order_traversal(node):
if node:
in_order_traversal(node.left)
print(node.value, end=' ')
in_order_traversal(node.right)
```
后序遍历的代码如下:
```python
def post_order_traversal(node):
if node:
post_order_traversal(node.left)
post_order_traversal(node.right)
print(node.value, end=' ')
```
最后,我们来求解二叉树的高度和叶子数目。求解高度可以使用递归的方式,代码如下:
```python
def tree_height(node):
if not node:
return 0
left_height = tree_height(node.left)
right_height = tree_height(node.right)
return max(left_height, right_height) + 1
```
求解叶子数目也可以使用递归的方式,代码如下:
```python
def leaf_count(node):
if not node:
return 0
if not node.left and not node.right:
return 1
return leaf_count(node.left) + leaf_count(node.right)
```
现在,我们将所有代码整合在一起,完整的代码如下:
```python
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def build_tree():
value = input("请输入节点的值(输入#表示空节点):")
if value == '#':
return None
node = TreeNode(value)
node.left = build_tree()
node.right = build_tree()
return node
def pre_order_traversal(node):
if node:
print(node.value, end=' ')
pre_order_traversal(node.left)
pre_order_traversal(node.right)
def in_order_traversal(node):
if node:
in_order_traversal(node.left)
print(node.value, end=' ')
in_order_traversal(node.right)
def post_order_traversal(node):
if node:
post_order_traversal(node.left)
post_order_traversal(node.right)
print(node.value, end=' ')
def tree_height(node):
if not node:
return 0
left_height = tree_height(node.left)
right_height = tree_height(node.right)
return max(left_height, right_height) + 1
def leaf_count(node):
if not node:
return 0
if not node.left and not node.right:
return 1
return leaf_count(node.left) + leaf_count(node.right)
if __name__ == '__main__':
root = build_tree()
print("先序遍历:", end='')
pre_order_traversal(root)
print()
print("中序遍历:", end='')
in_order_traversal(root)
print()
print("后序遍历:", end='')
post_order_traversal(root)
print()
print("二叉树高度:", tree_height(root))
print("叶子数目:", leaf_count(root))
```
您可以在运行时输入先序序列,程序将会输出三种遍历结果、二叉树高度和叶子数目。
阅读全文