//作者：lray //語(yǔ)言：C語(yǔ)言 //日期：2012年12月23日 //功能：實(shí)現平衡二叉樹(shù)的各種算法 /*用函數實(shí)現如下平衡二叉排序樹(shù)算法： （1） 插入新結點(diǎn) （2） 前序、中序、后序遍歷二叉樹(shù) （遞歸） （3） 前序、中序、后序遍歷的非遞歸算法 （4） 層次遍歷二叉樹(shù) （5） 在二叉樹(shù)中查找給定關(guān)鍵字(函數返回值為成功1,失敗0) （6） 交換各結點(diǎn)的左右子樹(shù) （7） 求二叉樹(shù)的深度 （8） 葉子結點(diǎn)數 （9） 刪除某結點(diǎn) */ #include<stdio.h> //引用頭文件stdio.h #include<stdlib.h> //引用頭文件stdlib.h #include<malloc.h> //引用頭文件malloc.h #define MAXSIZE 100 //用#define定義全局變量MAXSIZE的值為100 #define OK 1 //用#define定義全局變量OK的值為1 #define ERROR 0 //用#define定義全局變量ERROR的值為0 typedef int Status; //定義Status為int類(lèi)型來(lái)表示函數返回值狀態(tài) typedef int ElemType; //定義ElemType為int類(lèi)型來(lái)表示元素類(lèi)型 typedef struct BSTNode //定義平衡二叉樹(shù)結構體 { ElemType data; //結點(diǎn)存儲的數據 int height; //結點(diǎn)的高度 struct BSTNode *lchild,*rchild; //左、右孩子指針 }BSTNode,*BSTree; typedef BSTree Position; //定義Position為BSTree來(lái)表示節點(diǎn)樹(shù)中位置 typedef struct //定義棧的結構體 { BSTree *base; //在棧構造前和銷(xiāo)毀后，base的值為NULL BSTree *top; //棧頂指針 int stacksize; //當前已分配的存儲空間，以元素為單位 }Stack; typedef struct //定義隊列的結構體 { BSTree *front; //隊頭指針 BSTree *rear; //隊尾指針 int queuesize; //當前已分配的存儲空間，以元素為單位 }Queue; Status InsertBST(BSTree &T,ElemType e); //實(shí)現樹(shù)的節點(diǎn)的插入 Status PreOrderTraverse(BSTree T); //實(shí)現樹(shù)的遞歸前序遍歷 Status InOrderTraverse(BSTree T); //實(shí)現樹(shù)的遞歸中序遍歷 Status PostOrderTraverse(BSTree T); //實(shí)現樹(shù)的遞歸后序遍歷 Status AllOrderTraverse(BSTree T); //實(shí)現三種遞歸遍歷的打印 Status NonPreOrder(BSTree T,Stack S); //實(shí)現樹(shù)的非遞歸前序遍歷 Status NonInOder(BSTree T,Stack S); //實(shí)現樹(shù)的非遞歸中序遍歷 Status NonPostOrder(BSTree T,Stack S); //實(shí)現樹(shù)的非遞歸后序遍歷 Status NonAllOrder(BSTree T,Stack S); //實(shí)現三種非遞歸遍歷的打印 Status LevelTraverse(BSTree T,Queue Q); //實(shí)現二叉樹(shù)的層次遍歷 Status PostsSearch(BSTree T,ElemType e);//實(shí)現二叉樹(shù)中給定關(guān)鍵字的查找 Status SwapSubtree(BSTree T); //實(shí)現結點(diǎn)左右子樹(shù)的交換 int TreeDepth(BSTree T); //實(shí)現二叉樹(shù)深度的求值 int TotalNodeNum(BSTree T); //實(shí)現二叉樹(shù)總結點(diǎn)數的求值 int LeafNodeNum(BSTree T); //實(shí)現二叉樹(shù)葉子結點(diǎn)數的求值 Status DeleteBST(BSTree &T,ElemType e); //實(shí)現樹(shù)的節點(diǎn)的刪除 int TreeHeight(BSTree T); //實(shí)現樹(shù)的高度的求值 int Max(int a,int b); //實(shí)現兩個(gè)數中求最大值 Position MinElemSearch(BSTree T); //實(shí)現最小元素的查找 BSTree LeftRotate(BSTree g); //實(shí)現二叉樹(shù)一次左旋轉操作 BSTree RightRotate(BSTree g); //實(shí)現二叉樹(shù)一次右旋轉操作 BSTree L_RRotate(BSTree g); //實(shí)現一次先左旋轉再右旋轉操作 BSTree R_LRotate(BSTree g); //實(shí)現一次先右旋轉再左旋轉操作 Status CreatStack(Stack &S); //實(shí)現棧的建立 Status CreatQueue(Queue &Q); //實(shí)現隊列的建立 Status InsertBST(BSTree &T,ElemType e) //實(shí)現在二叉樹(shù)中插入新結點(diǎn)的函數 { if(T==NULL) //判斷是否為空樹(shù)，是則建建立一個(gè)根節點(diǎn)給樹(shù) { T=(BSTree)malloc(sizeof(BSTNode)); if(!T) //判斷該節點(diǎn)是否建立失敗 return ERROR; T->data=e; T->height=0; //根節點(diǎn)時(shí)，高度為0 T->lchild=T->rchild=NULL; } else if(e<T->data) //如果輸入的元素比節點(diǎn)數據小，則向左插入 { InsertBST(T->lchild,e); //遞歸調用該函數本身 if(TreeHeight(T->lchild)-TreeHeight(T->rchild)==2) { //判斷二叉樹(shù)是否出現不平衡狀態(tài)，是則進(jìn)入該分支 if(e<T->lchild->data) //若輸入的數據比左孩子結點(diǎn)的數據小，則進(jìn)行左旋轉 T=LeftRotate(T); else //否則先進(jìn)行左旋轉再右旋轉 T=L_RRotate(T); } } else if(e>T->data) //如果輸入的元素比節點(diǎn)數據大，則向右插入 { InsertBST(T->rchild,e); //遞歸調用該函數本身 if(TreeHeight(T->rchild)-TreeHeight(T->lchild)==2) { //判斷二叉樹(shù)是否出現不平衡狀態(tài)，是則進(jìn)入該分支 if(e>T->rchild->data) //若輸入的數據比右孩子結點(diǎn)的數據大，則進(jìn)行右旋轉 T=RightRotate(T); else //否則先進(jìn)行右旋轉再左旋轉 T=R_LRotate(T); } } //如果輸入數據與節點(diǎn)數據相等，不需要進(jìn)行操作 T->height=Max(TreeHeight(T->lchild),TreeHeight(T->rchild))+1; return OK; //最后需要記錄節點(diǎn)高度 } Status PreOrderTraverse(BSTree T) //實(shí)現遞歸前序遍歷函數 { if(T!=NULL) //判斷是否為空樹(shù) { printf("%d ",T->data); PreOrderTraverse(T->lchild); PreOrderTraverse(T->rchild); } return OK; } Status InOrderTraverse(BSTree T) //實(shí)現遞歸中序遍歷函數 { if(T!=NULL) //判斷是否為空樹(shù) { InOrderTraverse(T->lchild); printf("%d ",T->data); InOrderTraverse(T->rchild); } return OK; } Status PostOrderTraverse(BSTree T) //實(shí)現遞歸后序遍歷函數 { if(T!=NULL) //判斷是否為空樹(shù) { PostOrderTraverse(T->lchild); PostOrderTraverse(T->rchild); printf("%d ",T->data); } return OK; } Status AllOrderTraverse(BSTree T) //實(shí)現各種遞歸遍歷打印函數 { printf("\n\t遞歸前序遍歷如下：\n\t"); PreOrderTraverse(T); printf("\n"); printf("\n\t遞歸中序遍歷如下：\n\t"); InOrderTraverse(T); printf("\n"); printf("\n\t遞歸后序遍歷如下：\n\t"); PostOrderTraverse(T); printf("\n"); return OK; } Status NonPreOrder(BSTree T,Stack S) //實(shí)現非遞歸前序遍歷函數 { while(S.base!=S.top||T!=NULL) //判斷棧和樹(shù)是否為空 { while(T!=NULL) //向左子樹(shù)一直循環(huán)到最左的節點(diǎn) { printf("%d ",T->data); //輸出元素 *S.top++=T; T=T->lchild; } T=*--S.top; //實(shí)現出棧 T=T->rchild; //轉向右子樹(shù) } return OK; } Status NonInOder(BSTree T,Stack S) //實(shí)現非遞歸中序遍歷函數 { while(S.base!=S.top||T!=NULL) //判斷棧和樹(shù)是否為空 { while(T!=NULL) //向左子樹(shù)一直循環(huán)到最左的節點(diǎn) { *S.top++=T; T=T->lchild; } T=*--S.top; //實(shí)現出棧 printf("%d ",T->data); //輸出元素 T = T->rchild; //轉向右子樹(shù) } return OK; } Status NonPostOrder(BSTree T,Stack S) //實(shí)現非遞歸后序遍歷函數 { BSTree temp=NULL; //定義臨時(shí)變量，用來(lái)標記剛剛訪(fǎng)問(wèn)過(guò)的節點(diǎn) while(S.base!=S.top||T!= NULL) //判斷棧和樹(shù)是否為空 { while(T!=NULL) //向左子樹(shù)一直循環(huán)到最左的節點(diǎn) { *S.top++=T; T=T->lchild; } T=*(S.top-1); //取棧頂節點(diǎn) if(T->rchild==NULL||T->rchild==temp) { //如果該節點(diǎn)沒(méi)有右孩子或者其右孩子剛剛被訪(fǎng)問(wèn)過(guò) printf("%d ",T->data); //輸出元素 S.top--; //已訪(fǎng)問(wèn)，使其出棧 temp=T; //標記為剛剛訪(fǎng)問(wèn)過(guò) T=NULL; //若遍歷完以該節點(diǎn)為根的子樹(shù)，且?？?，則結束，否則繼續 } else T=T->rchild; //轉向右子樹(shù) } return OK; } Status NonAllOrder(BSTree T,Stack S) //實(shí)現各種非遞歸遍歷打印函數 { printf("\n\t非遞歸前序遍歷如下：\n\t"); CreatStack(S); NonPreOrder(T,S); printf("\n"); printf("\n\t非遞歸中序遍歷如下：\n\t"); CreatStack(S); NonInOder(T,S); printf("\n"); printf("\n\t非遞歸后序遍歷如下：\n\t"); CreatStack(S); NonPostOrder(T,S); printf("\n"); return OK; } Status LevelTraverse(BSTree T,Queue Q) //實(shí)現層次遍歷函數 { if(T!=NULL) { *Q.rear++=T; while(Q.front!=Q.rear) //判斷隊列是否為空 { if(T->lchild!=NULL) //判斷左子樹(shù)是否為空 *Q.rear++=T->lchild; //左子樹(shù)進(jìn)隊 if(T->rchild!=NULL) //判斷右子樹(shù)是否為空 *Q.rear++=T->rchild; //右子樹(shù)進(jìn)隊 T=*Q.front++; //實(shí)現出隊操作 printf("%d ",T->data); T=*Q.front; //此時(shí)的隊頭元素 } } return OK; } Status PostsSearch(BSTree T,ElemType e) //實(shí)現在二叉樹(shù)中查找給定關(guān)鍵字函數 { if(T!=NULL) //判斷二叉樹(shù)是否為空 { if(e==T->data) //判斷查找值是否與節點(diǎn)數據相等 return OK; else if(e<T->data) return PostsSearch(T->lchild,e);//查找值小于節點(diǎn)數據，則進(jìn)入左子樹(shù)查找 else return PostsSearch(T->rchild,e);//查找值大于節點(diǎn)數據，則進(jìn)入右子樹(shù)查找 } else return ERROR; } Status SwapSubtree(BSTree T) //實(shí)現交換各結點(diǎn)的左右子樹(shù)函數 { BSTree temp; //定義臨時(shí)變量 if(T!=NULL) //判斷二叉樹(shù)是否為空 { temp=T->lchild; T->lchild=T->rchild; T->rchild=temp; SwapSubtree(T->lchild); SwapSubtree(T->rchild); } return OK; } int TreeDepth(BSTree T) //實(shí)現求二叉樹(shù)的深度函數 { int deep,ldeep=0,rdeep=0; if(T!=NULL) //判斷二叉樹(shù)是否為空 { ldeep=TreeDepth(T->lchild); rdeep=TreeDepth(T->rchild); deep=Max(ldeep,rdeep)+1; } else return 0; return deep; } int TotalNodeNum(BSTree T) //實(shí)現統計總的結點(diǎn)數函數 { int sum=0,lsum=0,rsum=0; if(T!=NULL) //判斷二叉樹(shù)是否為空 { lsum=TotalNodeNum(T->lchild); rsum=TotalNodeNum(T->rchild); sum=lsum+rsum+1; return sum; } else return 0; } int LeafNodeNum(BSTree T) //實(shí)現統計葉子結點(diǎn)數函數 { int dot=0,ldot=0,rdot=0; if(T!=NULL) //判斷二叉樹(shù)是否為空 { if(T->lchild==NULL&&T->rchild==NULL) //判斷是否只含有一個(gè)節點(diǎn) dot=1; else { ldot=LeafNodeNum(T->lchild); rdot=LeafNodeNum(T->rchild); dot=ldot+rdot; } } else return 0; return dot; } Status DeleteBST(BSTree &T,ElemType e) //實(shí)現在二叉樹(shù)中刪除某結點(diǎn)的函數 { Position temp; //定義臨時(shí)變量 if(T==NULL) //判斷二叉樹(shù)是否為空 return ERROR; else if(e<T->data) //需要刪除的數據比節點(diǎn)數據小的情況 return DeleteBST(T->lchild,e); //繼續調用函數本身進(jìn)入左子樹(shù)查找 else if(e>T->data) //需要刪除的數據比節點(diǎn)數據大的情況 return DeleteBST(T->rchild,e); //繼續調用函數本身進(jìn)入右子樹(shù)查找 else //即需要刪除的數據與節點(diǎn)數據相等的情況 { if(T->lchild!=NULL&&T->rchild!=NULL) { //左右孩子都存在的情況 temp=MinElemSearch(T->rchild); //在右子樹(shù)中找到最小的節點(diǎn) T->data=temp->data; //用找到的最小節點(diǎn)的數據代替要刪除的節點(diǎn)的數據 DeleteBST(T->rchild,T->data); //刪除右子樹(shù)剛剛找到的最小的節點(diǎn) } else //有一個(gè)孩子或者沒(méi)有孩子的情況 { temp=T; if(T->lchild==NULL) //判斷是否沒(méi)有孩子的情況 T=T->rchild; else if(T->rchild==NULL) //判斷是否有一個(gè)孩子的情況 T=T->lchild; free(temp); } return OK; } } int TreeHeight(BSTree T) //實(shí)現求樹(shù)的高度的函數 { if(T==NULL) //判斷二叉樹(shù)是否為空 return -1; else return T->height; } int Max(int a,int b) //實(shí)現求較大值的函數 { return a>b?a:b; //三元運算符，哪個(gè)值大返回哪個(gè) } Position MinElemSearch(BSTree T) //實(shí)現查找最小元素的函數 { if(T==NULL) //判斷二叉樹(shù)是否為空 return NULL; else if(T->lchild==NULL) //判斷是否為沒(méi)有子樹(shù)的情況 return T; else return MinElemSearch(T->lchild); } BSTree LeftRotate(BSTree g) //實(shí)現樹(shù)的向左旋轉函數 { BSTree temp; temp=g->lchild; g->lchild=temp->rchild; temp->rchild=g; temp->height=Max(TreeHeight(temp->lchild),g->height)+1; g->height=Max(TreeHeight(g->lchild),TreeHeight(g->rchild))+1; return temp; //返回新的根節點(diǎn) } BSTree RightRotate(BSTree g) //實(shí)現樹(shù)的向左旋轉函數 { BSTree temp; temp=g->rchild; g->rchild=temp->lchild; temp->lchild=g; g->height=Max(TreeHeight(g->lchild),TreeHeight(g->rchild))+1; temp->height=Max(TreeHeight(g->rchild),g->height)+1; return temp; //返回新的根節點(diǎn) } BSTree L_RRotate(BSTree g) //實(shí)現樹(shù)的向左旋轉再向右旋轉函數 { g->lchild=RightRotate(g->lchild); //先逆時(shí)針旋轉 return LeftRotate(g); //再順時(shí)針旋轉 } BSTree R_LRotate(BSTree g) //實(shí)現樹(shù)的向右旋轉再向左旋轉函數 { g->rchild=LeftRotate(g->rchild); //先順時(shí)針旋轉 return RightRotate(g); //再逆時(shí)針旋轉 } Status CreatStack(Stack &S) //實(shí)現棧的建立函數 { S.base=(BSTree*)malloc(MAXSIZE*sizeof(BSTree)); if(!S.base) //判斷是否建立失敗 return ERROR; S.top=S.base; S.stacksize=MAXSIZE; return OK; } Status CreatQueue(Queue &Q) //實(shí)現隊列的建立函數 { Q.front=(BSTree*)malloc(MAXSIZE*sizeof(BSTree)); if(!Q.front) //判斷是否建立失敗 return ERROR; Q.rear=Q.front; Q.queuesize=MAXSIZE; return OK; } int main() //主函數 { ElemType k,e,d; int i,n,ch; char c; BSTree T=NULL; Stack S; Queue Q; printf("\n\t運行本程序需要先構造一個(gè)二叉樹(shù)！\n"); printf("\n\t請輸入需要插入的元素個(gè)數："); scanf("%d",&n); if(n==0) { printf("\n\t成功創(chuàng )建一個(gè)空二叉樹(shù)！",n); c=getchar(); //用來(lái)吸收多余字符 c=getchar(); //用來(lái)吸收多余字符 } else { printf("\n\t請輸入要插入的%d個(gè)元素：",n); for(i=0;i<n;i++) //連續輸入n個(gè)元素 { scanf("%d",&e); InsertBST(T,e); //插入元素 } printf("\n\t成功創(chuàng )建該二叉樹(shù)！",n); c=getchar(); //用來(lái)吸收多余字符 c=getchar(); //用來(lái)吸收多余字符 } while(1) //進(jìn)入程序的循環(huán) { system("cls"); //實(shí)現清屏處理 printf(" ☆ 實(shí)現平衡二叉樹(shù)的各種算法 ☆ \n"); printf(" \n"); printf(" ◆◆◆◆◆◆◆◆◆◆◆◆ 請從下面的操作中選擇一項 ◆◆◆◆◆◆◆◆◆◆◆◆◆\n"); printf(" ◆ ◆\n"); printf(" ◆ ◆ 1.在二叉樹(shù)中插入新結點(diǎn) ◆\n"); printf(" ◆ ◆ 2.實(shí)現遞歸的前序、中序、后序遍歷二叉樹(shù) ◆\n"); printf(" ◆ ◆ 3.實(shí)現非遞歸的前序、中序、后序遍歷二叉樹(shù) ◆\n"); printf(" ◆ ◆ 4.實(shí)現層次遍歷二叉樹(shù) ◆\n"); printf(" ◆ ◆ 5.在二叉樹(shù)中查找給定關(guān)鍵字 ◆\n"); printf(" ◆ ◆ 6.交換二叉樹(shù)中各結點(diǎn)的左右子樹(shù) ◆\n"); printf(" ◆ ◆ 7.實(shí)現二叉樹(shù)的深度的求值 ◆\n"); printf(" ◆ ◆ 8.統計二叉樹(shù)中葉子結點(diǎn)數 ◆\n"); printf(" ◆ ◆ 9.在二叉樹(shù)中刪除某結點(diǎn) ◆\n"); printf(" ◆ ◆ 0.退出本程序 ◆\n"); printf(" ◆ ◆\n"); printf(" ◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆\n"); printf("\n\t你的選擇是："); scanf("%d",&ch); switch(ch) //進(jìn)入選擇 { case 1: //調用插入結點(diǎn)的函數 printf("\n\t請輸入你想要插入的元素："); scanf("%d",&e); if(InsertBST(T,e)==OK) printf("\n\t成功插入元素%d！\n",e); else printf("\n\t插入元素%d失??！\n",e); break; case 2: //調用打印各種遞歸遍歷的函數 printf("\n\t平衡二叉樹(shù)的各種遞歸遍歷如下：\n"); AllOrderTraverse(T); break; case 3: //調用打印各種非遞歸遍歷的函數 printf("\n\t平衡二叉樹(shù)的各種非遞歸遍歷如下：\n"); NonAllOrder(T,S); break; case 4: //調用打印層次遍歷的函數 printf("\n\t平衡二叉樹(shù)的層次遍歷如下：\n\t"); CreatQueue(Q); //創(chuàng )建隊列 LevelTraverse(T,Q); printf("\n"); break; case 5: //調用關(guān)鍵字查找的函數 printf("\n\t請輸入你想要查找的關(guān)鍵字："); scanf("%d",&k); if(PostsSearch(T,k)==OK) //返回查找的值，成功返回1，失敗則返回0 printf("\n\t成功找到關(guān)鍵字%d！\n",k); else printf("\n\t沒(méi)有找到關(guān)鍵字%d！\n",k); break; case 6: //調用轉換子樹(shù)的函數 if(SwapSubtree(T)==OK) printf("\n\t成功交換左右子樹(shù)！\n"); else printf("\n\t交換左右子樹(shù)失??！\n"); break; case 7: //調用求二叉樹(shù)深度的函數 printf("\n\t平衡二叉樹(shù)的深度是："); printf("%d\n",TreeDepth(T)); break; case 8: //調用統計樹(shù)結點(diǎn)數的函數 printf("\n\t平衡二叉樹(shù)的總結點(diǎn)數是："); printf("%d\n",TotalNodeNum(T)); printf("\n\t平衡二叉樹(shù)的葉子結點(diǎn)數是："); printf("%d\n",LeafNodeNum(T)); break; case 9: //調用刪除結點(diǎn)的函數 printf("\n\t請輸入你想要刪除的元素："); scanf("%d",&d); if(DeleteBST(T,d)==OK) printf("\n\t成功刪除元素%d！\n",d); else printf("\n\t刪除失敗，沒(méi)有找到元素%d！\n",d); break; case 0: //輸入0，則推出本程序 return 0; break; default: //如果輸入非法字符，則進(jìn)入該分支 c=getchar(); //用來(lái)吸收多余字符 printf("\n\a\t輸入錯誤，請重新輸入！\n"); break; } scanf("%c",&c); //用來(lái)吸收多余字符 printf("\n\t按任意鍵繼續，或按“n”退出！你的選擇是："); scanf("%c",&c); if(c=='n') return 0; } return 0; }聯(lián)系客服
