二叉树的非递归中序遍历代码
时间: 2023-12-10 07:34:57 浏览: 32
以下是二叉树的非递归中序遍历代码:
```C++
vector<int> inorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
vector<int> res;
TreeNode* cur = root;
while (cur || !st.empty()) {
while (cur) {
st.push(cur);
cur = cur->left;
}
cur = st.top();
st.pop();
res.push_back(cur->val);
cur = cur->right;
}
return res;
}
```
该代码使用了栈来模拟递归过程,具体实现如下:
1. 初始化栈和结果数组,将当前节点指向根节点。
2. 当前节点不为空或栈不为空时,执行以下操作:
a. 当前节点不为空时,将当前节点入栈,并将当前节点指向其左子节点,直到当前节点为空。
b. 当前节点为空时,从栈中弹出一个节点,将其值加入结果数组中,并将当前节点指向该节点的右子节点。
3. 返回结果数组。
相关问题
二叉树的非递归中序遍历C++
二叉树的非递归中序遍历可以使用栈来实现。具体步骤如下:
1. 创建一个空栈和一个指向根节点的指针。
2. 将当前节点指针指向根节点。
3. 循环执行以下步骤,直到栈为空且当前节点指针为空:
- 将当前节点指针的所有左子节点依次入栈,直到当前节点指针为空。
- 弹出栈顶元素作为当前节点,并输出当前节点的值。
- 将当前节点指针指向当前节点的右子节点。
下面是一个示例的C++代码实现:
```cpp
#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 inorderTraversal(TreeNode* root) {
stack<TreeNode*> s;
TreeNode* curr = root;
while (curr != NULL || !s.empty()) {
while (curr != NULL) {
s.push(curr);
curr = curr->left;
}
curr = s.top();
s.pop();
cout << curr->val << " ";
curr = curr->right;
}
}
int main() {
// 构造二叉树
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);
// 非递归中序遍历
cout << "非递归中序遍历结果:";
inorderTraversal(root);
return 0;
}
```
二叉树的非递归中序遍历
二叉树的非递归中序遍历可以通过使用栈来实现。具体实现思路如下:
1. 从根节点开始,将所有左子树节点依次入栈,直到最左边的叶子节点。
2. 弹出栈顶节点并访问它。
3. 如果该节点有右子树,则将右子树节点入栈。
4. 重复步骤2和3,直到栈为空。
下面是C++代码实现:
```cpp
void inorderTraversal(TreeNode* root) {
stack<TreeNode*> s;
TreeNode* cur = root;
while (cur != nullptr || !s.empty()) {
while (cur != nullptr) {
s.push(cur);
cur = cur->left;
}
cur = s.top();
s.pop();
// 访问节点
cout << cur->val << " ";
cur = cur->right;
}
}
```
其中,`TreeNode`是二叉树节点的结构体,包含`val`、`left`和`right`三个成员变量。