1、构建一个二叉链表存储结构的二叉树。 2、基于上述构建的二叉树进行先序、中序和后序遍历操作。
时间: 2023-06-14 11:05:51 浏览: 116
编写采用二叉链表形式存储的二叉树的创建、先序、中序、后序和按层遍历的算法
5星 · 资源好评率100%
好的,下面是Python实现:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
class BinaryTree:
def __init__(self):
self.root = None
# 插入节点
def insert(self, val):
new_node = TreeNode(val)
if self.root is None:
self.root = new_node
else:
queue = [self.root]
while queue:
cur_node = queue.pop(0)
if cur_node.left is None:
cur_node.left = new_node
return
elif cur_node.right is None:
cur_node.right = new_node
return
else:
queue.append(cur_node.left)
queue.append(cur_node.right)
# 先序遍历
def preorder(self, node):
if node is not None:
print(node.val, end=' ')
self.preorder(node.left)
self.preorder(node.right)
# 中序遍历
def inorder(self, node):
if node is not None:
self.inorder(node.left)
print(node.val, end=' ')
self.inorder(node.right)
# 后序遍历
def postorder(self, node):
if node is not None:
self.postorder(node.left)
self.postorder(node.right)
print(node.val, end=' ')
```
这里我们使用了队列来插入节点,因为我们需要保证二叉树是一颗完全二叉树。先序、中序和后序遍历分别使用了递归的方式实现,输出结果中间以空格隔开。
下面是一个例子,我们先构建一颗二叉树:
```python
tree = BinaryTree()
tree.insert(1)
tree.insert(2)
tree.insert(3)
tree.insert(4)
tree.insert(5)
```
然后对其进行先序、中序和后序遍历:
```python
print('Preorder:')
tree.preorder(tree.root)
print('\nInorder:')
tree.inorder(tree.root)
print('\nPostorder:')
tree.postorder(tree.root)
```
输出结果为:
```
Preorder:
1 2 4 5 3
Inorder:
4 2 5 1 3
Postorder:
4 5 2 3 1
```
阅读全文