编写一个c++函数,其能够实现利用栈来对二叉树进行中序遍历
时间: 2024-05-04 15:20:40 浏览: 84
二叉树 中序遍历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) {
if (!root) {
return;
}
stack<TreeNode*> s;
TreeNode* node = root;
while (node || !s.empty()) {
while (node) {
s.push(node);
node = node->left;
}
node = s.top();
s.pop();
cout << node->val << " ";
node = node->right;
}
}
int main() {
TreeNode* root = new TreeNode(1);
root->right = new TreeNode(2);
root->right->left = new TreeNode(3);
cout << "Inorder Traversal of Binary Tree: ";
inorderTraversal(root);
cout << endl;
return 0;
}
```
该函数接受一个二叉树的根节点作为参数,并使用栈来遍历整棵树。在遍历过程中,首先将根节点入栈,然后不断将左子树的节点入栈,直到左子树为空。此时,弹出栈顶元素并输出其值,然后将右子树的节点入栈。重复以上步骤,直到栈为空且遍历完成。
阅读全文