先序遍历二叉树的非递归算法
时间: 2023-09-17 07:07:58 浏览: 86
先序遍历二叉树的非递归算法可以使用栈来实现。具体步骤如下:
1. 新建一个栈,将根节点入栈。
2. 当栈不为空时,执行以下操作:
a. 弹出栈顶元素,访问该节点。
b. 如果该节点的右子树不为空,将右子树入栈。
c. 如果该节点的左子树不为空,将左子树入栈。
3. 重复步骤2,直到栈为空。
代码实现如下:
```python
def preorderTraversal(root):
if not root:
return []
stack = [root]
res = []
while stack:
node = stack.pop()
res.append(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return res
```
其中,root表示二叉树的根节点,stack表示栈,res表示存放节点值的结果列表。
相关问题
先序非递归遍历算法遍历二叉树 中序非递归遍历算法遍历二叉树 后序非递归遍历算法遍历二叉树 层序遍历二叉树
好的,我可以给您介绍一下二叉树的四种非递归遍历算法以及层序遍历。
先序非递归遍历算法:
1. 新建一个栈,将根节点入栈。
2. 当栈不为空时,取出栈顶元素并访问它。
3. 将当前节点的右子节点(如果存在)入栈,再将左子节点(如果存在)入栈。
4. 重复步骤2-3,直到栈为空。
中序非递归遍历算法:
1. 新建一个栈,将根节点入栈。
2. 如果当前节点不为空,则将当前节点的左子节点全部入栈,并将当前节点置为左子节点。
3. 如果当前节点为空,则取出栈顶元素并访问它,将当前节点置为它的右子节点。
4. 重复步骤2-3,直到栈为空。
后序非递归遍历算法:
1. 新建两个栈:s1和s2,将根节点入s1。
2. 当s1不为空时,取出栈顶元素并将其压入s2中。
3. 将当前节点的左子节点(如果存在)入s1,再将右子节点(如果存在)入s1。
4. 重复步骤2-3,直到s1为空。
5. 依次访问s2中的元素即可得到后序遍历结果。
层序遍历算法:
1. 新建一个队列,将根节点入队。
2. 当队列不为空时,取出队首元素并访问它。
3. 将当前节点的左子节点(如果存在)入队,再将右子节点(如果存在)入队。
4. 重复步骤2-3,直到队列为空。
二叉树先序遍历非递归算法
二叉树的先序遍历是一种常见的树结构遍历方法,它按照“根-左-右”的顺序访问每个节点。非递归算法通常使用栈来辅助完成。以下是二叉树先序遍历的非递归算法步骤:
1. 创建一个空栈和一个指向根节点的指针(如果根节点存在)。
2. 当栈不为空或当前节点不为 null 时,执行以下操作:
a. 如果当前节点不为 null,将当前节点压入栈中。
b. 访问当前节点(即打印或处理当前节点的数据)。
c. 将当前节点设置为其右子节点(如果存在)。
3. 在访问完当前节点后,将栈顶元素弹出并更新为栈顶元素的左子节点,然后继续上述循环,直到栈为空。
下面是算法的伪代码:
```
function preorderTraversal(root):
stack = []
current = root
while stack or current is not null:
# 如果当前节点不为空,将其压入栈并访问
if current is not null:
stack.append(current)
print(current.value) # 替换成实际的操作
current = current.left # 移动到左子节点
# 如果当前节点为空,从栈顶取出节点并移动到其右子节点
else:
current = stack.pop()
current = current.right
```
阅读全文