本关任务:以先序的方式建立二叉树后,补充代码,统计该二叉树的节点数,叶子数,满节点数,计算数的高度。
时间: 2024-12-06 22:25:32 浏览: 16
在编程中,给定一个先序遍历序列(通常是根节点 -> 左子树 -> 右子树的形式),你可以通过递归的方式来构建二叉树并同时统计节点数、叶子数(无孩子的节点)、满节点数(所有左右子节点都已填充满的节点)以及树的高度。这里是一个简单的Python示例:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def build_tree(preorder):
if not preorder:
return None
# 根据先序遍历的第一个元素作为根
root_val = preorder[0]
root = TreeNode(root_val)
# 从第二个元素开始找到左子树的结束位置
index = 1
while preorder[index] != root_val:
index += 1
# 构建左子树和右子树
root.left = build_tree(preorder[1:index])
root.right = build_tree(preorder[index+1:])
return root
def count_nodes(root):
if root is None:
return 0
else:
return 1 + count_nodes(root.left) + count_nodes(root.right)
def count_leaves(root):
if root is None or (root.left is None and root.right is None):
return 1
else:
return count_leaves(root.left) + count_leaves(root.right)
def is_full_node(root):
if root is None:
return True
elif (root.left is None and root.right is None) or \
(root.left is not None and root.right is not None and count_leaves(root.left) == 0 and count_leaves(root.right) == 0):
return True
else:
return False
def tree_height(root):
if root is None:
return 0
else:
left_height = tree_height(root.left)
right_height = tree_height(root.right)
return max(left_height, right_height) + 1
# 使用示例
preorder = [1, 2, 3, 4, 5, 6, 7] # 假设这是你的先序遍历序列
root = build_tree(preorder)
node_count = count_nodes(root)
leaf_count = count_leaves(root)
full_node_count = sum(is_full_node(node) for node in preorder if node is not None)
height = tree_height(root)
print("节点数:", node_count)
print("叶子数:", leaf_count)
print("满节点数:", full_node_count)
print("高度:", height)
```
在这个例子中,你需要提供一个有效的先序遍历序列。然后,函数会依次创建二叉树,并计算相关的统计数据。
阅读全文