您的位置: 网站首页 > 程序开发 > 数据结构 > 第5章 树与二叉树 > 【5.3 二叉树基本运算算法】

5.3 二叉树基本运算算法

 

5.3  二叉树基本运算算法

5.3.1  二叉树的基本运算

一般地,二叉树有如下几个基本运算。

1CreateBTree(bt,str):根据二叉树的括号表示法str建立二叉链bt

2BTHeight(bt):求一棵二叉树bt的高度。

3NodeCount(bt):求一棵二叉树bt的节点个数。

4LeafCount(bt):求一棵二叉树bt的叶子节点个数。

5DispBTree(bt):以括号表示法输出一棵二叉树bt

6DispBTree1(bt):以凹入表示法输出一棵二叉树bt

5.3.2  二叉树基本运算实现算法

假设二叉树采用二叉链存储结构,实现以上基本运算的算法如下。

1.建立二叉链运算算法

ch扫描采用括号表示法表示二叉树的字符串str。分以下几种情况。

1)若ch='(',则将前面刚创建的节点作为双亲节点进栈,并置k=1,表示其后创建的节点将作为这个节点的左孩子节点。

2)若ch=')',表示栈中节点的左右孩子节点处理完毕,退栈。

3)若ch=',',表示其后创建的节点为右孩子节点。

4)其他情况,表示要创建一个节点,并根据k值建立它与栈中节点之间的联系,当k=1时,表示这个节点作为栈中节点的左孩子节点,当k=2时,表示这个节点作为栈中节点的右孩子节点。如此循环直到str处理完毕。算法中使用一个栈St保存双亲节点,top为其栈指针,k指定其后处理的节点是双亲节点(保存在栈中)的左孩子节点(k=1)还是右孩子节点(k=2)。

对应的算法如下:

void CreateBTree(BTNode * &bt,char *str)

{

    BTNode *St[MaxSize],*p=NULL;

    int top=-1,k,j=0; 

    char ch;

    bt=NULL;                                    /*建立的二叉树初始时为空*/

    ch=str[j];

    while (ch!='\0')                            /*str未扫描完时循环*/

    {

      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 (bt==NULL)                           /*p为二叉树的根节点*/

               bt=p;

           else                                  /*已建立二叉树根节点*/

                {

                switch(k)

                {

                    case 1:St[top]->lchild=p;break;

                    case 2:St[top]->rchild=p;break;

                }

                 }

        }

        j++;

        ch=str[j];

    }

}

2.求二叉树高度运算算法

求二叉树高度的递归模型f(b)如下:

f(b)=

         0                                      b=NULL

         Max{f(b->lchild),f(b->rchild)}+1     其他情况

对应的算法如下:

int BTHeight(BTNode *bt)

{

   int lchilddep,rchilddep;

   if (bt==NULL) return(0);                /*空树的高度为0*/

   else 

    {  

       lchilddep=BTHeight(bt->lchild);      /*求左子树的高度为lchilddep*/

       rchilddep=BTHeight(bt->rchild);      /*求右子树的高度为rchilddep*/

       return (lchilddep>rchilddep)? (lchilddep+1):(rchilddep+1);

   }

}

3.求二叉树节点个数运算算法

对应的递归模型如下:

f(bt)=

         0                                              bt=NULL

               f(bt->lchild)+f(bt->rchild)+1     其他情况

相应的递归算法如下:

int NodeCount(BTNode *bt)                       /*求二叉树bt的节点个数*/

{

    int num1,num2;

    if(bt==NULL)

        return 0;

    else

    {  

num1=NodeCount(bt->lchild);

        num2=NodeCount(bt->rchild);

        return (num1+num2+1);

    }

}

4.求二叉树叶子节点个数运算算法

对应的递归模型如下:

                     0                                        bt=NULL

f(bt)=     1                                        bt为叶子节点

                     f(bt->lchild)+f(bt->rchild)     其他情况

相应的递归算法如下:

int LeafCount(BTNode *bt)                   /*求二叉树bt的叶子节点个数*/

{

    int num1,num2;

    if(bt==NULL)

        return 0;

    else if(bt->lchild==NULL && bt->rchild==NULL)

        return 1;

    else

    {  

        num1=LeafCount(bt->lchild);

        num2=LeafCount(bt->rchild);

        return(num1+num2);

    }

}

5.以括号表示法输出二叉树运算算法

其过程是:对于非空二叉树bt,先输出其元素值,当存在左孩子节点或右孩子节点时,输出一个“(”符号,然后递归处理左子树,输出一个“,”符号,递归处理右子树,最后输出一个“)”符号。对应的递归算法如下:

void DispBTree(BTNode *bt)

{

    if(bt!=NULL)

    {  

        cout << bt->data;

        if(bt->lchild!=NULL || bt->rchild!=NULL)

        {  

            cout<<"(";

            DispBTree(bt->lchild);                      /*递归处理左子树*/

            if(bt->rchild!=NULL)

cout << ",";

            DispBTree(bt->rchild);                      /*递归处理右子树*/

            cout<<")";

        }

    }

}

6.以凹入表示法输出二叉树运算算法

采用先序遍历非递归的方法,用一个栈St保存树中节点指针,用Level数组保存栈中对应节点的输出长宽和该节点的类型(是根节点、双亲节点的左孩子或右孩子)。先将根节点指针进栈,在栈不空时循环:退栈一个节点,以对应的长宽输出,退栈,并将当前节点的右孩子节点(若存在)指针和左孩子节点(若存在)指针进栈。采用凹入表示法输出时,每个节点之前的括号中的标记表示是什么类型的节点,B表示根节点,L表示左节点,R表示右节点。对应的算法如下:

void DispBTree1(BTNode *bt)                 /*以凹入表示法输出一棵二叉树*/

{

    BTNode *St[MaxSize],*p;

    int Level[MaxSize][2],top=-1,n,i,width=4;

    char type;      /*取值L表示为左节点,R表示为右节点,B表示为根节点*/

    if(bt!=NULL)

    {

        top++;

        St[top]=bt;                         /*根节点入栈*/

        Level[top][0]=width;

        Level[top][1]=2;                    /*2表示根*/

        while (top>-1)

        {   p=St[top];                      /*退栈并凹入显示该节点值*/

            n=Level[top][0];

            switch(Level[top][1])

            {

               case 0:type='L';break;       /*左节点之后输出(L)*/

               case 1:type='R';break;       /*右节点之后输出(R)*/

               case 2:type='B';break;               /*根节点之后输出(B)*/

            }

            for (i=1;i<=n;i++)          /*其中n为显示长宽,字符以右对齐显示*/

                cout<<" ";

            cout<<p->data<<"("<<type<<")";

            for(i=n+1;i<=MaxWidth;i+=2)

                cout<<"";

            cout<<endl;

            top--;

            if(p->rchild!=NULL)

            {                                       /*将右子树根节点入栈*/

                top++;

                St[top]=p->rchild;

                Level[top][0]=n+width;  /*长宽增width即缩width格后再输出*/

                Level[top][1]=1;                    /*1表示右子树*/

            }

            if(p->lchild!=NULL)

            {                                       /*将左子树根节点入栈*/

                top++;

                St[top]=p->lchild;

                Level[top][0]=n+width;          /*显示长宽增width*/

                Level[top][1]=0;                     /*0表示左子树*/

            }

        }

    }

}