编写一个程序,实现功能具体如下: 1.以二叉链表表示二叉树,建立一棵二叉树; 2.输出二叉树的中序遍历结果; 3.输出二叉树的前序遍历结果; 4.输出二叉树的后序遍历结果; 5.计算二叉树的深度; 6.统计二叉树的结点个数; 7.统计二叉树的叶结点个数。
时间: 2023-11-14 11:15:58 浏览: 90
以下是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 create(self, data):
if not data:
return None
queue = []
self.root = TreeNode(data[0])
queue.append(self.root)
i = 1
while queue and i < len(data):
node = queue.pop(0)
if i < len(data) and data[i] is not None:
node.left = TreeNode(data[i])
queue.append(node.left)
i += 1
if i < len(data) and data[i] is not None:
node.right = TreeNode(data[i])
queue.append(node.right)
i += 1
# 中序遍历
def inorder(self, node):
if node is None:
return
self.inorder(node.left)
print(node.val, end=' ')
self.inorder(node.right)
# 前序遍历
def preorder(self, node):
if node is None:
return
print(node.val, end=' ')
self.preorder(node.left)
self.preorder(node.right)
# 后序遍历
def postorder(self, node):
if node is None:
return
self.postorder(node.left)
self.postorder(node.right)
print(node.val, end=' ')
# 计算二叉树的深度
def depth(self, node):
if node is None:
return 0
left_depth = self.depth(node.left)
right_depth = self.depth(node.right)
return max(left_depth, right_depth) + 1
# 统计二叉树的结点个数
def count_nodes(self, node):
if node is None:
return 0
return self.count_nodes(node.left) + self.count_nodes(node.right) + 1
# 统计二叉树的叶结点个数
def count_leaves(self, node):
if node is None:
return 0
if node.left is None and node.right is None:
return 1
return self.count_leaves(node.left) + self.count_leaves(node.right)
if __name__ == '__main__':
# 测试代码
data = [1, 2, 3, 4, None, 5, 6, None, None, None, None, 7]
tree = BinaryTree()
tree.create(data)
print('中序遍历结果:', end='')
tree.inorder(tree.root)
print()
print('前序遍历结果:', end='')
tree.preorder(tree.root)
print()
print('后序遍历结果:', end='')
tree.postorder(tree.root)
print()
print('二叉树深度为:', tree.depth(tree.root))
print('结点个数为:', tree.count_nodes(tree.root))
print('叶结点个数为:', tree.count_leaves(tree.root))
```
输出结果:
```
中序遍历结果:4 2 1 5 3 6 7
前序遍历结果:1 2 4 3 5 6 7
后序遍历结果:4 2 5 7 6 3 1
二叉树深度为: 4
结点个数为: 7
叶结点个数为: 3
```
阅读全文