二叉树的基本运算

二叉树的定义

  1. #include <stdio.h>
  2. #include <malloc.h>
  3. #define MaxSize 100
  4. #define MaxWidth 40
  6. typedef char ElemType;
  8. typedef struct tnode
  9. {
  10.     ElemType data;
  11.     struct tnode *lchild,*rchild;
  12. } BTNode;

由str创建二叉链

  1. void CreateBTree(BTNode * &bt,char *str)    /*由str创建二叉链bt*/
  2. {
  3.     BTNode *St[MaxSize],*p=NULL;
  4.     int top=-1,k,j=0;  
  5.     char ch;
  6.     bt=NULL;            /*建立的二叉树初始时为空*/
  7.     ch=str[j];
  8.     while (ch!='\0')      /*str未扫描完时循环*/
  9.     {
  10.               switch(ch) 
  11.         {
  12.         case '(':top++;St[top]=p;k=1; break;    /*为左孩子结点*/
  13.         case ')':top--;break;
  14.         case ',':k=2; break;                    /*为孩子结点右结点*/
  15.         default:p=(BTNode *)malloc(sizeof(BTNode));
  16.                 p->data=ch;p->lchild=p->rchild=NULL;
  17.                 if (bt==NULL)                   /**p为二叉树的根结点*/
  18.                     bt=p;
  19.                 else                              /*已建立二叉树根结点*/
  20.                 {    switch(k) 
  21.                     {
  22.                     case 1:St[top]->lchild=p;break;
  23.                     case 2:St[top]->rchild=p;break;
  24.                     }
  25.                 }
  26.         }
  27.         j++;
  28.         ch=str[j];
  29.     }
  30. }

求二叉树高度

  1. int BTHeight(BTNode *bt)    /*求二叉树高度*/
  2. {
  3.        int lchilddep,rchilddep;
  4.        if (bt==NULL) return(0);             /*空树的高度为0*/
  5.        else  
  6.     {    lchilddep=BTHeight(bt->lchild);    /*求左子树的高度为lchilddep*/
  7.           rchilddep=BTHeight(bt->rchild);    /*求右子树的高度为rchilddep*/
  8.         return (lchilddep>rchilddep)? (lchilddep+1):(rchilddep+1);
  9.        }
  10. }

求二叉树的结点个数

  1. int NodeCount(BTNode *bt)    /*求二叉树bt的结点个数*/
  2. {
  3.     int num1,num2;
  4.         if (bt==NULL)    /*空树结点个数为0*/ 
  5.             return 0;
  6.         else
  7.         {    num1=NodeCount(bt->lchild);    /*求出左子树的结点数*/
  8.             num2=NodeCount(bt->rchild);    /*求出右子树的结点数*/
  9.             return (num1+num2+1);
  10.     }
  11. }

求二叉树的叶子结点个数

  1. int LeafCount(BTNode *bt)    /*求二叉树bt的叶子结点个数*/
  2. {
  3.     int num1,num2;
  4.         if (bt==NULL)    /*空树叶子结点个数为0*/ 
  5.             return 0;
  6.         else if (bt->lchild==NULL && bt->rchild==NULL) 
  7.             return 1;    /*若为叶子结点返回1*/ 
  8.         else
  9.         {    num1=LeafCount(bt->lchild);    /*求出左子树的叶子结点数*/
  10.             num2=LeafCount(bt->rchild);    /*求出右子树的叶子结点数*/
  11.             return (num1+num2);
  12.     }
  13. }

以括号表示法输出二叉树

  1. void DispBTree(BTNode *bt)    /*以括号表示法输出二叉树*/
  2. {
  3.     if (bt!=NULL)
  4.     {    
  5.         printf("%c",bt->data);
  6.         if (bt->lchild!=NULL || bt->rchild!=NULL)
  7.         {    
  8.             printf("(");
  9.             DispBTree(bt->lchild);        /*递归处理左子树*/
  10.             if (bt->rchild!=NULL) 
  11.                 printf(",");
  12.             DispBTree(bt->rchild);        /*递归处理右子树*/
  13.             printf(")");
  14.         }
  15.     }
  16. }

以凹入表示法输出一棵二叉树

  1. void DispBTree1(BTNode *bt)  /*以凹入表示法输出一棵二叉树*/
  2. {
  3.     BTNode *St[MaxSize],*p;
  4.     int Level[MaxSize][2],top=-1,n,i,width=4;
  5.     char type;        /*取值L表示为左结点,R表示为右结点,B表示为根结点*/
  6.     if (bt!=NULL)
  7.     {    
  8.         top++;
  9.         St[top]=bt;                        /*根结点入栈*/
  10.         Level[top][0]=width;
  11.         Level[top][1]=2;                /*2表示是根*/
  12.         while (top>-1)
  13.         {    
  14.             p=St[top];                    /*退栈并凹入显示该结点值*/
  15.             n=Level[top][0];
  16.             switch(Level[top][1])
  17.             {
  18.             case 0:type='L';break;        /*左结点之后输出(L)*/
  19.             case 1:type='R';break;        /*右结点之后输出(R)*/
  20.             case 2:type='B';break;        /*根结点之后前输出(B)*/
  21.             }
  22.             for (i=1;i<=n;i++)            /*其中n为显示场宽,字符以右对齐显示*/
  23.                 printf(" ");
  24.             printf("%c(%c)",p->data,type);
  25.             for (i=n+1;i<=MaxWidth;i+=2)
  26.                 printf("━");
  27.             printf("\n");
  28.             top--;
  29.             if (p->rchild!=NULL)
  30.             {                            /*将右子树根结点入栈*/
  31.                 top++;
  32.                 St[top]=p->rchild;
  33.                 Level[top][0]=n+width;    /*场宽增width,即缩width格后再输出*/
  34.                 Level[top][1]=1;        /*1表示是右子树*/
  35.             }
  36.             if (p->lchild!=NULL)
  37.             {                            /*将左子树根结点入栈*/
  38.                 top++;
  39.                 St[top]=p->lchild;
  40.                 Level[top][0]=n+width;  /*显示场宽增width*/
  41.                 Level[top][1]=0;        /*0表示是左子树*/
  42.             }
  43.         }
  44.     }
  45. }

main

  1. void main()
  2. {
  3.     BTNode *bt;
  4.     CreateBTree(bt,"A(B(D,E(G,H)),C(,F(I)))");    /*构造图5.10(a)所示的二叉树*/
  5.     printf("二叉树bt:");DispBTree(bt);printf("\n");
  6.     printf("bt的高度:%d\n",BTHeight(bt));
  7.     printf("bt的结点数:%d\n",NodeCount(bt));
  8.     printf("bt的叶子结点数:%d\n",LeafCount(bt));
  9.     printf("bt凹入表示:\n");DispBTree1(bt);printf("\n");
  10. }