数据结构—二叉树练习—递归

素颜马尾好姑娘i 2022-08-22 13:15 269阅读 0赞

/*
    以孩子兄弟链作为树的存储结构，编写一个求树高度的递归算法。
    递归模型：
    设f(t)为树t的高度：
         f(t)=0     若t==NULL
         f(t)=1     若t没有孩子节点
         f(t)=MAX(f(p))+1   其他情况   (p为t的孩子)
    */
    int TreeHeight(TSBNode *t)
    {
        TSBNode *p;
        int m,max=0;
        if(t==NULL)   //空树
            return (0);
        else if(t->vp==NULL)  //孩子节点为NULL
            return 1;
        else
        {
            p=t->vp;    //指向第一个孩子节点
            while(p!=NULL)    //从所有孩子节点中找出一个高度最大的孩子节点
            {
                m=TreeHeight(p);
                if(max<m)
                    max=m;
                p=p->vp;   //继续求其他兄弟的高度
            }
            return (max+1);
        }
    }

/*
    二叉树应用练习：（假设二叉树采用二叉链存储结构）
    （1）计算二叉树结点个数；
    （2）输出一颗给定二叉树的所有叶子节点；
    （3）求二叉树中节点值为x的节点的层数；
    （4）判断两颗二叉树是否相似，所谓二叉树b1和b2相似是指b1和b2都是空树；或者b1和b2的根节点相似，且左子树和右子树分别相似；
    （5）输出值为x的节点的所有祖先。
    */
    #include <iostream>
    #include <malloc.h>
    #define MaxSize 100
    typedef char ElemType;
    using namespace std;
    typedef struct node
    {
        ElemType data;   //数据元素
        struct node *lchild;  //指向左孩子节点
        struct node *rchild;  //指向右孩子节点
    } BTNode;
    
    void CreateBTNode(BTNode *&b,char *str)   //创建二叉树
    {
        BTNode *St[MaxSize],*p;
        int top=-1,k,j=0;
        char ch;
        b=NULL;    //二叉树初始时为空
        ch=str[j];
        while(ch!='\0')    //循环扫描str中的每个字符
        {
            switch(ch)
            {
            case '(':   //开始处理左孩子节点
                top++;
                St[top]=p;
                k=1;   //将(之前的字符进栈，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;       //*p为二叉树的根节点
                else            //已建立二叉树根节点
                {
                    switch(k)
                    {
                    case 1:
                        St[top]->lchild=p;
                        break;
                    case 2:
                        St[top]->rchild=p;
                        break;
                    }
                }
            }
            j++;
            ch=str[j];     //循环str中的每个字符
        }
    }
    
    /*
    递归模型：
       f(b)=0             ,b==NULL
       f(b)=f(b->lchild)+f(b->rchild)+1   ,其他情况
    */
    int Nodes(BTNode *b)  //计算节点的个数
    {
        if(b==NULL)
            return 0;
        else
            return Nodes(b->lchild)+Nodes(b->rchild)+1;
    }
    
    /*
    递归模型：
        f(b)=不作任何事件    若b==NULL
        f(b)=输出*b节点的data域   若*b为叶子节点
        f(b)=f(b->lchild);f(b)=(b->rchild)    其他情况
    */
    void DispLeaf(BTNode *b)
    {
        if(b!=NULL)
        {
            if(b->lchild==NULL&&b->rchild==NULL)
                cout<<b->data;
            DispLeaf(b->lchild);
            DispLeaf(b->rchild);
        }
    }
    
    /*
    递归模型：
        f(b)=0    若b==NULL
        f(b)=h    若b->data==x
        f(b)=Level(b->lchild);Level(b->rchild)    其他情况
    */
    int Level(BTNode *b,ElemType x,int h)   //h置初值为1
    {
        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));
        }
    }
    
    /*
    递归模型：
        f(t1,t2)=true    若t1=t2=NULL
        f(t1,t2)=false   若t1、t2之一为NULL，另一个不为NULL
        f(t1,t2)=f(t1->lchild,t2->lchild)&&f(t1->rchild,t2->rchild);    其他情况
    */
    bool Like(BTNode *b1,BTNode *b2)   //b1和b2两棵二叉树相似时返回true，否则返回false
    {
        bool like1,like2;
        if(b1==NULL&&b2==NULL)
            return true;
        else if(b1==NULL||b2==NULL)
            return false;
        else
        {
            like1=Like(b1->lchild,b2->lchild);
            like2=Like(b1->rchild,b2->rchild);
            return (like1&&like2);
        }
    }
    
    /*
    递归模型：
        f(b,x)=false    若b==NULL
        f(b,x)=true，并输出b->data   若*b节点的左或右孩子data域为x
        f(b,x)=true，并输出b->data   若f(b->lchild,x)==true或f(b->rchild,x)==true
        f(b,x)=false    其他情况
    */
    bool ancestor(BTNode *b,ElemType x)   //输出节点值为x的祖先
    {
        if(b==NULL)
            return false;
        else if(b->lchild!=NULL&&b->lchild->data==x||b->rchild!=NULL&&b->rchild->data==x)
        {
            cout<<b->data;
            return true;
        }
        else if(ancestor(b->lchild,x)||ancestor(b->rchild,x))
        {
            cout<<b->data;
            return true;
        }
        else
            return false;
    }
    int main()
    {
        BTNode *b,*b1;
        bool c;
        CreateBTNode(b,"A(B(D(,G)),C(E,F))");
        CreateBTNode(b1,"A(B(D(,G)),C(E,F))");
        cout<<"节点的个数："<<Nodes(b)<<endl;
        cout<<"输出叶子节点：";
        DispLeaf(b);
        cout<<endl;
        cout<<"输出节点值为D的节点的层数："<<Level(b,'D',1)<<endl;
        if(Like(b,b1))
            cout<<"b和b1是否相似? 是"<<endl;
        else
            cout<<"b和b1是否相似? 否"<<endl;
        cout<<"节点值为G的祖先：";
        c=ancestor(b,'G');
        cout<<endl;
        return 0;
    }

运行结果：

![Center][]

[Center]: /images/20220722/63b4ccbedf3a4c60873681bc92633b9e.png