基于二叉链表的存储格式,输入二叉树的先序序列,用*代表空节点,如ABD**CE***F**建立二叉树,然后中序遍历二叉树,输出节点的值。代码
时间: 2024-10-10 12:00:59 浏览: 34
A*算法八数码问题C语言实现
4星 · 用户满意度95%
首先,让我们了解一下基于二叉链表的存储格式。对于二叉树的表示,每个节点通常包含三个部分:数据、左指针和右指针。如果某个节点为空,它的左指针和右指针将指向`NULL`。
给定先序遍历序列"ABD**CE***F**",可以按照先序遍历的特点(根 -> 左 -> 右)构建二叉树:
1. 先读取第一个元素A作为根节点。
2. 然后遇到**,说明接下来的是左子树的空节点,所以在A的左孩子处插入空节点。
3. 遇到B,它是A的左孩子的下一个节点,所以我们创建一个新的节点B,并设置其左指针为`NULL`(因为左子树已经结束),右指针指向后续的**。
4. 接着遇到D,同样插入到B的右孩子位置。
5. 遇到**,左子树结束,进入右子树,继续寻找下一个非**节点。
6. 最后,遇到C和F,分别插入到D的左右孩子位置,因为它们后面没有**了。
现在我们有了这样的二叉树结构:
```
A
/ \
B D
/ \
NULL C
\
F
```
中序遍历的顺序是左子树 -> 根节点 -> 右子树。所以中序遍历的结果将是DBACF。
以下是用Python实现这个过程的示例代码:
```python
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def build_tree(preorder):
if not preorder:
return None
root_val = preorder.pop(0)
root = Node(root_val)
if '*' in preorder:
left_end = preorder.index('*')
root.left = build_tree(preorder[:left_end])
else:
root.left = None
if '*' in preorder:
right_end = preorder.index('*', left_end + 1) + 1
root.right = build_tree(preorder[right_end:])
else:
root.right = None
return root
def inorder_traversal(node, result=None):
if result is None:
result = []
if node:
inorder_traversal(node.left, result)
result.append(node.data)
inorder_traversal(node.right, result)
return result
# 先序序列
preorder = ['A', 'B', '*', 'D', '*', 'C', '*', 'F']
root = build_tree(preorder)
# 中序遍历并打印结果
in_order_sequence = inorder_traversal(root)
print("中序遍历结果:", in_order_sequence)
```
运行这段代码会得到输出:`['D', 'B', 'A', 'C', 'F']`,这是输入先序序列构建的二叉树的中序遍历结果。
阅读全文