sy6_2.c

数据结构实验与学习指导

/*递归建立二叉树，求二叉树的结点和叶子结点的个数、二叉树的深度，交换二叉树的左右子树sy6_2.c*/
#include <stdio.h>
#include <alloc.h>
#define MAXSIZE 20
/*int i=0;        */
typedef struct btnode
    {
    char cdata;
    struct btnode *lchild,*rchild;
    }BTNode;
    int count,deep;/* count：叶子结点个数，deep：树的深度*/
    BTNode *Create_BiTree2()
    { BTNode  *t;          char c;
      c=getchar();
      if(c=='#')   return(NULL);
     else{
             t=(BTNode *)malloc(sizeof(BTNode));
             t->cdata=c;
             t->lchild=Create_BiTree2();
             t->rchild=Create_BiTree2(); 
    }
     return(t);
  }/* Create_BiTree2 */
void Preorder2(BTNode *bt)   /* 利用栈实现前序遍历非递归算法 */
 {
    BTNode * p=bt,*s[MAXSIZE]; int top=-1;
    while(p||top>-1)
      {  if(p)                         /* 二叉树非空 */
        { printf("%c",p->cdata);       /*访问根结点，输出结点*/
          ++top ;s[top]=p;         /*根结点指针进栈*/
          p=p->lchild ;   }        /*p移向左孩子*/
        else                         /*栈非空*/
          {  p=s[top] ;--top ;     /*双亲结点指针出栈*/
             p=p->rchild ;     }    /*p移向右孩子*/
          }
    }/* Preorder2 */
void Inorder2(BTNode *bt)   /* 利用栈实现中序遍历非递归算法 */
  {
    BTNode * p=bt,*s[MAXSIZE]; int top=-1;
    while(p||top>-1)
        {  if(p)                         /* 二叉树非空 */
           { ++top ;s[top]=p;       /*根结点指针进栈*/
              p=p->lchild ;   }      /*p移向左孩子*/
           else                         /*栈非空*/
             {  p=s[top] ;
                printf("%c",p->cdata);       /*访问根结点，输出结点*/
                --top ;     /*双亲结点指针出栈*/
               p=p->rchild ;     }    /*p移向右孩子*/
           }
      }/* Inorder2 */
int Postorder2(BTNode *T)   /*非递归后序遍历二叉树*/
{  BTNode *p,s[MAXSIZE];
     int s2[MAXSIZE],top=0,mark;
     p=T;
     do
     { while(p!=NULL)
        { s[top]=*p; s2[top++]=0;  p=p->lchild; }
         if(top>0)
           { mark=s2[--top];  *p=s[top];
             if(mark==0)         /*第二次进栈*/
             { s[top]=*p;s2[top++]=1;
                p=p->rchild;
              }
            else
             { printf("%c",p->cdata);    /*输出*/
               p=NULL;  }
          } /*while(p!=NULL)*/
     }while(top>0);
    return 1;
}/* Postorder2*/
void Node_Count(BTNode *T)/*求二叉树结点数*/
{
   if(T)
       {
         count++;  
         Node_Count(T->lchild);
         Node_Count(T->rchild);
       }
   }/* Node_Count*/
void Leaf_BiTree(BTNode *T,int j)   /*求叶子结点及二叉树的深度*/
{
  if(T)
   {
     if(T->lchild==NULL && T->rchild==NULL)
       { printf("%c\n",T->cdata);
         count++;
       }
      j++;
      if(deep<j)  deep=j;
      Leaf_BiTree(T->lchild,j);
      Leaf_BiTree(T->rchild,j);
   }
}/* Leaf_BiTree */
void  Exchange(BTNode *bt)
{/*交换左右子树*/
    if(bt)
    {   BTNode *p;
         p=bt->lchild;
         bt->lchild=bt->rchild;
         bt->rchild=p;
         Exchange(bt->lchild);
         Exchange(bt->rchild);
          }
}/* Exchange */
void main()
  {
     int i=1;
     BTNode *t;
  t=Create_BiTree2();
 while(i)
  {
    printf("\n"); /*功能菜单*/
    printf("请选择操作:\n");
    printf("1:  二叉树的前序遍历\n");
    printf("2:  二叉树的中序遍历\n");
    printf("3:  二叉树的后序遍历\n");
    printf("4:  求二叉树的结点数\n");
    printf("5:  求二叉树的叶子结点及树的深度\n");
    printf("6:  二叉树左右子树的交换\n");
    printf("0:  退出程序\n");
    scanf("%d",&i);
    switch(i)
     {
      case 0: printf(" 程序退出！\n ");exit(0);
      case 1: printf("前序遍历结果:\n"); Preorder2(t);
      break;
      case 2: printf("中序遍历结果:\n"); Inorder2(t);
      break;
      case 3: printf("后序遍历结果:\n"); Postorder2(t);
           break;
      case 4: count=0;
                Node_Count(t);
                printf("二叉树结点的个数是%d",count,"\n");
               break;
      case 5: printf("叶子结点数和树的深度\n");
               deep=count=0;
               Leaf_BiTree(t,count);
               printf("树叶结点数为:%d",count);
               printf("\n树的深度为:%d",deep);
               break;
      case 6: Exchange(t);
         printf("左、右子树已交换成功!:");
         printf("\n前序遍历序列为:");Preorder2(t);
         printf("\n中序遍历序列为:");Inorder2(t);
         printf("\n后序遍历序列为:");Postorder2(t);
         break;
      default : printf("\n输入无效，请重新选择操作!\n" );break;
   }
  }
}