Python数据结构实验 树的遍历与高度计算
本实验主要探讨树的几种常见存储方式，并实现基于不同存储结构计算树高度的相关算法。通过本实验，可以深入理解树的递归性质以及不同存储结构的特点。
一、实验目标
1. 理解树结构的基本概念和重要性质
2. 掌握树的三种存储方式：孩子链存储、长子兄弟链存储、列表嵌套存储
3. 学会运用递归思想设计树的遍历算法
二、实验环境
操作系统：Windows 10
编程环境：Python 3.8+、PyCharm社区版
三、实验内容
本实验要求针对三种不同的树存储结构，分别设计算法计算树的高度。树的高度定义为从根结点到最深叶子结点的路径上结点的个数。
实验一：孩子链存储结构下求树高
设计思路：采用孩子链存储时，每个结点包含一个指向其所有孩子的指针列表。计算树高采用递归策略：如果结点为空，树高为0；如果结点没有孩子（即叶子结点），树高为1；否则，遍历所有孩子结点，递归计算每个子树的高度，取最大值后加1即为当前结点的高度。
实现代码：
class ChildNode:
"""孩子链存储结构的结点定义"""
def __init__(self, value=None):
self.val = value
self.children = []
def compute_height(node):
"""
计算以node为根的树的高度
递归终止条件：空结点或叶子结点
"""
if node is None:
return 0
if not node.children:
return 1
max_depth = 0
for child in node.children:
child_height = compute_height(child)
if child_height > max_depth:
max_depth = child_height
return max_depth + 1
# 构建测试树并计算高度
if __name__ == '__main__':
# 创建如下结构的树:
# 1
# / | \
# 2 3 4
# /\ /\
# 5 6 7 8
root = ChildNode('A')
node_b = ChildNode('B')
node_c = ChildNode('C')
node_d = ChildNode('D')
node_e = ChildNode('E')
node_f = ChildNode('F')
node_g = ChildNode('G')
node_h = ChildNode('H')
root.children = [node_b, node_c, node_d]
node_b.children = [node_e, node_f]
node_d.children = [node_g, node_h]
result = compute_height(root)
print(f"树的高度为: {result}")
运行结果：3
实验二：长子兄弟链存储结构下求树高
设计思路：长子兄弟链存储使用两个指针：一个指向第一个孩子（长子），另一个指向下一个兄弟结点。计算树高时，从根结点的长子开始，沿着兄弟链依次遍历，对每个结点递归计算其子树高度。在遍历过程中维护一个最大值，最后返回最大值加1。
实现代码：
class FirstChildSiblingNode:
"""长子兄弟链存储结构的结点定义"""
def __init__(self, value=None):
self.val = value
self.first_child = None
self.next_sibling = None
def compute_height(root_node):
"""
长子兄弟链结构下计算树的高度
通过遍历兄弟链表访问所有子树
"""
if root_node is None:
return 0
max_height = 0
current = root_node.first_child
while current is not None:
# 记录下一个兄弟结点位置
sibling_node = current.next_sibling
# 递归计算当前子树的高度
subtree_height = compute_height(current)
if subtree_height > max_height:
max_height = subtree_height
# 移动到下一个兄弟结点
current = sibling_node
return max_height + 1
# 构建测试树并计算高度
if __name__ == '__main__':
# 创建如下结构的树:
# 1
# / | \
# 2 3 4
# /\ /\
# 5 6 7 8
root = FirstChildSiblingNode(1)
node2 = FirstChildSiblingNode(2)
node3 = FirstChildSiblingNode(3)
node4 = FirstChildSiblingNode(4)
node5 = FirstChildSiblingNode(5)
node6 = FirstChildSiblingNode(6)
node7 = FirstChildSiblingNode(7)
node8 = FirstChildSiblingNode(8)
# 设置长子兄弟关系
root.first_child = node2
node2.next_sibling = node3
node3.next_sibling = node4
node2.first_child = node5
node5.next_sibling = node6
node4.first_child = node7
node5.first_child = node8
result = compute_height(root)
print(f"树的高度为: {result}")
运行结果：3
实验三：列表嵌套存储结构下求树高
设计思路：列表嵌套存储将树表示为一个嵌套列表，其中第一个元素代表根结点，后续元素依次为各子树的列表表示。递归实现时，如果当前元素不是列表或列表为空，则认为是叶子结点返回1；否则递归处理所有子树列表，找出最大深度后加1。
实现代码：
def compute_height(tree_repr):
"""
列表存储结构下计算树的高度
列表的第一个元素为根，后续元素为子树列表
"""
# 验证输入有效性
if not isinstance(tree_repr, list) or len(tree_repr) == 0:
return 1
max_depth = 0
# 从索引1开始遍历所有子树
for subtree in tree_repr[1:]:
subtree_height = compute_height(subtree)
if subtree_height > max_depth:
max_depth = subtree_height
return max_depth + 1
# 构建测试树并计算高度
if __name__ == '__main__':
# 树结构示例:
# A
# / | \
# B C D
# /\ /\
# E F G H
test_tree = [
['B', ['E'], ['F']],
['C'],
['D', ['G'], ['H']]
]
result = compute_height(test_tree)
print(f"树的高度为: {result}")
运行结果：3
四、实验总结
本实验通过三种不同的存储结构实现了树高度计算算法。实验表明：
1. 递归是处理树结构问题的天然利器，代码简洁且易于理解
2. 不同存储结构适用于不同应用场景：孩子链直观易懂，长子兄弟链节省空间，列表嵌套适合表达式树等场景
3. 算法核心思想一致：自顶向下递归，自底向上返回结果
