在给出的程序框架里填写4个二叉树遍历应用算法函数,包括输出二叉树中度为2的结点值,求二叉树的高度,求二叉树中结点个数,求二叉树中叶子结点个数。 (后两个使用全局变量n和n0分 别进行统计个数)
时间: 2024-01-23 11:48:45 浏览: 70
二叉树遍历和获取树高和结点数
```python
class Node:
def __init__(self, value=None, left=None, right=None):
self.value = value
self.left = left
self.right = right
class BinaryTree:
def __init__(self, root=None):
self.root = root
# 输出二叉树中度为2的结点值
def print_full_node(self):
def dfs(node):
if not node:
return
if node.left and node.right:
print(node.value)
dfs(node.left)
dfs(node.right)
dfs(self.root)
# 求二叉树的高度
def get_height(self):
def dfs(node):
if not node:
return 0
left_height = dfs(node.left)
right_height = dfs(node.right)
return 1 + max(left_height, right_height)
return dfs(self.root)
# 求二叉树中结点个数
def get_node_count(self):
def dfs(node):
if not node:
return 0
return 1 + dfs(node.left) + dfs(node.right)
return dfs(self.root)
# 求二叉树中叶子结点个数(使用全局变量n0)
def get_leaf_count(self):
global n0
n0 = 0
def dfs(node):
global n0
if not node:
return
if not node.left and not node.right:
n0 += 1
dfs(node.left)
dfs(node.right)
dfs(self.root)
return n0
if __name__ == '__main__':
# 构造一棵二叉树
n1 = Node('A')
n2 = Node('B')
n3 = Node('C')
n4 = Node('D')
n5 = Node('E')
n6 = Node('F')
n7 = Node('G')
n8 = Node('H')
n1.left, n1.right = n2, n3
n2.left, n2.right = n4, n5
n3.left, n3.right = n6, n7
n5.left = n8
tree = BinaryTree(n1)
# 输出二叉树中度为2的结点值
tree.print_full_node()
# 求二叉树的高度
print(tree.get_height())
# 求二叉树中结点个数
print(tree.get_node_count())
# 求二叉树中叶子结点个数
print(tree.get_leaf_count())
```
阅读全文