数据结构第七章实验题6 求二叉树中的结点个数，叶子结点个数，某结点层次和二叉树宽度

- 日理万妓 2022-02-13 07:41 183阅读 0赞

目的：掌握二叉树遍历算法的应用，熟练使用先序、中序、后序3种递归遍历算法和层次遍历算法进行二叉树的问题求解。

内容：编写一个程序exp7-6.cpp实现以下功能，并对图7.33所示的二叉树进行验证。

（1）输出二叉树b的结点个数。

（2）输出二叉树b的叶子结点个数。

（3）求二叉树b中指定结点值（假设所有节点值不同）的结点层次。

（4）利用层次遍历求二叉树b的宽度。

代码如下：

#include<bits/stdc++.h>
    using namespace std;
    const int MaxSize=99999;
    int num=0;
    typedef struct node
    {
        int data;
        struct node * lchild;
        struct node * rchild;
    }BTNode;
    void CreateBtree(BTNode * &b,char *str)
    {
        BTNode * St[MaxSize],* p;
        int top=-1,k,j=0;
        char ch;
        b=NULL;
        ch=str[j];
        while(ch!='\0')
        {
            switch(ch)
            {
                case '(' : top++;St[top]=p;k=1;break;
                case ')' : top--;break;
                case ',' : k=2;break;
                default : p=(BTNode * )malloc (sizeof(BTNode));
                p->data=ch;
                p->lchild=p->rchild=NULL;
                if(b==NULL)
                    b=p;
                else
                {
                    switch(k)
                    {
                        case 1:St[top]->lchild=p;break;
                        case 2:St[top]->rchild=p;break;
                    }
                }
            }
            j++;
            ch=str[j];
        }
    }
    void DestroyBTree(BTNode * &b)//销毁二叉树
    {
        if(b!=NULL)
        {
            DestroyBTree(b->lchild);
            DestroyBTree(b->rchild);
            free(b);
        }
    }
    BTNode *FindNode(BTNode * b,int x)//查找结点FindNode(b,x)
    {
        BTNode * p;
        if(b==NULL)
            return NULL;
        else if(b->data==x)
            return b;
        else
        {
            p=FindNode(b->lchild,x);
            if(p!=NULL)
                return p;
            else
                return FindNode(b->rchild,x);
        }
    }
    BTNode * LchildNode(BTNode * p)//找孩子结点LchildNode(p)
    {
        return p->lchild;
    }
    BTNode * RchildNode(BTNode * p)//找孩子结点RchildNode(p)
    {
        return p->rchild;
    }
    int BTHeight(BTNode *b)//求高度BTHeight(b)
    {
        int lchildh,rchildh;
        if(b==NULL)
            return 0;
        else
        {
            lchildh =BTHeight (b->lchild);
            rchildh =BTHeight(b->rchild);
            return (lchildh>rchildh)?(lchildh+1):(rchildh+1);
        }
    }
    void DispBTree(BTNode * b)//输出二叉树
    {
        if(b!=NULL)
        {
            printf("%c",b->data);
            if(b->lchild!=NULL||b->rchild!=NULL)
            {
                printf("(");
                DispBTree(b->lchild);
                if(b->rchild!=NULL)
                    printf(",");
                DispBTree(b->rchild);
                printf(")");
            }
        }
    }
    void PreOrder(BTNode * b)//先序遍历
    {
        if(b!=NULL)
        {
            printf("%c ",b->data);
            PreOrder(b->lchild);
            PreOrder(b->rchild);
        }
    }
    void InOrder(BTNode * b)//中序遍历
    {
        if(b!=NULL)
        {
            InOrder(b->lchild);
            printf("%c ",b->data);
            num++;
            InOrder(b->rchild);
        }
    }
    void PostOrder(BTNode * b)//后序遍历
    {
        if(b!=NULL)
        {
            PostOrder(b->lchild);
            PostOrder(b->rchild);
            printf("%c ",b->data);
        }
    }
    int WidthOfBiTree(BTNode *root)//层次遍历求二叉树的最大宽度
    {
        if(root == NULL)
            return 0;
     
        int maxWidth = 0;
        deque<BTNode *> d;
        d.push_back(root);
        while(true)
        {
            int len = d.size();
            if(len == 0)
                break;
            while(len > 0)
            {
                BTNode* temp = d.front();
                d.pop_front();
                len--;
                if(temp->lchild)
                    d.push_back(temp->lchild);
                if(temp->rchild)
                    d.push_back(temp->rchild);
            }
            maxWidth = maxWidth > d.size() ? maxWidth : d.size();//maxWidth=max(maxWidth,d.size());<==错误写法，数据类型不同
        }
        return maxWidth;
    }
    int numleaf=0;
    void DispLeaf(BTNode * b)//叶子节点个数numleaf，以及遍历叶子节点
    {
        if(b!=NULL)
        {
            if(b->lchild==NULL&&b->rchild==NULL){
                printf("%c ",b->data);
                numleaf++;
            }
            DispLeaf(b->lchild);
            DispLeaf(b->rchild);
        }
    }
    int Level(BTNode * b,int x,int h)//求指定结点的层次。
    {
        int l;
        if(b==NULL)
            return (0);
        else if(b->data==x)
            return (h);
        else
        {
            l=Level(b->lchild,x,h+1);
            if(l!=0)
                return (l);
            else
                return (Level(b->rchild,x,h+1));
        }
    }
    int main()
    {
        char a[]={"A(B(D,E(H(J,K(L,M(,N))),)),C(F,G(,I)))"};
        BTNode *b;
        CreateBtree(b,a);
        InOrder(b);
        cout<<endl;
        cout<<"结点个数为："<<num<<endl;
        cout<<"所有的叶子结点为："<<endl;
        DispLeaf(b);
        cout<<endl<<"叶子结点个数为："<<numleaf<<endl;
        cout<<"二叉树中，各结点值的结点的层次："<<endl;
        for(int i='A';i<num+'A';i++)
        {
            cout<<"结点"<<char(i)<<"的层次为"<<Level(b,i,1)<<endl;
        }
        cout<<"层次遍历求得该二叉树的最大宽度为："<<WidthOfBiTree(b)<<endl;
        return 0;
    }

转载自[https://blog.csdn.net/ytuyzh/article/details/84768366][https_blog.csdn.net_ytuyzh_article_details_84768366]

[https_blog.csdn.net_ytuyzh_article_details_84768366]: https://blog.csdn.net/ytuyzh/article/details/84768366