數據結構 - 二叉排序樹的實現

數據結構 - 二叉排序樹的實現

二叉排序樹（Binary Sort Tree）又稱二叉查找樹（Binary Search Tree），亦稱二叉搜索樹。

它或者是一棵空樹；或者是具有下列性質的二叉樹：

（1）若左子樹不空，則左子樹上所有結點的值均小於它的根結點的值；

（2）若右子樹不空，則右子樹上所有結點的值均大於它的根結點的值；

（3）左、右子樹也分別為二叉排序樹；

上機代碼：

#include 
#include 
#include 
#include 
#include  
using namespace std;

#define KeyType int 
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)< (b))
#define LQ(a,b) ((a)<=(b))
#define FALSE 0
#define TRUE 1 
#define OK 1
//#define OVERFLOW 0
#define ERROR 0
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10

typedef struct  
{
	KeyType key;                                                //關鍵字域
} ElemType;                                                                                   

typedef struct BiTNode               //定義二叉樹二叉鏈表
{
	ElemType  data;
	struct BiTNode *lchild, *rchild;
}BiTNode,*BiTree,*SElemType;

typedef struct
{
	SElemType *base;
	SElemType *top;
	int stacksize;
}SqStack;

int DestroyBiTree(BiTree &T) //銷毀樹
{
	if(T!=NULL)
	free(T);
	return 0;
}

int ClearBiTree(BiTree &T) //清空樹
{
	if(T!=NULL)
	{
		T->lchild=NULL;
		T->rchild=NULL;
		T=NULL;
	}
	return 0;
}

int SearchBST(BiTree T,KeyType key,BiTree f,BiTree &p)    //查找關鍵字,指針p返回
{
	if(!T)
	{
		p=f;
		return FALSE;
	}
	else if EQ(key,T->data.key) 
	{
		p=T;
		return TRUE;
	}
	else if LT(key,T->data.key)
		return SearchBST(T->lchild,key,T,p);
	else 
		return SearchBST(T->rchild,key,T,p);
}

int InsertBST(BiTree &T,ElemType e)   //插入節點元素
{
	BiTree s,p;
	if(!SearchBST(T,e.key,NULL,p))
	{
		s=(BiTree)malloc(sizeof(BiTNode));
		s->data=e;
		s->lchild=s->rchild=NULL;
		if(!p)
			T=s;
		else if LT(e.key,p->data.key)
			p->lchild=s;
		else 
			p->rchild=s;
		return TRUE;
	}
	else return FALSE;
}

int ShowBST(BiTree T,int nlayer)      //顯示樹形二叉排序樹
{
	int i;
	if(T==NULL)  
		return FALSE;
	ShowBST(T->rchild,nlayer+1);
	for(i=0;idata);
	ShowBST(T->lchild,nlayer+1);
	return OK;
}

int Visit(ElemType e)  //Visit函數
{
	printf("%d ",e.key);
	return OK;
}

int InitStack(SqStack &S)   //構造空棧
{
	S.base=(SElemType*)malloc(STACK_INIT_SIZE *sizeof(SElemType));
	if(!S.base) exit(OVERFLOW);
	S.top=S.base;
	S.stacksize=STACK_INIT_SIZE;
	return OK;
}//InitStack

int Push(SqStack &S, SElemType e)  //插入元素e為新棧頂
{
	if(S.top-S.base>=S.stacksize)
	{
		S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));
		if(!S.base) exit(OVERFLOW);
		S.top=S.base+S.stacksize;
		S.stacksize+=STACKINCREMENT;
	}
	*S.top++=e;
	return OK;
}//Push

int Pop(SqStack &S,SElemType &e)  //刪除棧頂，應用e返回其值
{
	if(S.top==S.base)  return ERROR;
	e=*--S.top;
	return OK;
}//Pop

int StackEmpty(SqStack S)          //判斷是否為空棧
{
	if(S.base==S.top) return TRUE;
	return FALSE;
}

