思路:
![图片[1]-中序遍历非递归实现(迭代)-编程社](https://cos.bianchengshe.com/wp-content/uploads/2023/11/1941384-20200406095558790-679135811.png?imageMogr2/format/webp/interlace/1/quality/100)
参考代码:
#include <iostream>
#include <stack>
// 二叉树的节点结构
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
void inorderTraversal(TreeNode* root) {
std::stack<TreeNode*> nodeStack;
TreeNode* current = root;
while (current != nullptr || !nodeStack.empty()) {
// 将左子树入栈
while (current != nullptr) {
nodeStack.push(current);
current = current->left;
}
// 访问节点并转向右子树
current = nodeStack.top();
nodeStack.pop();
std::cout << current->val << " "; // 访问节点
current = current->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);
// 中序遍历
std::cout << "Inorder Traversal: ";
inorderTraversal(root);
return 0;
}
© 版权声明
文章版权归作者所有,未经允许请勿转载。
THE END
暂无评论内容