迭代,中序遍历非递归实现 。小编来告诉你更多相关信息 。
中序遍历非递归实现
跟大家分享中序遍历非递归实现的话题，接下来分享详细内容 。
思路：
- 从根节点开始，一直访问左子树，同时将经过的节点入栈 。
- 当左子树访问完毕（为空）时 ， 弹出栈顶元素，访问该节点，并转向其右子树，然后重复步骤1 。
- 直到栈为空且当前节点为空时 ， 遍历结束 。
文章插图
【迭代 中序遍历非递归实现】参考代码：
#include #include // 二叉树的节点结构struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}};void inorderTraversal(TreeNode* root) {std::stack 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 <val <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;}本文分享的中序遍历非递归实现 迭代的详细讲解，仅供大家参考建议！