编写一个实验程序,假设二叉树采用二叉链存储结构,所有结点值为单个字符。按从上到下的层次输出一棵二叉树中的所有结点,各层的顺序是第1层从左到右,第2层从右到左,第3层从左到右,第4层从右到左,以此类推
时间: 2024-05-01 08:22:41 浏览: 55
数据结构实验报告(顺序存储、链式存储、二叉树,共三份).docx
5星 · 资源好评率100%
以下是采用 Python 语言实现的代码:
```python
class Node:
def __init__(self, val=None, left=None, right=None):
self.val = val
self.left = left
self.right = right
def print_tree(root):
if not root:
return
queue = [root]
left_to_right = True
while queue:
size = len(queue)
level_vals = []
for i in range(size):
node = queue.pop(0)
level_vals.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
if not left_to_right:
level_vals.reverse()
print(level_vals)
left_to_right = not left_to_right
```
代码中,我们定义了一个 `Node` 类来表示二叉树中的结点。每个结点包含一个值 `val`,以及左子树和右子树的引用 `left` 和 `right`。
`print_tree` 函数接受根结点 `root` 作为参数,按照题目要求输出二叉树中的所有结点。我们使用队列来辅助进行层次遍历。在每一层中,我们将结点的值存储在 `level_vals` 列表中,并将该结点的左右子结点加入队列中。如果当前层是从右到左遍历,则将 `level_vals` 列表反转后输出。
下面是一个样例二叉树的构建和输出过程:
```python
root = Node('A')
root.left = Node('B')
root.right = Node('C')
root.left.left = Node('D')
root.left.right = Node('E')
root.right.left = Node('F')
root.right.right = Node('G')
print_tree(root)
```
输出:
```
['A']
['C', 'B']
['D', 'E', 'F', 'G']
```
阅读全文