實現(xiàn)平衡二叉排序樹的各種算法代碼 一

1、實現(xiàn)平衡二叉排序樹的各種算法代碼 一 /* 實現(xiàn)平衡二叉排序樹的各種算法一、分析題目要求用函數(shù)實現(xiàn)如下平衡二叉排序樹算法,:（1） 插入新結點 （2） 前序、中序、后序遍歷二叉樹 （遞歸）（3） 前序、中序、后序遍歷的非遞歸算法 （4） 層次遍歷二叉樹 （5） 在二叉樹中查找給定關鍵字(函數(shù)返回值為成功1,失敗0) （6） 交換各結點的左右子樹 （7） 求二叉樹的深度 （8） 葉子結點數(shù)（9） 刪除某結點為了完成以上的各項操作，首先應該用函數(shù)建一棵平衡二叉排序樹，輸入形式是首先輸入要建的二叉樹的結點數(shù)，然后依次輸入各個結點的值。在實現(xiàn)插入新結點的函數(shù)時，需要一個向一棵二叉樹插入新結點的函數(shù)?？?/p>

2、用遞歸算法寫出平衡二叉樹的前序，中序，后序遍歷的函數(shù)。在寫平衡二叉樹的前，中，后序遍歷的非遞歸算法時要用到棧結構的知識，運用棧結構來存儲平衡二叉樹結點的指針。在層次遍歷二叉樹時需要用到隊列結構，運用隊列結構的先進先出來存儲二叉樹的結點指針。在遍歷二叉樹的結點時需要一個訪問結點數(shù)據(jù)的函數(shù)。二叉樹是一棵排序樹，所以二叉樹的查找可以運用其有序的性質，查找的方式和建樹的方式相似。交換二叉樹各結點的左右子樹時，可以用先序遍歷遞歸的方式從根結點向下遞歸，每次訪問結點時就需將各結點的左右孩子的指針調換，并對該結點的平衡因子作相應的處理。示二叉樹的深度時，可用遞歸的方式訪問結點的左右子樹，并記錄下左右子樹的深

3、度，最后返回左右子樹中較深的深度的值即可?？梢杂靡淮伪闅v的方式遍歷二叉樹，記錄每一個經過的結點，若結點存在且左右孩子都為空，則該結點為葉子結點。刪除二叉樹的某個結點時，首先要寫一個函數(shù)，用遞歸查找的方式找到相應的結點，該函數(shù)還要有調整二叉樹平衡的作用，因為若刪除結點使得二叉樹深度減少而不平衡，需要調整二叉樹的平衡，若該結點不存在則返回ERROR,，若存在該結點，則應該再寫一個函數(shù)來刪除該結點，在刪除之前還要判斷該結點是只有左子樹還是只有右子樹還是左右子樹都有的情況：若只有左或是只有右子樹，則只需刪除該結點，并回溯調整二叉樹的平衡；若該結點的左右子樹都有，則應該用另一個函數(shù)遞歸找到該結點的直接“

4、后繼”，并從該“后繼”開始回溯調整二叉樹的平衡。*/#include<stdio.h>#include<stdlib.h>#include<malloc.h>#define OK 1#define ERROR 0#define LH 1#define EH 0#define RH -1#define EQ(a,b) (a)=(b)#define LT(a,b) (a)<(b)#define LQ(a,b) (a)<=(b)#define STACK_INIT_SIZE 100 / 棧 #define STACKINCREMENT 10 / 棧 #

5、defi ne MAXQSIZE 100 /隊列 #define ElemType int #define Status int #define TRUE 1#define FALSE 0#define Boolean bool/- 結構體 typedef struct BSTNode/平衡二叉樹結構ElemType data;int bf;struct BSTNode *lchild,*rchild;BSTNode,*BSTree;typedef BSTree SElemType; /棧 typedef BSTree QElemType; /隊列 typedef struct /隊列的結構體

