用二叉链表表示树,结点的值为结点的序号,创建n个结点的完全二叉树,输出前、中、后三种遍历
时间: 2024-05-01 10:21:55 浏览: 106
好的,针对你的问题,我来为你解答。
下面是用二叉链表表示完全二叉树的代码实现:
```python
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def create_complete_binary_tree(n):
if n <= 0:
return None
nodes = [Node(i) for i in range(1, n+1)]
for i in range(n//2):
nodes[i].left = nodes[2*i+1]
nodes[i].right = nodes[2*i+2]
return nodes[0]
```
上述代码中,我们定义了一个 Node 类,表示二叉树的结点,每个结点包含一个值 value、左子结点 left 和右子结点 right。然后,我们定义了一个函数 create_complete_binary_tree(n),用于创建 n 个结点的完全二叉树。首先,我们创建 n 个结点,并将它们存储在一个列表中。然后,我们按照完全二叉树的性质,为每个结点分配左右子结点。最后,我们返回根节点 nodes[0],即完全二叉树的根结点。
接下来,我们分别使用前序遍历、中序遍历和后序遍历的方式输出这棵二叉树。
```python
def preorder_traversal(root):
if root is None:
return
print(root.value)
preorder_traversal(root.left)
preorder_traversal(root.right)
def inorder_traversal(root):
if root is None:
return
inorder_traversal(root.left)
print(root.value)
inorder_traversal(root.right)
def postorder_traversal(root):
if root is None:
return
postorder_traversal(root.left)
postorder_traversal(root.right)
print(root.value)
root = create_complete_binary_tree(7)
print("前序遍历:")
preorder_traversal(root)
print("中序遍历:")
inorder_traversal(root)
print("后序遍历:")
postorder_traversal(root)
```
输出结果如下:
```
前序遍历:
1
2
4
5
3
6
7
中序遍历:
4
2
5
1
6
3
7
后序遍历:
4
5
2
6
7
3
1
```
因为这是一棵完全二叉树,所以它的前序遍历、中序遍历和后序遍历结果都是唯一的。
阅读全文