bitree.cpp

数据结构 二叉树算法集合为学习数据结构的同学提供帮助 互相交流

#include<stdio.h>
#include<stdlib.h>
#define OVERRFLOW 0
#define OK 1
#define ERROR 0
#define MAXSIZE 100

typedef struct BiNode{
   char data;
   struct BiNode *lchild,*rchild;
}BiNode,*BiTree;

typedef struct SqQueue{ //循环队列结点
    BiTree *base;
	int front;
	int rear;
	int queuesize;
}SqQueue,*SqQueueptr;

typedef enum{Visit,Travel}TaskType;

typedef struct{
 BiTree ptr;
 TaskType task;
}ElemType;

typedef struct stack{
  ElemType *base;
  ElemType *top;
  int stacksize;
}Stack;

InitStack(Stack &S){
S.base=new ElemType[100];
if(!S.base) return ERROR;
S.top=S.base;
S.stacksize=MAXSIZE;
return OK;
}

StackEmpty(Stack S){
if(S.base==S.top)return OK;
else return ERROR;

}
Push(Stack &S,ElemType e){
//插入新的元素e使之成为新的栈顶元素
if(S.top>S.base+S.stacksize) return ERROR;
*S.top++=e;  
return OK; 
}

Pop(Stack &S,ElemType &e){
 if(S.top==S.base)return ERROR;
 e=*(--S.top);
 return OK;
}

InitQueue(SqQueue &Q){   //初始化循环链表
Q.base=new BiTree[MAXSIZE];
if(!Q.base)exit(0);
Q.queuesize=MAXSIZE;
Q.front=Q.rear=0;
return OK;
}

IsEmpty(SqQueue Q){    
if(Q.rear==Q.front)return OK;
else return ERROR;
}

EnQueue(SqQueue &Q,BiTree e){           //新元素入队列
//插入元素e为Q的新的队尾元素
	if((Q.rear+1)%Q.queuesize==Q.front)return ERROR;
	Q.base[Q.rear]=e;
	Q.rear=(Q.rear+1)%Q.queuesize;
	return OK;
}

DeQueue(SqQueue &Q,BiTree &e){      //出队列
if(Q.front==Q.rear)return ERROR;
e=Q.base[Q.front];
Q.front=(Q.front+1)%Q.queuesize;
return OK;
}

CreateBiTree(BiTree &T){            //创建二叉树
	char ch;
	scanf("%c",&ch);
	if(ch==' ')T=NULL;
	else{
	if(!(T=(BiNode *)malloc(sizeof(BiNode)))) exit(0);
	T->data=ch;
	CreateBiTree(T->lchild);
	CreateBiTree(T->rchild);	
	}
  return OK;
}

PrintElement(BiTree T){
 printf("%c",T->data);
 return OK;
}

PreOderTrverse(BiTree T){       //递归前序输出
  
	if(T){
	  if(PrintElement(T))
	  if(PreOderTrverse(T->lchild))
	  if(PreOderTrverse(T->rchild)) return OK;
	  return ERROR;
	}
   else return OK;
}
BackOderTrverse(BiTree T){          //递归后序输出
  
	if(T){
	  if(BackOderTrverse(T->lchild))
	  if(BackOderTrverse(T->rchild)) 
	  if(PrintElement(T))return OK;
	  return ERROR;
	}
   else return OK;

}

InOderTrverse(BiTree T){           //递归中序输出
  
	if(T){

	  if(InOderTrverse(T->lchild))
	  if(PrintElement(T))
	  if(InOderTrverse(T->rchild)) return OK;
	  return ERROR;
	}
   else return OK;

}
PreOderTraverse1(BiTree T){
Stack S;ElemType e;BiTree p;
InitStack(S);
e.ptr=T;e.task=Travel;
if(T)Push(S,e);
while(!StackEmpty(S)){
Pop(S,e);
if(e.task==Visit)PrintElement(e.ptr);
else if(e.ptr){
p=e.ptr;e.ptr=p->rchild;e.task=Travel;
Push(S,e);
e.ptr=p->lchild;
Push(S,e);
e.ptr=p;e.task=Visit;
Push(S,e);
}
}
return OK;
}

