1) 建立一棵含有n个节点的二叉树,采用二叉链表存储; 2) 输出前序、中序、后续遍历该二叉树的遍历结果。请写出代码
时间: 2024-10-19 12:10:58 浏览: 20
建立一棵包含 n 个节点的二叉链表存储的二叉树,并提供前序、中序和后序遍历的代码如下:
首先,我们需要创建一个二叉树节点的结构体:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
```
接下来,我们创建一个函数用于构建满二叉树(从前往后逐层插入,每层节点数等于下一层两倍减一),这里仅做示例,实际可以根据需求调整:
```python
def build_full_binary_tree(n):
if n <= 0:
return None
root = TreeNode(1)
queue = [root]
level = 2
while len(queue) > 0:
current_level_size = level
next_level_size = level * 2 - 1
# 构建当前级节点
for _ in range(current_level_size):
node = queue.pop(0)
if len(queue) < next_level_size:
node.left = TreeNode()
node.right = TreeNode()
queue.append(node.left)
queue.append(node.right)
level += 1
return root
```
然后,我们可以实现前序、中序和后序遍历:
- 前序遍历(根-左-右):
```python
def preorder_traversal(root):
if root is not None:
print(root.val, end=" ")
preorder_traversal(root.left)
preorder_traversal(root.right)
# 使用时调用
preorder_traversal(build_full_binary_tree(n))
```
- 中序遍历(左-根-右):
```python
def inorder_traversal(root):
if root is not None:
inorder_traversal(root.left)
print(root.val, end=" ")
inorder_traversal(root.right)
# 使用时调用
inorder_traversal(build_full_binary_tree(n))
```
- 后序遍历(左-右-根):
```python
def postorder_traversal(root):
if root is not None:
postorder_traversal(root.left)
postorder_traversal(root.right)
print(root.val, end=" ")
# 使用时调用
postorder_traversal(build_full_binary_tree(n))
```
阅读全文