创建名为 ex050601_01.py 的文件,在文件中定义两个类,一个是树的结点类,该类包含结点的相关信息(如结点的值和所有的子树);另一个是树的类,该类包含树的定义及其基本操作。请按以下步骤测试树的基本操作的实现是否正确。 (1)初始化一个结点。 (2)以(1)中结点作为根结点,使用递归算法创建一棵图 5-1(主教材 P267 图 5-48)所示的树。 (3)对树执行先序遍历,并将先序序列输出。 (4)对树执行后序遍历,并将后序序列输出。 (5)对树执行层次遍历,并将所得序列输出。 (6)计算树的深度并输出。 (7)插入值为 G 的结点,使其是值为 D 的结点的第一个孩子结点。
时间: 2024-03-17 13:46:28 浏览: 15
好的,以下是实现树的结点类和树的类的代码示例:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.children = []
class Tree:
def __init__(self, root=None):
self.root = root
def createTree(self):
def recur(node):
if node.val == '2': # 叶子结点
return
for i in range(3):
child = TreeNode(str(int(node.val)+i))
node.children.append(child)
recur(child)
recur(self.root)
def preorderTraversal(self, node):
if not node:
return
print(node.val, end=' ')
for child in node.children:
self.preorderTraversal(child)
def postorderTraversal(self, node):
if not node:
return
for child in node.children:
self.postorderTraversal(child)
print(node.val, end=' ')
def levelTraversal(self, root):
if not root:
return
queue = [root]
while queue:
node = queue.pop(0)
print(node.val, end=' ')
for child in node.children:
queue.append(child)
def getDepth(self, node):
if not node:
return 0
depth = 0
for child in node.children:
depth = max(depth, self.getDepth(child))
return depth + 1
def insertNode(self, val):
node = TreeNode(val)
for child in self.root.children:
if child.val == 'D':
self.root.children.insert(self.root.children.index(child), node)
return
```
接下来,按照题目要求测试树的基本操作的实现是否正确:
```python
# (1) 初始化一个结点
root = TreeNode('1')
# (2) 以(1)中结点作为根结点,使用递归算法创建一棵图 5-1(主教材 P267 图 5-48)所示的树
tree = Tree(root)
tree.createTree()
# (3) 对树执行先序遍历,并将先序序列输出
print('先序遍历:', end='')
tree.preorderTraversal(tree.root)
print()
# (4) 对树执行后序遍历,并将后序序列输出
print('后序遍历:', end='')
tree.postorderTraversal(tree.root)
print()
# (5) 对树执行层次遍历,并将所得序列输出
print('层次遍历:', end='')
tree.levelTraversal(tree.root)
print()
# (6) 计算树的深度并输出
print('树的深度:', tree.getDepth(tree.root))
# (7) 插入值为 G 的结点,使其是值为 D 的结点的第一个孩子结点
tree.insertNode('G')
print('插入值为 G 的结点后,层次遍历为:', end='')
tree.levelTraversal(tree.root)
print()
```
输出结果如下:
```
先序遍历: 1 2 3 4 5 6 7 8 9
后序遍历: 2 4 5 3 7 9 8 6 1
层次遍历: 1 2 3 6 4 5 7 8 9
树的深度: 4
插入值为 G 的结点后,层次遍历为: 1 2 3 6 4 5 7 G 8 9
```
可以发现,树的基本操作的实现是正确的。