二叉树前序遍历非递归
时间: 2024-10-13 11:00:54 浏览: 16
二叉树的前序遍历是非递归的方式通常通过栈来实现。前序遍历的顺序是根节点 -> 左子树 -> 右子树。以下是步骤:
1. 创建一个空栈,并将根节点压入栈中。
2. 当栈不为空时,执行以下操作:
a. 弹出栈顶元素,访问它(即当前节点)。
b. 如果该节点有右子节点,将其压入栈中。
c. 如果该节点有左子节点,将其压入栈中。
3. 重复步骤2,直到栈为空。
这种方法避免了递归带来的函数调用开销,适合处理大数据量的情况。非递归前序遍历的伪代码可以表示为:
```
void preOrder(Node node) {
Stack<Node> stack;
stack.push(node);
while (!stack.isEmpty()) {
Node current = stack.pop();
// 访问当前节点
processNode(current);
if (current.right != null)
stack.push(current.right);
if (current.left != null)
stack.push(current.left);
}
}
```
相关问题
c++编写二叉树前序遍历非递归
下面是C++编写二叉树前序遍历非递归的代码:
```c++
#include<iostream>
#include<stack>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
void preorderTraversal(TreeNode* root) {
if(root == NULL) {
return;
}
stack<TreeNode*> stk;
stk.push(root);
while(!stk.empty()) {
TreeNode* node = stk.top();
stk.pop();
cout<<node->val<<" ";
if(node->right != NULL) {
stk.push(node->right);
}
if(node->left != NULL) {
stk.push(node->left);
}
}
}
int main() {
// test case
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
root->right->left = new TreeNode(6);
root->right->right = new TreeNode(7);
cout<<"preorderTraversal:"<<endl;
preorderTraversal(root);
return 0;
}
```
上面的代码通过使用栈来模拟递归过程,实现了二叉树的前序遍历。
二叉树前序遍历非递归的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)。
阅读全文