• 二叉树的基本运算
    • 二叉树的定义
    • 由str创建二叉链
    • 求二叉树高度
    • 求二叉树的结点个数
    • 求二叉树的叶子结点个数
    • 以括号表示法输出二叉树
    • 以凹入表示法输出一棵二叉树
    • main

    二叉树的基本运算

    二叉树的定义

    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. }