6、QElemType *base;int front;int rear;SqQueue;typedef struct SqStack /棧的結構體 SElemType *base;SElemType *top;int stacksize;SqStack;/- 函數(shù)列表/隊列Status InitQueue(SqQueue &Q); /初始化隊列Status EnQueue(SqQueue &Q,QElemType e); /進隊列Status DeQueue(SqQueue &Q,QElemType &e); /出隊列Status GetHead(SqQueue

7、Q,QElemType &e); /獲隊列首 int QueueLength(SqQueue Q); /隊列長度Status QueueTraverse(SqQueue Q); /遍歷隊列/棧 Status InitStack(SqStack &S); /初始化棧 Status Push(SqStack &S,SElemType e); /進棧Status Pop(SqStack &S,SElemType &e); /出棧 Status GetTop(SqStack S,SElemType &e); /獲棧頂 int StackLength(Sq

8、Stack S); /棧的長度 Status StackEmpty(SqStack S); /判?？誗tatus StackTraverse(SqStack S); /棧的遍歷 /平衡二叉樹void R_Rotate(BSTree &p); /右旇void L_Rotate(BSTree &p); /左旇 Status InsertAVL(BSTree &T,ElemType e,Boolean &taller);/平衡二叉樹結點插void LeftBalance(BSTree &T); /左平衡 void RigthBalance(BSTree &am

9、p;T); /右平衡 Status CreateBST(BSTree &T,int n); /建樹 Status Visit(ElemType e); /訪問 Status PreOrderTraverse(BSTree T); /前序遍歷Status InOrderTraverse(BSTree T); /中序遍歷Status PostOrderTraverse(BSTree T); /后序遍歷 Status preOrderIter(BSTree T); /前序非遞歸遍歷Status inOrderIter(BSTree T); /中序非遞歸遍歷Status postOrderIt

10、er(BSTree T); /后序非遞歸遍歷 Status FindBST(BSTree T,ElemType key,int &n);/在二叉樹中查找關鍵詞 Status OverTraverse(BSTree &T); /層次遍歷 Status OverChang(BSTree &T); /交換左右子樹int BSTDeep(BSTree T); /求樹的深度Status Sum(BSTree T,int &n); /求葉子結點數(shù) Status DeleteBST(BSTree &T,int key,bool &taller);/刪除結點 S

11、tatus Delete(BSTree &p,bool &taller);Status Delete2(BSTree &p,bool taller,ElemType &f);void MU(); /選擇菜單 /-/-初始化隊列Status InitQueue(SqQueue &Q)Q.base=(QElemT ype*)malloc(MAXQSIZE*sizeof(QElemType);if(!Q.base)return ERROR;Q.front=Q.rear=0;return OK;/-進隊列Status EnQueue(SqQueue &Q

12、,QElemType e)if(Q.rear+1)%MAXQSIZE=Q.front)return ERROR;Q.baseQ.rear=e;Q.rear=(Q.rear+1)%MAXQSIZE;return OK;/-出隊列Status DeQueue(SqQueue &Q,QElemType &e)if(Q.front=Q.rear)return ERROR;e=Q.baseQ.front;Q.front=(Q.front+1)%MAXQSIZE;return OK;/-獲隊列首 Status GetHead(SqQueue Q,QElemType &e)if(Q.

13、front=Q.rear)return ERROR;e=Q.baseQ.front;return OK;/-隊列長度int QueueLength(SqQueue Q)return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;/-遍歷隊列Status QueueTraverse(SqQueue Q)int i;i=Q.front;if(Q.front=Q.rear)printf("The Queue is Empty!");elseprintf("The Queue is:");while(i!=Q.rear)printf(&q

14、uot;% d",Q.basei);i=i+1;printf("n");return OK;/-/-初始化棧 Status InitStack(SqStack &S)S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!S.base)return ERROR;S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;/-進棧 Status Push(SqStack &S,SElemType e)if(S.top-S.base>

15、=S.stacksize)S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType);if(S.base)return ERROR;S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;return OK;/-出棧 Status Pop(SqStack &S,SElemType &e)if(S.top=S.base)return ERROR;e=*-S.top;return OK;/-獲棧頂 Status

