bitree.c

ADT抽象数据类型二叉树基本操作 基本上实现了《数据结构（C语言版）》严蔚敏著 中描述的所有二叉树基本操作 Dev C++ 编译

#include<stdio.h>
#include<stdlib.h>     
#include<malloc.h>
#include<conio.h>   
#define MaxSize 50
#define OK    1
#define ERROR 0
#define TRUE  1
#define FALSE 0

/*以下为二叉树存储结构定义*/

typedef char TElemType; 
typedef struct BiTNode{
 TElemType  data;
 struct BiTNode  *lchild,*rchild;//左右孩子指针 
}BiTNode,*BiTree;

/*---------------------以下为二叉树基本操作-----------------------------*/

void InitBiTree(struct BiTNode* *T)//构造空二叉树
{ 
 T=NULL; 
 return;
}//InitBiTree

void DestroyBiTree(struct BiTNode *T) //销毁二叉树
{
 free(T);
 return;
}//DestroyBiTree

void CreatBiTNode(struct BiTNode* *T, char *str) //构造二叉树 
{
 BiTNode *p;
 BiTNode *s[MaxSize];/*括号堆栈区*/ 
 int top = -1; /* 栈顶标志，初值为-1,表示空栈 */
 int k; 
 int i=0; 
 *T=NULL; /* 初始化二叉树 */
 while(str[i]!='\0'){
     switch(str[i]){
         case ' ':
           break;  /* 对空格不作任何处理 */
         case '(':
           top++;
           s[top]=p;
           k = 1;
           break;
         case ')':
           top--;
           break;
         case ',':
           k = 2;
           break;
         default:
           p = (BiTNode*)malloc(sizeof(BiTNode));  /*为结点申请储存空间*/
           p->data=str[i];
           p->lchild = p->rchild = NULL;
           
           if(*T==NULL) *T=p;          /*结点为根结点*/
           else{
               if( k == 1) s[top]->lchild = p; /*当k=1时处理左孩子，当k=2时应处理右孩子*/
               if( k == 2) s[top]->rchild = p;
           }
      }//end switch
    i++;  
 }//end while 
 printf("\n\n构造二叉树完毕\n");
 getchar();
 return;
}
 
void ClearBiTree(struct BiTNode *T)//清空二叉树
{
 if(T){
   ClearBiTree(T->lchild);    
   ClearBiTree(T->rchild);    
   T->data='#';    
 }

}//ClearBiTree


int BiTreeEmpty(struct BiTNode *T)//二叉树判空
{
 if(T->data=='#')
  return TRUE;
 else
  return FALSE; 
}//BiTreeEmpty

int BiTreeDepth(struct BiTNode *T)//求二叉树深度
{
 int ld,rd;
 if(T==NULL)return 0;/*空树*/
 else{
  ld=BiTreeDepth(T->lchild); /*选取左右子树深度最大值*/
  rd=BiTreeDepth(T->rchild); 
  if(ld>=rd)
   return ld+1;
  else
   return rd+1;
 }
 return 1;/*只有根结点*/
}//BiTreeDepth

void Root(struct BiTNode *T)//求二叉树根结点
{
  if(T)
    printf("\n该二叉树根结点为:%c\n",T->data); 
}//Root                                                                               ///////以上显示正常////// 


BiTNode *Value(struct BiTNode *T,TElemType e)//返回值为e的结点指针                             
{      
 BiTNode *p;
 if(T==NULL)    
   return NULL;
 else if(T->data==e)     
   return T;
 else{     
  p=Value(T->lchild,e);
  if(p!=NULL)
    return p;
  else    
    return Value(T->rchild,e);
 }
}//*FindNode


BiTNode *Parent(struct BiTNode *T,TElemType e)//若e是T的非根结点，则返输出其双亲，否则返回"空"。
{
     
 if(T==NULL)
  return NULL;
 if(T->lchild!=NULL&&T->lchild->data==e){ 
    printf("\n该结点的双亲应为:%c\n",T->data);
    // return T;
   if(T->rchild!=NULL) 
     printf("\n该结点的右兄弟为:%c\n",T->rchild->data);
    else
     printf("\n无右兄弟\n"); 
 }    
 else if(T->rchild!=NULL&&T->rchild->data==e){ 
    printf("\n该结点双亲为:%c\n",T->data);
   // return T;
   if(T->lchild!=NULL) 
     printf("\n该结点的左兄弟为:%c\n",T->lchild->data);
    else
     printf("\n无左兄弟\n");
 }   
 Parent(T->lchild,e);
 Parent(T->rchild,e);
}//Parent


