本关任务:实现二叉树的创建函数及二叉树的遍历函数。
时间: 2024-10-27 18:03:01 浏览: 9
在计算机科学中,二叉树是一种常见的数据结构,每个节点最多有两个子节点,通常称为左子节点和右子节点。实现二叉树主要包括两个关键部分:二叉树节点的定义和创建函数,以及三种基本的遍历方法,分别是前序遍历、中序遍历和后序遍历。
首先,我们定义一个简单的二叉树节点结构体:
```python
class TreeNode:
def __init__(self, value=0, left=None, right=None):
self.value = value
self.left = left
self.right = right
```
接下来,我们需要编写创建函数`build_binary_tree`,通过给定的值列表构建一棵二叉树:
```python
def build_binary_tree(values):
if not values:
return None
root_value = values[0]
root = TreeNode(root_value)
stack = [root]
for val in values[1:]:
node = stack.pop()
if val < root_value:
node.left = TreeNode(val)
stack.append(node.left)
else:
node.right = TreeNode(val)
stack.append(node.right)
return root
```
对于遍历,这里分别给出前序遍历(根-右)、中序遍历(左-根-右)和后序遍历(左-右-根)的实现:
```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=" -> ")
```
阅读全文