数据结构实验之二叉树的建立与遍历

淩亂°似流年 2022-05-16 23:58 191阅读 0赞

二叉树的遍历分为以下三种：

先序遍历：遍历顺序规则为【根左右】

中序遍历：遍历顺序规则为【左根右】

后序遍历：遍历顺序规则为【左右根】

什么是【根左右】？就是先遍历根，再遍历左孩子，最后遍历右孩子。其余的同理；

举个例子，看下图（图从网上找的）：

![Center][]

先序遍历：ABCDEFGHK

中序遍历：BDCAEHGKF

后序遍历：DCBHKGFEA

代码实现起来非常的简单，只需要几个递归函数就可以实现树的中序后序遍历；举个题目的例子看下吧  
链接：[https://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/2562/pid/2136][https_acm.sdut.edu.cn_onlinejudge2_index.php_Home_Contest_contestproblem_cid_2562_pid_2136]，这个题目包括了二叉树的一些基本的东西很经典，有求树叶以及深度还有中后遍历。

代码实现：

#include<bits/stdc++.h>
    using namespace std;
    char s[110];
    int i,sum;
    struct tree
    {
        char data;
        tree *lc,*rc;
    }*T;
    tree *creat()///按照先序遍历创建一颗二叉树；
    {
        tree *t;
        if(s[i++]==',')
            t=NULL;
        else
        {
            t=new tree;
            t->data=s[i-1];
            t->lc=creat();
            t->rc=creat();
        }
        return t;
    }
    void inorder(tree *T)///通过递归输出中序遍历的结果
    {
        if(T!=NULL)
        {
            inorder(T->lc);
            cout<<T->data;
            inorder(T->rc);
        }
    }
    void postorder(tree *T)///通过递归输出后序遍历的结果；
    {
        if(T!=NULL)
        {
            postorder(T->lc);
            postorder(T->rc);
            cout<<T->data;
        }
    }
    void coutleaf(tree *T)
    {
        if(T)///判断当前节点是否为空；
        {
        if((!T->lc)&&(!T->rc))
            sum++;
        coutleaf(T->lc);
        coutleaf(T->rc);
        }
    }
    int depth(tree *T)
    {
        int l,r;
        if(!T)///如果为空则输出0；
            return 0;
        else
        {
            l=depth(T->lc);
            r=depth(T->rc);
            return l>=r?l+1:r+1;///+1是为了加上根节点;
        }
    }
    int main()
    {
        while(~scanf("%s",s))
        {
            sum=0;///用来统计叶子数；
            i=0;
            T=creat();
            inorder(T);
            cout<<endl;
            postorder(T);
            cout<<endl;
            coutleaf(T);
            cout<<sum<<endl;
            cout<<depth(T);
    
        }
    }

[Center]: /images/20220517/006365e5e5b84bec82c16046fae96945.png
[https_acm.sdut.edu.cn_onlinejudge2_index.php_Home_Contest_contestproblem_cid_2562_pid_2136]: https://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/2562/pid/2136