二叉树的前序遍历非递归
时间: 2023-09-07 08:17:24 浏览: 50
二叉树的前序遍历非递归方式可以使用栈来实现。具体步骤如下:
1. 将根节点入栈。
2. 循环执行以下步骤,直到栈为空:
a. 弹出栈顶元素并访问。
b. 如果该节点有右子树,将其右子树入栈。
c. 如果该节点有左子树,将其左子树入栈。
下面是一个示例代码实现:
```
vector<int> preorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> s;
if (root != nullptr) {
s.push(root);
}
while (!s.empty()) {
TreeNode* node = s.top();
s.pop();
result.push_back(node->val);
if (node->right != nullptr) {
s.push(node->right);
}
if (node->left != nullptr) {
s.push(node->left);
}
}
return result;
}
```
其中,TreeNode 是二叉树的节点定义,val 表示节点的值。函数返回值是一个 vector,记录了前序遍历的结果。
相关问题
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)。