16、GetTop(SqStack S,SElemType &e)if(S.top=S.base)return ERROR;e=*(S.top-1);return OK;/-棧的長度 int StackLength(SqStack S)int i=0;while(S.top!=S.base)i+;S.top-;return i;/-判?？誗tatus StackEmpty(SqStack S) if(S.top=S.base) return 1;else return 0;/-棧的遍歷 Status StackTraverse(SqStack S)SElemType *p=(SElemTyp

17、e*)malloc(sizeof(SElemType);p=S.top;if(S.top=S.base)printf("The Stack is Empty!");elseprintf("The Stack is:");p-;S.base-;while(p!=S.base)printf("% d",*p);p-;printf("n");return OK;/-/-右旇 void R_Rotate(BSTree &p)BSTree lc;lc=p->lchild;p->lchild=lc->

18、rchild;lc- >rchild=p;p=lc;/-左旇 void L_Rotate(BSTree &p) BSTree rc;rc=p->rchild;p->rchild=rc->lchild;rc->lchild=p;p=rc;/-平衡二叉樹結點插入 Status InsertAVL(BSTree &T,ElemType e,Boolean &taller)if(!T)T=(BSTree)malloc(sizeof(BSTNode);T->data=e;T->lchild=T->rchild=NULL;T->

19、bf=EH;taller=TRUE;else if(EQ(e,T->data) taller=FALSE;return 0;/已經有結點了 if(LT(e,T->data) if(!InsertAVL(T->lchild,e,taller) return 0;/左子樹的深度增加 if(taller)switch(T->bf)case LH:LeftBalance(T);taller=FALSE;break;case EH:T->bf=LH;taller=TRUE;break;case RH:T->bf=EH;taller=FALSE;break; else

20、if(!InsertAVL(T->rchild,e,taller) return 0;/右子樹的深度增加 if(taller)switch(T->bf)case LH:T->bf=EH;taller=FALSE;break;case EH:T->bf=RH;taller=TRUE;break;case RH:RigthBalance(T);taller=FALSE;break; return 1;/-左平衡 void LeftBalance(BSTree &T)BSTree c,rd;c=T->lchild;switch(c->bf)case LH:

21、T->bf=c->bf=EH;R_Rotate(T);break;case RH:rd=c->rchild;switch(rd->bf)case LH:T->bf=RH; c->bf=EH;break;case EH:T->bf=c->bf=EH; break;case RH:T->bf=EH;c->bf=LH; break;rd->bf=EH;L_Rotate(T->lchild);R_Rotate(T);/-右平衡 void RigthBalance(BSTree &T)BSTree rd,lc;rd=T-&g

22、t;rchild;switch(rd->bf)case RH:T->bf=rd->bf=EH;L_Rotate(T);break;case LH:lc=rd->lchild;switch(lc->bf)case RH:T->bf=LH;rd->bf=EH;break;case EH:T->bf=rd->bf=EH;break;case LH:T->bf=EH;rd->bf=RH;break;lc->bf=EH;R_Rotate(T->rchild);L_Rotate(T); /-建樹 Status CreateBST

23、(BSTree &T,int n)T=NULL;bool taller=FALSE;int k,i;for(i=1;i<=n;i+)scanf("%d",&k);InsertAVL(T,k,taller);return OK; /-訪問 Status Visit(ElemType e)printf("%d ",e);return OK;/- 前序遍歷 Status PreOrderTraverse(BSTree T)if(T)if(Visit(T->data)if(PreOrderTraverse(T->lchild)i

24、f(PreOrderTraverse(T->rchild)return OK;return ERROR;elsereturn OK;/-前序非遞歸遍歷 Status preOrderIter(BSTree T) BSTree p,q;p=T; SqStack S; if (T = NULL) return ERROR;InitStack(S);Push(S,p); while (!StackEmpty(S) GetTop(S,p);Visit(p->data); Pop(S,p); if (p->rchild != NULL) Push(S,p->rchild); if

25、 (p->lchild != NULL) Push(S,p->lchild); printf("n"); return OK; /-中序遍歷 Status InOrderTraverse(BSTree T)if(T)if(InOrderTraverse(T->lchild)if(Visit(T->data)if(InOrderTraverse(T->rchild)return OK;return ERROR;elsereturn OK;/-中序非遞歸遍歷 Status inOrderIter(BSTree T) BSTree p;p=T; Sq

26、Stack S; if (T = NULL) return ERROR;InitStack(S);while (p!= NULL | !StackEmpty(S) if (p!= NULL) Push(S,p); p=p->lchild; else GetTop(S,p); Visit(p->data); Pop(S,p); p=p->rchild; printf("n"); return OK; /- -后序遍歷 Status PostOrderTraverse(BSTree T)if(T)if(PostOrderTraverse(T->lchil

27、d)if(PostOrderTraverse(T->rchild)if(Visit(T->data)return OK;return ERROR;elsereturn OK;/-后序非遞歸遍歷 Status postOrderIter(BSTree T) if (!T) return 0; BSTree p,q;p=T; SqStack S1,S2; InitStack(S1);InitStack(S2);Push(S1,p); while (!StackEmpty(S1) GetTop(S1,q); Push(S2,q); Pop(S1,p); if (q->lchild)

28、 Push(S1,q->lchild); if (q->rchild) Push(S1,q->rchild); while (!StackEmpty(S2) GetTop(S2,q);Visit(q->data);Pop(S2,q); printf("n");return OK; /-在二叉樹中查找關鍵詞 Status FindBST(BSTree T,ElemType key,int &n)if(!T) return ERROR;if(EQ(key,T->data) n=1;return OK;else if(LT(key,T->

29、;data)FindBST( T->lchild, key,n);else FindBST( T->rchild,key,n);return OK;/-層次遍歷 Status OverTraverse(BSTree &T)BSTree p;SqQueue Q;if(!InitQueue(Q) return ERROR;p=T;if(!T) return ERROR;EnQueue(Q,p);while(QueueLength(Q)DeQueue(Q,p);Visit(p->data);if(p->lchild) EnQueue(Q,p->lchild);i

30、f(p->rchild) EnQueue(Q,p->rchild);return OK;/-交換左右子樹 Status OverChang(BSTree &T)BSTree q;if(T)q=T->lchild;T->lchild=T->rchild;T->rchild=q; switch(T->bf)case LH:T->bf=RH;break;case EH:break;case RH:T->bf=LH;break;if(OverChang(T->lchild)if(OverChang(T->rchild)retur

31、n OK;return ERROR;elsereturn OK;/-求樹的深度 int BSTDeep(BSTree T)int ln=0,rn=0,n=0;if(T)ln=(BSTDeep(T->lchild);rn=(BSTDeep(T->rchild);n=ln>rn?ln:rn;n+;return n;elsereturn 0;/-求葉子結點數(shù) Status Sum(BSTree T,int &n)if(T) if(T->lchild=NULL)&&(T->rchild=NULL) n+;if(Sum(T->lchild,n)

32、if(Sum(T->rchild,n)return OK;return ERROR;elsereturn OK;/-刪除結點 Status D eleteBST(BSTree &T,int key,bool &taller)if(!T) return FALSE;else if(EQ(key,T->data) Delete(T,taller);else if(LT(key,T->data) if(!DeleteBST(T->lchild,key,taller) return 0;if(taller)switch(T->bf)case LH:T-&g

33、t;bf=EH;taller=FALSE;break;case EH:T->bf=RH;taller=FALSE;break;case RH:RigthBalance(T);taller=FALSE;break; else if(!DeleteBST(T->rchild,key,taller) return 0;if(taller)switch(T->bf)case LH:LeftBalance(T);taller=TRUE;break;case EH:T->bf=LH;taller=FALSE;break;case RH:T->bf=EH;taller=FALS

34、E;break; return OK;/-Status Delete(BSTree &p,bool &taller)BSTree q,s;ElemType f;if(!p->rchild)q=p;p=p->lchild;taller=true;free(q);else if(!p->lchild)q=p;p=p->rchild;taller=true;free(q);else q=p;s=p->lchild;if(!s->rchild) p->lchild=s->lchild;free(s);taller=TRUE;else De

35、lete2(p,taller,f);p->data=f;return OK;/- -Status Delete2(BSTree &p,bool taller,ElemType &f)BSTree q;q=p->rchild;if(q->rchild) if(!Delete2(p->rchild,taller,f) return 0;if(taller)switch(p->bf)case LH:LeftBalance(p);taller=TRUE;break;case EH:p->bf=LH;taller=FALSE;break;case RH

36、:p->bf=EH;taller=FALSE;break; else p->rchild=q->lchild;f=q->data;taller=TRUE;free(q);return OK; /-選擇菜單 void MU() printf("=n");printf("1 建一棵新的二叉樹n");printf("2 插入新的結點n");printf("3 前，中，后序遍歷二叉樹n");printf("4 前序、中序、后序遍歷的非遞歸算法n");printf("5 層次遍歷二叉樹n");printf("6 在二叉樹中查找給定關鍵字(函數(shù)返回值為成功1,失敗0)n");printf("7 交換各結點的左右子樹n");printf("8 求二叉樹的深度n");printf("9 葉子結點數(shù)n");printf(&qu