int PreOrderTraverse(BiTree T,int(*Visit)(ElemType e))  //先序遍歷，運用棧
{
	SqStack S;
	BiTree p;
	InitStack(S);
	p=T;
	while(p|| !StackEmpty(S))
	{
		if(p)
		{
			Push(S,p);
			if(!Visit(p->data)) return ERROR;   
			p=p->lchild;
		}
		else
		{
			Pop(S, p);
			p=p->rchild;
		}
	}
	return OK;
}

int InOrderTraverse(BiTree T, int(*Visit)(ElemType e))  //中序遍歷，運用棧
{
	SqStack S;
	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)) return ERROR;
			p=p->rchild;
		}
	
	}
	return OK;
}

int PostOrderTraverse(BiTree T,int(*Visit)(ElemType e)) //後序遍歷，運用棧
{
	SqStack S,SS;
	BiTree p;
	InitStack(S);
	InitStack(SS);
	p=T;
	while(p|| !StackEmpty(S))
	{
		if(p)
		{
			Push(S,p);
			Push(SS,p);
			p=p->rchild;
		}
		else
		{
			if(!StackEmpty(S))
			{
				Pop(S, p);
				p=p->lchild;
			}
		}
	}
    while(!StackEmpty(SS))
    {
        Pop(SS, p);
		if(!Visit(p->data)) return ERROR;     
    }
	return OK;
}

int Delete(BiTree &p) // 三種刪除節點的操作實現
{
	BiTree q,s;
	if(!p->rchild)    //右子樹為空
	{
		q=p;
		p=p->lchild;
		free(q);
	}
	else if(!p->lchild)    //左子樹為空
	{
		q=p;
		p=p->rchild;
		free(q);
	}
	else
	{
		q=p;
		s=p->lchild;
		while(s->rchild)
		{
			q=s;
			s=s->rchild;
		}
		p->data=s->data;
		if(q!=p)
			q->rchild=s->lchild;
		else
			q->lchild=s->lchild;
		free(s);
	}
	return TRUE;
}

int DeleteBST(BiTree &T,KeyType key) //實現二叉排序樹的刪除操作
{
	if(!T)
		return FALSE;
	else
	{
		if (EQ(key,T->data.key))       //T->data.key等於key
			return Delete(T);
		else if (LT(key,T->data.key))   //T->data.key是否小於key
			return DeleteBST(T->lchild,key);
		else 
			return DeleteBST(T->rchild,key);
	}
	return 0;
}

int main()
{
	int i,nlayer;
	ElemType k,d;
    BiTree  BT,p;
	BT=NULL;
	p=NULL;
	nlayer=1;
	printf("請輸入插入的二叉樹節點的數值（輸入數字0結束節點賦值）:\n");
	scanf("%d",&k.key);
	for(i=0;k.key!=NULL;i++)
	{		
		if(!SearchBST(BT,k.key,NULL,p))         //查找關鍵字
		{
			InsertBST(BT,k);                    //二叉樹節點數值插入
			scanf("%d",&k.key);
		}
		else
		{
			printf("輸入數據重復！\n");
			return 0;
		}
	}
	printf("二叉排序樹樹形輸出為：\n");
	ShowBST(BT,nlayer);                        //樹形顯示二叉排序樹
	printf("請輸入刪除的數據：");
	scanf("%d",&d.key);
	DeleteBST(BT,d.key);                       //刪除關鍵字
	ShowBST(BT,nlayer);
	printf("先序遍歷為：");                    //先序遍歷、中序遍歷、後序遍歷
	PreOrderTraverse(BT,Visit);
	printf("\n中序遍歷為：");
	InOrderTraverse(BT, Visit);
	printf("\n後序遍歷為：");
	PostOrderTraverse(BT,Visit); 
	printf("\n清空該二叉排序樹.\n");            //清空二叉樹
	ClearBiTree(BT);
	ShowBST(BT,nlayer);
	printf("\n銷毀該二叉排序樹.\n");	        //銷毀二叉樹
	ClearBiTree(BT);
	
	return 0;
}