bitree.c

数据结构的基本应用

#define TElemType char
#define OK 1
#define MaxSize 50

#include <stdio.h>
#include <iostream.h>
#include <malloc.h>

typedef struct BiTNode{
  TElemType data;
  struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

int CreatBiTree(BiTree *T){
  char ch;
  scanf("%c",&ch);
    if(ch==' ') *T=NULL;
    else{
	*T=(BiTNode *)malloc(sizeof(BiTNode));
	(*T)->data=ch;
	CreatBiTree(&(*T)->lchild);
	CreatBiTree(&(*T)->rchild);

  }
 return OK;
} //CreatBiTree

//先序遍历二叉树
void Preorder(BiTNode *T){            
	if(T){
		printf("%c ",T->data);
		Preorder(T->lchild);
		Preorder(T->rchild);
	}
} //Preorder

//中序遍历二叉树
void Inorder(BiTNode *T){
	if(T){
		Inorder(T->lchild);
		printf("%c ",T->data);
		Inorder(T->rchild);
	}
}//Inorder

//后序遍历二叉树
void Postorder(BiTNode *T){
	if(T){
		Postorder(T->lchild);
		Postorder(T->rchild);
		printf("%c ",T->data);
	}
}//Postorder

//非递归中序遍历
void NInorder(BiTNode *T)
{
	BiTNode *stack[MaxSize],*p;
	int top=-1;
	p=T;
	while(p||top!=-1)
	{
		if(p)
		{
			top++;
			stack[top]=p;
			p=p->lchild;
		}                              //根节点进栈，遍历左子树
		else                           //根节点退栈，访问根节点，遍历右子树
		{
			p=stack[top];
			top--;
			printf("%c ",p->data);
			p=p->rchild;
		}
	}
}//NInorder

//非递归先序遍历
void NPreorder(BiTNode *T)
 {
	BiTNode *stack[MaxSize],*p;
	int top=-1;
	 if(T)
	 {
		 top++;
		 stack[top]=T;                  //根节点进栈
		 while(top>-1)                  //栈不为空时循环
		 {
			 p=stack[top];              //退栈并访问该节点
			 top--;
			 printf("%c ",p->data);
			 if(p->rchild)             //右孩子进栈
			 {
				 top++;
				 stack[top]=p->rchild;
			 }
			 if(p->lchild)             //左孩子进栈
			 {
				 top++;
				 stack[top]=p->lchild;
			 }
		 }                          
	 }
}//NPreorder

//非递归后序遍历
void NPostorder(BiTNode *T)
{
	BiTNode *stack[MaxSize],*p;
	int flag,top=-1;
	do
	{
		while(T)                     //所有左节点进栈
		{
			top++;
			stack[top]=T;
			T=T->lchild;
		}                              
		p=NULL;                        //p总是指向当前节点的前一个已经访问过的节点
		flag=1;                        //flag为1表示当前节点已经访问过了
		while(top!=-1 && flag)
		{
			T=stack[top];
			if(T->rchild==p)          //右子树不存在或者已经被访问过时
			{
				printf("%c ",T->data);
				top--;
				p=T;                  //调整p指针
			}
			else
			{
				T=T->rchild;
				flag=0;              //调整访问标志
			}
		}
	} while(top!=-1);
}//NPostorder

//层次遍历二叉树
void Translever(BiTNode *T)
{
	struct node
	{
		BiTNode *vec[MaxSize];
		int f,r;                     //r为队尾，f为队头
	}queue;
	BiTNode *p;
	p=T;
	queue.f=0;
	queue.r=0;                      //置队列为空队列
	if(T)
		printf("%c ", p->data);
	queue.vec[queue.r]=p;
	queue.r=queue.r+1;             //结点指针进入队列
	while(queue.f<queue.r)         //队列不空
	{
		p=queue.vec[queue.f];       //队头出队列
		queue.f=queue.f+1;
		if(p->lchild)               //输出左孩子并入队列
		{
			printf("%c ",p->lchild->data);
			queue.vec[queue.r]=p->lchild;
			queue.r=queue.r+1;
		}
		if(p->rchild)              //输出右孩子并入队列
		{
			printf("%c ",p->rchild->data);
			queue.vec[queue.r]=p->rchild;
			queue.r=queue.r+1;
		}
	}
	printf("\n");
}//Translever

//求二叉树的深度（后序）
int Depth(BiTNode *T){
	int dep,depthleft,depthright;
	if(T==NULL) dep=0;
	else {
		depthleft=Depth(T->lchild);
		depthright=Depth(T->rchild);
		dep=1+(depthleft>depthright ? depthleft:depthright);
	}
	return dep;
}//Depth

//输出二叉树
void DispTree(BiTNode *T){    
	if(T){
		printf("%c ",T->data);
		if(T->lchild||T->rchild){
			printf("(");
			DispTree(T->lchild);
			if(T->rchild) 
				printf(",");
			DispTree(T->rchild);
			   printf(")");
		}
	}
} //DispTree

main(){
  BiTree BT=NULL;
  int j,sign=1;

   printf("                ****************二叉树******************\n");
   printf("0.生成二叉树                                 1.求二叉树的深度\n");
   printf("2.递归先序遍历                               3.非递归先序遍历\n");
   printf("4.递归中序遍历                               5.非递归中序遍历\n");
   printf("6.递归后序遍历                               7.非递归后序遍历\n"); 
   printf("8.层次遍历                                   9.输出二叉树\n");
   printf("10.退出程序\n");
   while(sign){
   printf("\n请选择: ");
   scanf("%d",&j);
   getchar();
      switch(j){
      case 0:
	        printf("以先序序列建立二叉树，叶子结点用空格代替:");
            CreatBiTree(&BT); 
			printf("建立二叉树树成功!\n");
			break;
      case 1:
	       if(BT){
			   printf("二叉树的深度:");
			   printf("%d\n",Depth(BT));
		   }
		   else
		     printf("二叉树为空！\n");
		   break;
      case 2:
	       if(BT){
			   printf("递归先序遍历二叉树:");
			   Preorder(BT); 
			   printf("\n");
		   }
		   else
		     printf("二叉树为空！\n");
		   break;
      case 3:
	       if(BT){
			   printf("非递归先序遍历二叉树:");
			   NPreorder(BT); 
			   printf("\n");
		   }
		   else
		     printf("二叉树为空！\n");
		   break;
      case 4:
	       if(BT){
			   printf("递归中序遍历二叉树:");
			   Inorder(BT); 
			   printf("\n");
		   }
		   else
		     printf("二叉树为空！\n");
		   break;
      case 5:
	       if(BT){
			   printf("非递归中序遍历二叉树:");
			   NInorder(BT);  
			   printf("\n");
		   }
		   else
		     printf("二叉树为空！\n");
		   break;
      case 6:
	       if(BT){
			   printf("递归后序遍历二叉树:");
			   Postorder(BT); 
			   printf("\n");
		   }
		   else
		     printf("二叉树为空！\n");
		   break;
      case 7:
	       if(BT){
			   printf("非递归后序遍历二叉树:");
			   NPostorder(BT); 
			   printf("\n");
		   }
		   else
		     printf("二叉树为空！\n");
		   break;
      case 8:
	       if(BT){
			   printf("层次遍历二叉树:");
			   Translever(BT); 
			   printf("\n");
		   }
		   else
		     printf("二叉树为空！\n");
		   break;
      case 9:
	       if(BT){
			   printf("输出二叉树:");
			   DispTree(BT); 
			   printf("\n");
		   }
		   else
		     printf("二叉树为空！\n");
		   break;
	  
	 case 10:  sign=0;
			 break;
	 default: printf("输入错误，请重新输入!\n");
		   
	  }//switch
  }//while

}//main