迭代方式实现中序遍历的非递归算法 - 汇站网

迭代方式实现中序遍历的非递归算法

2023-12-11 0 392

思路:

1.从根节点开始,一直向左子树遍历,同时将经过的节点入栈。
2.当左子树为空时,弹出栈顶元素,访问该节点,并转向其右子树,然后重复步骤 1。
3.直到栈为空且当前节点为空时,遍历结束。
迭代方式实现中序遍历的非递归算法

参考代码:

#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;
}

转载请注明:汇站网 » 迭代方式实现中序遍历的非递归算法

收藏 (0)

微信扫一扫

支付宝扫一扫

点赞 (0)

感谢您的来访,获取更多精彩资源请收藏本站。

本站声明

本资源仅用于个人学习和研究使用,禁止用于任何商业环境!

 1.  本网站名称:汇站网
 2.  本站永久网址:https://www.huizhanii.com/
 3.  本站所有资源来源于网友投稿和高价购买,所有资源仅对编程人员及源代码爱好者开放下载做参考和研究及学习,本站不提供任何技术服务!
 4.  未经原版权作者许可,禁止用于任何商业环境,任何人不得擅作它用,下载者不得用于违反国家法律,否则发生的一切法律后果自行承担!
 5.  为尊重作者版权,请在下载24小时内删除!请购买原版授权作品,支持你喜欢的作者,谢谢!
 6.  若资源侵犯了您的合法权益, 请持您的版权证书和相关原作品信息来信通知我们请来信     通知我们我们会及时删除,给您带来的不便,我们深表歉意!
 7.  如下载链接失效、广告或者压缩包问题请联系站长处理!
 8.  如果你也有好源码或者教程,可以发布到网站,分享有金币奖励和额外收入!
 9.  本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
 10.  因源码具有可复制性,一经赞助 ,不得以任何形式退款。
 11.  更多详情请点击查看

汇站网 C/C++ 迭代方式实现中序遍历的非递归算法 https://www.huizhanii.com/34104.html

汇站

站长资源下载中心-找源码上汇站

常见问题
  • 如果付款后没有弹出下载页面,多刷新几下,有问题联系客服!
查看详情
  • 本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。
查看详情

相关文章

发表评论
暂无评论
  随机评论 表情开关按钮图片
表情表情表情表情表情表情表情表情表情表情表情表情表情表情表情表情表情表情表情表情表情表情表情表情表情表情表情表情表情表情表情表情表情表情表情表情表情表情表情
登录后评论
联系官方客服

为您解决烦忧 - 24小时在线 专业服务

(汇站网)一个专注站长资源的平台网站,提供最新的网站模板和整站源码,内容包含各类精品网页模板,企业网站模板,网站模板,DIV+CSS模板,织梦模板,帝国cms模板,discuz模板,wordpress模板,个人博客论坛模板,上千种免费网页模板下载尽在汇站网.找源码上汇站.huizhanii.com