树的先根遍历的递归和迭代算法
时间: 2024-12-22 22:05:05 浏览: 2
树的先序遍历(也称为先根遍历),即访问根节点,然后遍历左子树,最后遍历右子树,可以用递归和迭代两种方式进行。
**递归算法**:
```python
def preorder_recursive(root):
if root is not None:
print(root.val) # 访问根节点
preorder_recursive(root.left) # 遍历左子树
preorder_recursive(root.right) # 遍历右子树
```
在这个递归过程中,我们首先检查根节点是否为空,如果不为空,就打印根节点值,接着递归地对左右子树进行同样的操作。
**迭代算法**:
```python
def preorder_iterative(root):
stack, output = [root], []
while stack:
root = stack.pop()
if root:
output.append(root.val)
stack.extend([root.right, root.left]) # 先右后左
else:
root = stack.pop() # 当前节点已空,回溯到上一个节点
return output
```
这里使用了一个栈来模拟递归过程。首先将根节点入栈,然后在一个循环中,不断从栈顶取出节点并访问,将其子节点按照先右后左的顺序压入栈。当某个节点的左、右子节点都访问完毕,表示当前路径结束,再返回去访问其父节点的下一个子节点。
阅读全文