创建名为shixun2_1.py的文件,在文件中定义两个类,一个是二叉树的结点类,该类包含结点的相关信息(如结点的值和左、右子树);另一个是二叉树的类,该类包含二叉树的定义及其深度优先遍历操作的递归算法。请通过以下步骤测试二叉树深度优先遍历递归算法的实现是否正确。 ⑴初始化一个结点。 ⑵以⑴中结点作为根结点并使用链式存储结构,递归创建一棵如图所示的二叉树。 此处二叉树请同学们自已定义,替换此树 ⑶对二叉树执行先序遍历递归算法,并将先序序列输出。 ⑷对二叉树执行中序遍历递归算法,并将中序序列输出。 ⑸对二叉树执行后序遍历递归算法,并将后序序列输出。
时间: 2023-12-03 15:43:21 浏览: 29
以下是shixun2_1.py文件的代码实现:
```python
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
class BinaryTree:
def __init__(self, root):
self.root = Node(root)
def preorder_traversal(self, start, traversal):
if start:
traversal += (str(start.val) + " ")
traversal = self.preorder_traversal(start.left, traversal)
traversal = self.preorder_traversal(start.right, traversal)
return traversal
def inorder_traversal(self, start, traversal):
if start:
traversal = self.inorder_traversal(start.left, traversal)
traversal += (str(start.val) + " ")
traversal = self.inorder_traversal(start.right, traversal)
return traversal
def postorder_traversal(self, start, traversal):
if start:
traversal = self.postorder_traversal(start.left, traversal)
traversal = self.postorder_traversal(start.right, traversal)
traversal += (str(start.val) + " ")
return traversal
# 创建一棵二叉树
tree = BinaryTree(1)
tree.root.left = Node(2)
tree.root.right = Node(3)
tree.root.left.left = Node(4)
tree.root.left.right = Node(5)
tree.root.right.left = Node(6)
tree.root.right.right = Node(7)
# 执行先序遍历并输出结果
print("先序遍历结果:", tree.preorder_traversal(tree.root, ""))
# 执行中序遍历并输出结果
print("中序遍历结果:", tree.inorder_traversal(tree.root, ""))
# 执行后序遍历并输出结果
print("后序遍历结果:", tree.postorder_traversal(tree.root, ""))
```
运行结果如下:
```
先序遍历结果: 1 2 4 5 3 6 7
中序遍历结果: 4 2 5 1 6 3 7
后序遍历结果: 4 5 2 6 7 3 1
```