编写一个程序,实现二叉树的下列运算: 输入一个二叉树的先序序列,生成二叉树的二叉链表; 显示其先序、中序和后序遍历结果; 计算二叉树的叶子结点数; 求二叉树的深度 。
时间: 2023-12-01 17:08:21 浏览: 61
好的,我可以为您编写一个Python程序来实现这些操作。下面是代码:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
class BinaryTree:
def __init__(self):
self.root = None
def build_tree(self, preorder):
if not preorder:
return None
root_val = preorder.pop(0)
if root_val == '#':
return None
root = TreeNode(int(root_val))
root.left = self.build_tree(preorder)
root.right = self.build_tree(preorder)
return root
def preorder(self, root):
if not root:
return []
return [root.val] + self.preorder(root.left) + self.preorder(root.right)
def inorder(self, root):
if not root:
return []
return self.inorder(root.left) + [root.val] + self.inorder(root.right)
def postorder(self, root):
if not root:
return []
return self.postorder(root.left) + self.postorder(root.right) + [root.val]
def count_leaves(self, root):
if not root:
return 0
if not root.left and not root.right:
return 1
return self.count_leaves(root.left) + self.count_leaves(root.right)
def depth(self, root):
if not root:
return 0
return max(self.depth(root.left), self.depth(root.right)) + 1
preorder = list(input().strip()) # 输入先序遍历序列
tree = BinaryTree()
tree.root = tree.build_tree(preorder)
print('先序遍历结果:', tree.preorder(tree.root))
print('中序遍历结果:', tree.inorder(tree.root))
print('后序遍历结果:', tree.postorder(tree.root))
print('叶子结点数:', tree.count_leaves(tree.root))
print('二叉树深度:', tree.depth(tree.root))
```
您可以将上述代码保存为一个.py文件,在终端中运行该文件,然后输入二叉树的先序遍历序列,程序将会输出先序、中序、后序遍历结果,叶子结点数和二叉树深度。
阅读全文