建立二叉树,然后实现:输出先序遍历、中序遍历、后序遍历的结果。输入说明第一行:结点个数n。 以下行:每行3个数,第一个是父亲,后两个依次为左右孩子,0表示空。
时间: 2024-12-18 13:22:13 浏览: 14
建立二叉树并实现先序、中序和后续遍历的过程涉及以下几个步骤:
1. **构建二叉树**:
首先,你需要创建一个节点类,每个节点包含值、左子节点和右子节点。对于给定的数据,你可以从输入读取,并按照层次结构组装成树。假设数据是递归的,如 `father left right` 形式,你可以这样构造:
```python
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def build_tree(n, input_list):
# 省略具体的实现细节,这里假设input_list是一个列表,每一项对应一行输入
tree = None
for i in range(n):
father_val, left_val, right_val = input_list[i]
if father_val == 0:
continue
new_node = Node(father_val)
if left_val != 0:
new_node.left = build_tree(1, [left_val])
if right_val != 0:
new_node.right = build_tree(1, [right_val])
return tree
```
2. **遍历方法**:
- **先序遍历(Preorder Traversal)**:根 -> 左 -> 右
- **中序遍历(Inorder Traversal)**:左 -> 根 -> 右
- **后序遍历(Postorder Traversal)**:左 -> 右 -> 根
以下是遍历函数的示例:
```python
def preorder_traversal(node):
if node is not None:
print(node.value, end=' ')
preorder_traversal(node.left)
preorder_traversal(node.right)
def inorder_traversal(node):
if node is not None:
inorder_traversal(node.left)
print(node.value, end=' ')
inorder_traversal(node.right)
def postorder_traversal(node):
if node is not None:
postorder_traversal(node.left)
postorder_traversal(node.right)
print(node.value, end=' ')
# 使用时调用上述函数并传入你的二叉树根节点
tree_root = build_tree(n, ...your_input_data...) # 替换为实际的输入数据
preorder_traversal(tree_root)
print()
inorder_traversal(tree_root)
print()
postorder_traversal(tree_root)
```
阅读全文