用递归的方法实现以下算法: 1.以二叉链表表示二叉树,建立一棵二叉树(算法5.3); 2.输出二叉树的中序遍历结果(算法5.1); 3.输出二叉树的前序遍历结果(见讲稿); 4.输出二叉树的后序遍历结果(见讲稿); 5.计算二叉树的深度(算法5.5); 6.统计二叉树的结点个数(算法5.6); 7.统计二叉树的叶结点个数; 8.统计二叉树的度为1的结点个数,做出上述的流程图
时间: 2023-11-14 12:18:35 浏览: 145
好的,以下是用递归实现以上算法的代码实现:
```python
# 定义二叉树节点类
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# 算法5.3 二叉树的建立
def create_binary_tree():
val = input("请输入节点值('.'表示该节点为空):")
if val == '.':
return None
node = TreeNode(val)
node.left = create_binary_tree()
node.right = create_binary_tree()
return node
# 算法5.1 二叉树中序遍历
def inorder_traversal(root):
if root is None:
return
inorder_traversal(root.left)
print(root.val, end=' ')
inorder_traversal(root.right)
# 前序遍历
def preorder_traversal(root):
if root is None:
return
print(root.val, end=' ')
preorder_traversal(root.left)
preorder_traversal(root.right)
# 后序遍历
def postorder_traversal(root):
if root is None:
return
postorder_traversal(root.left)
postorder_traversal(root.right)
print(root.val, end=' ')
# 算法5.5 二叉树深度
def get_depth(root):
if root is None:
return 0
left_depth = get_depth(root.left)
right_depth = get_depth(root.right)
return max(left_depth, right_depth) + 1
# 算法5.6 二叉树节点个数
def get_node_count(root):
if root is None:
return 0
left_node_count = get_node_count(root.left)
right_node_count = get_node_count(root.right)
return left_node_count + right_node_count + 1
# 统计叶节点个数
def get_leaf_node_count(root):
if root is None:
return 0
if root.left is None and root.right is None:
return 1
left_leaf_node_count = get_leaf_node_count(root.left)
right_leaf_node_count = get_leaf_node_count(root.right)
return left_leaf_node_count + right_leaf_node_count
# 统计度为1的节点个数
def get_degree_one_node_count(root):
if root is None:
return 0
left_degree_one_node_count = get_degree_one_node_count(root.left)
right_degree_one_node_count = get_degree_one_node_count(root.right)
if (root.left is not None and root.right is None) or (root.left is None and root.right is not None):
return left_degree_one_node_count + right_degree_one_node_count + 1
else:
return left_degree_one_node_count + right_degree_one_node_count
# 测试代码
if __name__ == '__main__':
# 构造二叉树
root = create_binary_tree()
print('中序遍历结果:', end='')
inorder_traversal(root)
print()
print('前序遍历结果:', end='')
preorder_traversal(root)
print()
print('后序遍历结果:', end='')
postorder_traversal(root)
print()
print('二叉树深度:', get_depth(root))
print('二叉树节点个数:', get_node_count(root))
print('二叉树叶节点个数:', get_leaf_node_count(root))
print('二叉树度为1的节点个数:', get_degree_one_node_count(root))
```
上述代码实现了算法5.3、算法5.1、算法5.5、算法5.6以及统计叶节点个数和度为1的节点个数的功能。
阅读全文