void RightChild(struct BiTNode *T,TElemType e)//返回右孩子
{
 BiTNode *p;
 p=Value(T,e);  
 if(p->rchild!=NULL)
  printf("\n该结点的右孩子为:%c\n",p->rchild->data);
 else
   printf("\n该结点的右孩子为空\n");
}//rightChild

char LeftChild(struct BiTNode *T,char e)//返回左孩子/                            
{
 BiTNode *p;
 p=Value(T,e);  
 if(p->lchild!=NULL)
  printf("\n该结点的左孩子为:%c\n",p->lchild->data);
 else
   printf("\n该结点的左孩子为空\n");
}//LeftChild

void DisplayBiTree(struct BiTNode *T)//先序输出显示二叉树括号表示形式 
{
 if(T){
   printf("%c", T->data);  /* 输出根结点的值 */ 
   if(T->lchild||T->rchild){
     printf("(");
     DisplayBiTree(T->lchild);
     if(T->rchild) printf(",");/*若右孩子存在，则先输出“,”*/ 
     DisplayBiTree(T->rchild);
     printf(")");
   } //end if  
 }//end if
 return;
}//DisplayBiTree

void InsertChild(struct BiTNode *T,struct BiTNode *p,int LR,struct BiTNode *c)
//在p指向结点插入c为左或右子树， T中原子树则成为c左或右子树
{
 switch(LR){
    case(0):{
             if(p->lchild==NULL)/*p左子树空*/
                p->lchild=c;
             else{
                c->rchild=p->lchild;
                p->lchild=c;
             }
             break;
    }
    case(1):{
             if(p->rchild==NULL) /*p右子树空*/
                p->rchild=c;
             else{
                c->rchild=p->rchild;
                p->rchild=c;
             }
             break;
    }
    default:break;
 }//switch
}//InsertChild

void DeleteChild(struct BiTNode *T,struct BiTNode *p,int LR)
//删除p指向T中某结点，LR为0删除做子树，LR为1删除右子树
{
  switch(LR){
    case(0):{p->lchild=NULL;break;}
    case(1):{p->rchild=NULL;break;}
    default:break;
  }//switch
}//DeleteChild


void PreOrderTraverse(struct BiTNode *T)//先序遍历
{
 if(T){
   printf(" %c",T->data);
   PreOrderTraverse(T->lchild);
   PreOrderTraverse(T->rchild);  
 }  
 return ;
}//PreOrderTraverse

void InOrderTraverse(struct BiTNode *T)//中序遍历
{
 if(T){ 
  InOrderTraverse(T->lchild);
  printf(" %c",T->data);
  InOrderTraverse(T->rchild); 
 }
 return ; 
}//InOrderTraverse

void PostOrderTraverse(struct BiTNode *T)//后序遍历
{
 if(T){ 
   PostOrderTraverse(T->lchild); 
   PostOrderTraverse(T->rchild);
   printf(" %c",T->data); 
 }
 return ; 
}//InOrderTraverse

void levelOrderTraverse(struct BiTNode *T)//层次遍历  
{
 BiTNode *p;
 BiTNode *q[MaxSize];
 int front=0, rear=0;
 
 if(T){               /* 根结点进队 */
   rear=(rear+1)%MaxSize;   
    q[rear]=T;
 }
 while(front!=rear){  /* 队列非空 */
    front=(front+1)%MaxSize; 
    p = q[front];
    printf(" %c", p->data);

    if(p->lchild){  /* 左孩子结点指针进队 */
       rear=(rear+1)%MaxSize;
       q[rear]=p->lchild;
    }
 
    if(p->rchild){  /* 右孩子结点指针进队 */
       rear=(rear+1)%MaxSize;
       q[rear]=p->rchild;
    }
 }//end while
 return;
}//levelOrderTraverse

/*-----------------------------以下为主函数-----------------------------------*/ 

