写一个非递归的二叉树序遍历算法代码
时间: 2023-06-16 21:03:44 浏览: 81
二叉树序遍历有前序遍历、中序遍历和后序遍历,非递归的实现方式都是借助栈数据结构来完成的。下面是非递归前序遍历的代码实现:
```python
def preorderTraversal(root):
if not root:
return []
stack, res = [root], []
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
```
非递归中序遍历和后序遍历也可以用类似的方法实现,只需要在遍历节点时候的顺序和加入栈中的顺序做一些调整即可。
相关问题
写一个非递归的先序遍历算法
非递归的先序遍历算法可以使用栈来实现。具体步骤如下:
1. 将根节点入栈
2. 当栈不为空时,取出栈顶元素并访问(即输出)
3. 如果该节点存在右子树,则将其右子树入栈
4. 如果该节点存在左子树,则将其左子树入栈
5. 重复步骤2-4,直到栈为空
下面是一个示例代码:
```python
def preorder(root):
if not root:
return
stack = [root]
while stack:
node = stack.pop()
print(node.val) # 访问节点
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
```
其中,`root`为二叉树的根节点,`stack`为存储节点的栈。在每次循环中,取出栈顶元素并访问,然后将其右子树和左子树(如果存在)分别入栈。循环终止条件是栈为空。
请写出二叉树非递归遍历算法、递归遍历算法 、层次遍历算法的伪代码。
好的,下面是二叉树非递归遍历算法、递归遍历算法、层次遍历算法的伪代码:
1. 二叉树非递归遍历算法(中序遍历)
```
非递归中序遍历二叉树(root为二叉树根节点):
1. 将root节点入栈;
2. 当栈不为空时,取出栈顶元素,如果该元素左子树不为空,则将其左子树全部入栈;
3. 如果该元素左子树为空,或者左子树已经被访问过了,则输出该节点的值,并将其右子树入栈;
4. 重复步骤2~3,直到栈为空为止。
```
2. 二叉树递归遍历算法(先序遍历)
```
递归先序遍历二叉树(root为二叉树根节点):
1. 如果root节点为空,直接返回;
2. 输出root节点的值;
3. 递归遍历root节点的左子树;
4. 递归遍历root节点的右子树。
```
3. 二叉树层次遍历算法
```
层次遍历二叉树(root为二叉树根节点):
1. 将root节点入队列;
2. 当队列不为空时,取出队首元素,输出其值;
3. 如果该元素的左子树不为空,则将其左子树入队列;
4. 如果该元素的右子树不为空,则将其右子树入队列;
5. 重复步骤2~4,直到队列为空为止。
```
以上就是二叉树非递归遍历算法、递归遍历算法、层次遍历算法的伪代码。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)