二叉树前序遍历非递归怎么实现,请给出完整代码
时间: 2023-01-11 16:55:36 浏览: 71
二叉树的前序遍历非递归实现方式如下:
1. 创建一个栈,用于存储遍历过程中访问的节点。
2. 从根节点开始,将根节点入栈。
3. 重复以下步骤直到栈为空:
- 取出栈顶元素并访问。
- 如果栈顶元素的右子节点不为空,将右子节点入栈。
- 如果栈顶元素的左子节点不为空,将左子节点入栈。
代码如下:
```python
def preorder_traversal(root):
if root is None:
return
stack = []
node = root
while stack or node:
while node:
print(node.val) # 访问节点
stack.append(node)
node = node.left
node = stack.pop()
node = node.right
```
这段代码使用了一个栈来模拟递归过程,每遇到一个节点就将其入栈,然后遍历它的左子树。当左子树遍历完成后,就从栈中取出栈顶元素并遍历它的右子树。
需要注意的是,在取出栈顶元素时,需要将其出栈。这样可以保证每个节点只会被遍历一次,并且保证了遍历的顺序。
相关问题
二叉树前序遍历非递归怎么实现,请给出完整C语言代码
非递归实现二叉树前序遍历的方法是使用栈进行模拟递归的过程。具体步骤如下:
1. 将根节点入栈。
2. 取出栈顶节点并访问。
3. 如果栈顶节点有右子节点,就将右子节点入栈。
4. 如果栈顶节点有左子节点,就将左子节点入栈。
5. 重复步骤 2~4 直到栈为空。
下面是用 C 语言实现二叉树前序遍历的非递归代码:
```
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树的节点结构
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
// 创建二叉树
// 传入的数组是前序遍历的结果
struct TreeNode* createTree(int* preorder, int preorderSize) {
if (preorderSize == 0) return NULL; // 空树
// 创建根节点
struct TreeNode* root = (struct TreeNode*) malloc(sizeof(struct TreeNode));
root->val = preorder[0];
// 在前序遍历序列中找到第一个大于根节点的元素,
// 该元素之前的元素对应根节点的左子树,之后的元素对应根节点的右子树
int i;
for (i = 1; i < preorderSize; i++) {
if (preorder[i] > root->val) break;
}
// 递归创建左右子树
root->left = createTree(preorder + 1, i - 1);
root->right = createTree(preorder + i, preorderSize - i);
return root;
}
// 二叉树前序遍历的非递归实现
二叉树前序遍历非递归的C语言代码
二叉树前序遍历非递归的C语言代码如下:
```c
void preorder_traverse(struct Node *root) {
struct Node *p = root;
struct Stack *s = create_stack();
while (p != NULL || !is_empty(s)) {
if (p != NULL) {
printf("%d ", p->data); // 访问根节点
push(s, p); // 将根节点压入栈中
p = p->left; // 遍历左子树
} else {
p = pop(s); // 弹出栈顶元素
p = p->right; // 遍历右子树
}
}
destroy_stack(s);
}
```
其中,struct Node是二叉树的节点结构体,包含数据域data和左右子树指针left、right。struct Stack是一个用于存储二叉树节点的栈,create_stack()、push()、pop()、is_empty()、destroy_stack()是对应的栈操作函数。
在上述代码中,我们使用一个指针p指向当前遍历到的节点,从根节点开始遍历,每遍历到一个节点,就将其压入栈中。每次从栈中弹出一个节点时,就遍历该节点的右子树。
需要注意的是,在这个算法中,我们需要使用一个辅助栈来存储遍历过程中的节点,因此它的时间复杂度是O(n),空间复杂度也是O(n)。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)