main(){
    BiTNode *T;  
    int num;    /*用于查找第N个结点*/
    char search; /*用于查找结点的双亲，孩子，兄弟*/ 
    char c;/*用于作出选择何种操作*/
 
 START:
   
  system("cls"); /*清屏*/
  printf("\n\n\n"); 
  printf("\n               -------====欢迎使用二叉树ADT抽象数据类型演示程序====--------              \n");
  printf("                                                      \n");
  printf("                                该程序实现了以下基本操作：\n");
  printf("\n                              1. 二叉树的输入\n");
  printf("\n                              2. 二叉树的前序构造与展示 \n");     
  printf("\n                              3. 二叉树的前中后序以及层次遍历    \n");     
  printf("\n                              4. 二叉树的深度和根结点探寻    \n");     
  printf("\n                              5. 搜索结点并回显该结点所有信息    \n");     
  printf("\n                              6. 销毁与判空二叉树   \n"); 
  printf("\n                                                            \n");
  printf("\n               -----------Copyright @ 张林海 计算机科学与技术7班------------\n\n");
  printf("\n\n\n                               按(Q)键退出程序，按任意键继续... "); 
  c=getch();
  if(c=='q'||c=='Q')
   exit(1);
  
  system("cls"); /*清屏*/
    /*-------------------------输入二叉树-----------------------------*/   
    char str[MaxSize]={' '},ch;
    char str1[MaxSize]="a(b,d(e(f,g),h(#,i)))";
    int count=0; 
    
    void print(){   //此为手动输入二叉树函数                       
       int i;  
       printf("\n\n用括号表示法输入二叉树(以'#'结尾):");  
       i=0;
        while(scanf("%c",&ch)!=EOF){
		    if(ch=='#')break;
            str[i++]=ch;
            count++;
            if(count>=MaxSize){printf("error\n");return;}
        } 
    }//print
    
    void howto(){   //此为输入方法选择函数 
       printf("\n请选择初始化方式：1.手动输入二叉树 2.使用现有二叉树   ");
       c=getch();
       switch(c){
              case '1' :   print();                          
                           CreatBiTNode(&T,str);/*构造二叉树*/
                           break;
              
              case '2' :   CreatBiTNode(&T,str1);/*构造二叉树*/
                           break;
            
              default  :   printf("\n\n输入错误，请重新输入！\n");
                           howto();
                           break;
      }  
    }//howto
    
    howto();

//	getchar();
//    getchar();
	/*-----------------------二叉树基本操作----------------------------*/
	
    /*在howto()函数中，二叉树构造已完成*/ 

	printf("原始二叉树为:");
	DisplayBiTree(T);
	printf("\n\n");
    printf("前序遍历：");  /* 先序遍历 */ 
	PreOrderTraverse(T);
    printf("\n先序遍历完毕\n\n");
    printf("中序遍历：");  /* 中序遍历 */ 
	InOrderTraverse(T);
	printf("\n中序遍历完毕\n\n");
    printf("后序遍历：");  /* 后序遍历 */ 
	PostOrderTraverse(T);
	printf("\n后序遍历完毕\n\n");
	printf("层次遍历：");  /* 层次遍历 */ 
	levelOrderTraverse(T);
	printf("\n层次遍历完毕\n\n");
	printf("该二叉树深度为：%d\n",BiTreeDepth(T));  /*深度*/ 
	Root(T);  /*查找显示二叉树根结点*/ 
	
    printf("\n请输入一个结点的值以便查找其家族信息："); /*查找并显示输入结点的双亲，孩子，兄弟*/
    scanf("%c",&search);
    Parent(T,search);   /*查找双亲 兄弟*/
    LeftChild(T,search); /*查找左孩子*/
    RightChild(T,search);  /*查找右孩子*/
    
    void clear(){           //此为清空二叉树指令函数
      printf("\n请选择，是否清空该二叉树：1.是 2.否   ");
      c=getch();
      switch(c){
              case '1' :   ClearBiTree(T)   ;break;/*清空二叉树*/
              case '2' :                    ;break;
              default  :printf("\n\n输入错误，请重新输入！\n");clear();break;
      }
    }//clear
    
    clear(); /*调用二叉树是否清空指令*/
    
    if(BiTreeEmpty(T))  /*二叉树判空*/
      printf("\n\n判空完毕，二叉树已经清空\n");
    else
      printf("\n\n判空完毕，二叉树没有被清空\n");
    printf("\n按任意键返回主界面...");   
	getchar();
	getchar();	
    goto START;

	
}