您现在的位置是:群英 > 开发技术 > 编程语言
基于C语言的二叉树中序遍历方法是什么
Admin发表于 2022-10-28 17:50:58306 次浏览
这篇文章给大家分享的是“基于C语言的二叉树中序遍历方法是什么”,文中的讲解内容简单清晰,对大家学习和理解有一定的参考价值和帮助,有这方面学习需要的朋友,接下来就跟随小编一起学习一下“基于C语言的二叉树中序遍历方法是什么”吧。

中序遍历的遍历方法为:对于当前结点,首先遍历左子树,然后访问当前节点,最后遍历右子树。中序遍历是二叉树遍历的一种,也叫做中根遍历、中序周游。

本教程操作环境:windows7系统、C++17版本、Dell G3电脑。

二叉树是一种重要的数据结构,对二叉树的遍历也很重要。这里简单介绍三种二叉树中序遍历的方法。二叉树的中序遍历就是首先遍历左子树,然后访问当前节点,最后遍历右子树。对于下面的二叉树,中序遍历结果如下:


结果:[5,10,6,15,2]

直观来看,二叉树的中序遍历就是将节点投影到一条水平的坐标上。如图:


1、递归法

这是思路最简单的方法,容易想到并且容易实现。递归的终止条件是当前节点是否为空。首先递归调用遍历左子树,然后访问当前节点,最后递归调用右子树。代码如下:

//recursive
class Solution1 {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ret;
        if(root==NULL)return ret;
        inorderHelper(ret,root);
        return ret;
    }
private:
    void inorderHelper(vector<int>& ret,TreeNode* root)
    {
        if(root==NULL)return;
        inorderHelper(ret,root->left);
        ret.push_back(root->val);
        inorderHelper(ret,root->right);
    }
};

2、迭代法

在迭代方法中,从根节点开始找二叉树的最左节点,将走过的节点保存在一个栈中,找到最左节点后访问,对于每个节点来说,它都是以自己为根的子树的根节点,访问完之后就可以转到右儿子上了。代码如下:

//iterate,using a stack
class Solution2 {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ret;
        if(root==NULL)return ret;
        TreeNode *curr=root;
        stack<TreeNode*> st;
        while(!st.empty()||curr!=NULL)
        {
            while(curr!=NULL)
            {
                st.push(curr);
                curr=curr->left;
            }
            curr=st.top();
            st.pop();
            ret.push_back(curr->val);
            curr=curr->right;
        }
        return ret;
    }
};

这种方法时间复杂度是O(n),空间复杂度也是O(n)。

3、Morris法

这种方法是Morris发明的,看完之后感觉精妙无比。这种方法不使用递归,不使用栈,O(1)的空间复杂度完成二叉树的遍历。这种方法的基本思路就是将所有右儿子为NULL的节点的右儿子指向后继节点(对于右儿子不为空的节点,右儿子就是接下来要访问的节点)。这样,对于任意一个节点,当访问完它后,它的右儿子已经指向了下一个该访问的节点。对于最右节点,不需要进行这样的操作。注意,这样的操作是在遍历的时候完成的,完成访问节点后会把树还原。整个循环的判断条件为当前节点是否为空。例如上面的二叉树,遍历过程如下(根据当前节点c的位置):

(1)当前节点为10,因为左儿子非空,不能访问,找到c的左子树的最右节点p:


结果:[]

(2)找节点c的左子树的最右节点有两种终止条件,一种右儿子为空,一种右儿子指向当前节点。下面是右儿子为空的情况,这种情况先要构造,将节点p的右儿子指向后继节点c,然后c下移:


结果:[]

(3)当前节点c的左儿子为空,进行访问。访问后将c指向右儿子(即后继节点):


结果:[5]

(4)继续寻找左子树的最右节点,这次的终止条件是最右节点为当前节点。这说明当前节点的左子树遍历完毕,访问当前节点后,还原二叉树,将当前节点指向后继节点:


结果:[5,10]

(5)重复上述过程,直到c指向整棵二叉树的最右节点:


左儿子为空,进行访问,c转到右儿子。右儿子为空,不满足判断条件,循环结束,遍历完成。结果如下:

[5,10,6,15,2]

这就是Morris方法,时间复杂度为O(n),空间复杂度是O(1)。代码如下:

//Morris traversal,without a stack
class Solution3 {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ret;
        if(root==NULL)return ret;
        TreeNode *curr=root;
        TreeNode *pre;
        while(curr)
        {
            if(curr->left==NULL)
            {
                ret.push_back(curr->val);
                curr=curr->right;
            }
            else
            {
                pre=curr->left;
                while(pre->right&&pre->right!=curr)
                    pre=pre->right;
                if(pre->right==NULL)
                {
                    pre->right=curr;
                    curr=curr->left;
                }
                else
                {
                    ret.push_back(curr->val);
                    pre->right=NULL;
                    curr=curr->right;
                }
            }
        }
        return ret;
    }
};



感谢各位的阅读,以上就是“基于C语言的二叉树中序遍历方法是什么”的内容了,通过以上内容的阐述,相信大家对基于C语言的二叉树中序遍历方法是什么已经有了进一步的了解,如果想要了解更多相关的内容,欢迎关注群英网络,群英网络将为大家推送更多相关知识点的文章。

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:mmqy2019@163.com进行举报,并提供相关证据,查实之后,将立刻删除涉嫌侵权内容。

标签: 中序遍历
相关信息推荐
2022-09-28 17:57:23 
摘要:这篇文章主要介绍了PHP之CI框架学习讲解,本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下
2022-04-29 16:42:52 
摘要:这篇文章主要介绍了C语言柔性数组,通过实例分析了不完整类型、结构体及柔性数组等概念,需要的朋友可以参考下
2022-08-02 17:47:00 
摘要:本文由go语言​教程栏目给大家介绍go module如何使用本地包 ,希望对需要的朋友有所帮助!
云活动
推荐内容
热门关键词
热门信息
群英网络助力开启安全的云计算之旅
立即注册,领取新人大礼包
  • 联系我们
  • 24小时售后:4006784567
  • 24小时TEL :0668-2555666
  • 售前咨询TEL:400-678-4567

  • 官方微信

    官方微信
Copyright  ©  QY  Network  Company  Ltd. All  Rights  Reserved. 2003-2019  群英网络  版权所有   茂名市群英网络有限公司
增值电信经营许可证 : B1.B2-20140078   粤ICP备09006778号
免费拨打  400-678-4567
免费拨打  400-678-4567 免费拨打 400-678-4567 或 0668-2555555
微信公众号
返回顶部
返回顶部 返回顶部