InOderTraverse1(BiTree T){      
Stack S; ElemType e;BiTree p;
InitStack(S);
e.ptr=T;e.task=Travel;
if(T)Push(S,e);
while(!StackEmpty(S)){
	Pop(S,e);
	if(e.task==Visit)PrintElement(e.ptr);
    else if(e.ptr){
	p=e.ptr;e.ptr=p->rchild;e.task=Travel;
    Push(S,e);
    e.ptr=p;e.task=Visit;
	Push(S,e);
    p=e.ptr;e.ptr=p->lchild;e.task=Travel;
	Push(S,e);
	}
}
return OK;
}

BackTraverse1(BiTree T){
Stack S; ElemType e;BiTree p;
InitStack(S);
e.ptr=T;e.task=Travel;
if(T)Push(S,e);
while(!StackEmpty(S)){
Pop(S,e);  
if (e.task==Visit) PrintElement(e.ptr);
else if(e.ptr){
 //p=e.ptr; 
 e.task=Visit;  
 Push(S,e); 
 p=e.ptr; e.task=Travel; e.ptr=p->rchild;  
 Push(S,e); // 遍历右子树
 e.ptr=p->lchild; 
 Push(S,e); // 遍历左子树
}
}
return  OK;
}

LayerTraverse(BiTree T){       //层次输出
SqQueue Q;BiTree p;//p=T;
InitQueue(Q);
if(T)EnQueue(Q,T);
while(!IsEmpty(Q)){
	DeQueue(Q,p);PrintElement(p);
    if(p->lchild)EnQueue(Q,p->lchild);
	if(p->rchild)EnQueue(Q,p->rchild);
}
return  OK;
}

BiTreeDepth(BiTree T,int &depth){       //求二叉树的深度
int Ldepth=0,Rdepth=0;
if(!T)depth=0;
else {
  BiTreeDepth(T->lchild,Ldepth);
  BiTreeDepth(T->rchild,Rdepth);
  depth=1+(Ldepth>Rdepth?Ldepth:Rdepth);
}
return OK;
}


CountFleaves(BiTree T,int &count){      //求叶子结点的数目
if(T){
	if(T->lchild==NULL&&T->rchild==NULL)
	  count++;
	  CountFleaves(T->lchild,count);
      CountFleaves(T->rchild,count);
	}
   return OK;
}

CountNodes(BiTree T,int &count2){   //总结点的数目

	if(T) {
	 count2++;
	 CountNodes(T->lchild,count2);
	 CountNodes(T->rchild,count2);
	  
	}
 
   return OK;

}

main(){           //主函数
int i;
BiTree T;
int count,count2,depth;
while(1){
count=0,count2=0;depth=0;
printf("\n\n创建二叉树-------------------------1\n");
printf("递归方法输出(前、中、后序)---------2\n");
printf("非递归方法输出(前、中、后序)-------3\n");
printf("二叉树的深度-----------------------4\n");
printf("层次输出---------------------------5\n");
printf("叶子接点数-------------------------6\n");
printf("接点总数---------------------------7\n");
printf("退出-------------------------------0\n");
scanf("%d",&i);
switch(i){
case 0: exit(0);break;
case 1: printf("\n输入二叉树的项:\n");getchar();CreateBiTree(T); break;
case 2:	printf("递归方法实现遍历:\n前序输出:\n");PreOderTrverse(T);
	    printf("\n中序输出:\n");InOderTrverse(T);
		printf("\n后序输出:\n");BackOderTrverse(T);break;
case 3: printf("非递归方法实现遍历:\n前序输出:\n");PreOderTraverse1(T);
	    printf("\n中序输出:\n");InOderTraverse1(T);
	    printf("\n后序输出:\n");BackTraverse1(T);break;
case 4: BiTreeDepth(T,depth);printf("二叉树的深度为:%d\n",depth);break;
case 5: printf("层次输出:\n");LayerTraverse(T);break;
case 6: CountFleaves(T,count);printf("叶子接点数为:%d\n",count);break;
case 7: CountNodes(T,count2); printf("接点总数为:%d\n",count2);break;
default: break;
}
}
return OK;
}