头歌非递归中序遍历二叉树
时间: 2023-11-14 17:00:10 浏览: 69
非递归中序遍历二叉树的方法是使用栈来实现。具体步骤如下:
1. 创建一个空栈和一个指向根节点的指针。
2. 将当前节点指针沿着左子树一直往下移动,并将经过的节点依次入栈。
3. 当当前节点为空时,从栈中弹出一个节点作为当前节点,并输出它。
4. 将当前节点指针指向弹出节点的右子树。
5. 重复步骤2到步骤4,直到栈为空且当前节点为空。
这样,就可以实现非递归的中序遍历二叉树。
相关问题
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 inorderTraversal(TreeNode* root) {
stack<TreeNode*> s;
TreeNode* cur = root;
while (cur != NULL || !s.empty()) {
while (cur != NULL) {
s.push(cur);
cur = cur->left;
}
cur = s.top();
s.pop();
cout << cur->val << " ";
cur = cur->right;
}
}
int main() {
TreeNode* root = new TreeNode(1);
root->right = new TreeNode(2);
root->right->left = new TreeNode(3);
inorderTraversal(root); // 输出:1 3 2
return 0;
}
```
如何用c++非递归中序遍历二叉树
以下是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* cur = root;
while (cur != NULL || !s.empty()) {
while (cur != NULL) {
s.push(cur);
cur = cur->left;
}
cur = s.top();
s.pop();
cout << cur->val << " ";
cur = cur->right;
}
}
int main() {
TreeNode* root = new TreeNode(1);
root->right = new TreeNode(2);
root->right->left = new TreeNode(3);
inorderTraversal(root); // 输出:1 3 2
return 0;
}
```