二叉树的基本运算

    由str创建二叉链

    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.                     bt=p;
    18.                 else                              /*已建立二叉树根结点*/
    19.                 {    switch(k) 
    20.                     {
    21.                     case 1:St[top]->lchild=p;break;
    23.                     }
    24.                 }
    25.         }
    26.         j++;
    27.         ch=str[j];
    28.     }
    29. }

    求二叉树的结点个数

    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. {
    2.     if (bt!=NULL)
    4.         printf("%c",bt->data);
    5.         if (bt->lchild!=NULL || bt->rchild!=NULL)
    6.         {    
    7.             printf("(");
    8.             DispBTree(bt->lchild);        /*递归处理左子树*/
    9.             if (bt->rchild!=NULL) 
    10.                 printf(",");
    11.             DispBTree(bt->rchild);        /*递归处理右子树*/
    12.             printf(")");
    13.         }
    14.     }
    15. }

    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");