实验5.cpp

实现二叉排序树的各种算法

#include "iostream"
#include "stdlib.h"
#include "stdio.h" 
#include "malloc.h"
#define STACK_INIT_SIZE 5
#define STACKINCREMENT 1
#define N 100
using namespace std;
typedef struct BiTNode{//定义二叉树
	int data;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
BiTree T;
typedef struct {//定义栈
	BiTree *base;
	BiTree *top;
	int stacksize;
}SqStack;
SqStack S;
typedef struct{//定义队列
	BiTree *base;
	int front;
	int rear;
}SqQueue;
SqQueue Q;
int bb=0;
int InitQueue(SqQueue &Q){//建立循环队列
	Q.base=(BiTree *)malloc(N*sizeof(BiTNode));
	if(!Q.base){
		cout<<"error"<<endl;
		exit(0);
	}
	Q.front=Q.rear=0;
	return 1;
}
int EnQueue(SqQueue &Q,BiTree e){//元素入队
	if((Q.rear+1)%N==Q.front){
		cout<<"error"<<endl;
		exit(0);
	}
	Q.base[Q.rear]=e;
	Q.rear=(Q.rear+1)%N;
	return 1;
}
int DeQueue(SqQueue &Q,BiTree &e){//元素出队
	if(Q.front==Q.rear){
		cout<<"error"<<endl;
		exit(0);
	}
	e=Q.base[Q.front];
	Q.front=(Q.front+1)%N;
	return 1;
}
int EmptyQueue(SqQueue Q){//判断队列是否为空
	if(Q.front==Q.rear) return 1;
	else return 0;
}
int InitStack(SqStack &S){//建立空桟
	S.base=(BiTree *)malloc(STACK_INIT_SIZE*sizeof(BiTNode));
	if(!S.base){
		cout<<"error"<<endl;
		exit(0);
	}
	S.top=S.base;
	S.stacksize=STACK_INIT_SIZE;
	return 1;
}
int Push(SqStack &S,BiTree e){//元素入栈
	if(S.top-S.base>=S.stacksize)
	{
		S.base=(BiTree *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(BiTNode));
		if(!S.base){
			cout<<"error"<<endl;
			exit(0);
		}
		S.top=S.base+S.stacksize;
		S.stacksize+=STACKINCREMENT;
	}
	*S.top++=e;
	return 1;
}
int Pop(SqStack &S,BiTree &e){//元素出栈
	if(S.top==S.base){
		cout<<"error"<<endl;
		exit(0);
	}
	e=*--S.top;
	return 1;
}
int StackEmpty(SqStack &S){//判断栈是否空
	if(S.top==S.base) return 1;
	else return 0;
}
BiTree CreatTree(){//建立二叉排序列叉树并插入结点
    BiTNode *p,*q;
    int x,i,n,j;
    T=NULL;
    cout<<"你想输入多少个数:";
    cin>>n;
	cout<<"这些数是:";
    for(j=0;j<n;j++){
		cin>>x;
		q=(BiTNode *)malloc(sizeof(BiTNode));
        q->data=x;
        q->lchild=NULL;
        q->rchild=NULL;
	    if(T==NULL) T=q;
        else{  
			p=T;
		    i=1;
		    while(i){
				if(x<p->data){
					if(p->lchild!=NULL) p=p->lchild;
					else{
						p->lchild=q;
						i=0;
					}
				}
				else{
					if(p->rchild!=NULL) p=p->rchild;
					else{
						p->rchild=q;
						i=0;
					}
				}
			}
		}
	}
	return(T);
}
int Visit(int e){//输出函数
	cout<<e;
	return 1;
}
int PreOrderTraverse(BiTree T){//前序遍历二叉树
	if(T){
		if(Visit(T->data))
			if(PreOrderTraverse(T->lchild))
				if(PreOrderTraverse(T->rchild)) return 1;
		return 0;
		}
	else return 1;
}
int InOrderTraverse1(BiTree T){//中序递归遍历二叉树
	if(T){
		InOrderTraverse1(T->lchild);
		Visit(T->data);
		InOrderTraverse1(T->rchild);
	}
	return 1;
}
int InOrderTraverse2(BiTree T){ //中序非递归遍历二叉树
	BiTree p;
	InitStack(S);
	p=T;
	while(p||!StackEmpty(S)){
    if(p){
		Push(S,p);
		p=p->lchild; 
	}
    else {
		Pop(S,p);  
		if(!Visit(p->data)){
			cout<<"error"<<endl;
			exit(0);
		}
		p=p->rchild;
    }
  }
  return 1;
} 
int PostOrderTraverse(BiTree T){//后序遍历
	if(T){
		PostOrderTraverse(T->lchild);
        PostOrderTraverse(T->rchild);
        Visit(T->data);
	}
	return 1;
}
int ccbl(BiTree T){//层次遍历
	BiTree p;
	InitQueue(Q);
    p=T;
	EnQueue(Q,p);
	while(!EmptyQueue(Q)){
		DeQueue(Q,p);
		Visit(p->data);
		if(p->lchild!=NULL) EnQueue(Q,p->lchild);
		if(p->rchild!=NULL) EnQueue(Q,p->rchild);
	}
	return 1;
}
int search(BiTree T){//搜查关键字
	int b,c=0;
	BiTree p;
	cout<<"请输入关键字:";
	cin>>b;
	InitQueue(Q);
    p=T;
	EnQueue(Q,p);
	while(!EmptyQueue(Q)){
		DeQueue(Q,p);
		if(b==p->data){
			cout<<"该关键字存在"<<endl;
            c=1;
		}
		if(p->lchild!=NULL) EnQueue(Q,p->lchild);
		if(p->rchild!=NULL) EnQueue(Q,p->rchild);
	}
	if(c==0) cout<<"该关键字不存在"<<endl;
	return 1;
}
int leaf(BiTree T){//计算叶子结点
	BiTree p;
	int b=0;
	InitQueue(Q);
    p=T;
	EnQueue(Q,p);
	while(!EmptyQueue(Q)){
		DeQueue(Q,p);
		if(p->lchild==NULL&&p->rchild==NULL) b++; 
		if(p->lchild!=NULL) EnQueue(Q,p->lchild);
		if(p->rchild!=NULL) EnQueue(Q,p->rchild);
	}
	cout<<"叶子结点数为:";
	cout<<b<<endl;
	b=0;
	return 1;
}
int depth(BiTree T){//求深度
	if(T==NULL) return 0;
	int l=depth(T->lchild);
	int r=depth(T->rchild);
	return (l>r)?l+1:r+1; 
}
int change(BiTree T){//交换左右子树
	BiTree t;
	if(T){
	change(T->lchild);
    change(T->rchild);
    t=T->lchild;
	T->lchild=T->rchild;
	T->rchild=t;
	}
	return 1;
}
int Tstructure(BiTree T,int bb){//横向输出树型结构,头结点位于左
	int n;
	if(T){
		bb+=6;//空格计数器
		Tstructure(T->rchild,bb);
        for(n=0;n<bb;n++) cout<<" ";
		printf("%10d\n",T->data);
        Tstructure(T->lchild,bb);
	}
	return 1;
}
void main(){
	int a,b;
	while(1){
		cout<<"请选择:"<<endl;
        cout<<"1.建二叉排序树并插入结点"<<endl;
        cout<<"2.前序遍历"<<endl;
		cout<<"3.中序递归遍历"<<endl;
		cout<<"4.中序非递归遍历"<<endl;
		cout<<"5.后序遍历"<<endl;
		cout<<"6.层次遍历"<<endl;
		cout<<"7.查找关键字"<<endl;
		cout<<"8.交换左右子树"<<endl;
		cout<<"9.求二叉树深度"<<endl;
		cout<<"10.叶子结点数"<<endl;
		cout<<"11.输出树型结构"<<endl;
		cout<<"12.退出"<<endl;
		cin>>a;
		switch (a){
		case 1: CreatTree(); break;
		case 2: PreOrderTraverse(T); break;
		case 3: InOrderTraverse1(T); break;
		case 4: InOrderTraverse2(T); break;
		case 5: PostOrderTraverse(T); break;
		case 6: ccbl(T); break;
		case 7: search(T); break;
		case 8: change(T); break;
		case 9: b=depth(T); cout<<"该树深度为:"<<b<<endl; break;
		case 10: leaf(T); break;
		case 11: Tstructure(T,bb); break;
		case 12:exit(0); break;
		}
	}
}