1、123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136

2、137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236

3、237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334/googl

4、e來的#include<stdio.h> #include<malloc.h> #include<math.h> #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 typedef int Status  /函數狀態類型 typedef int ElemType &

5、#160;/二叉樹結點數據類型為整型 #define FORMAT "%d " /輸出格式與ElemType對應  void RandomHundred(int ran100) /產生100個不大于100且各不相同的整數，存放在ran100中 int i,temp,ransubscript  /temp用于交換，ransubscript為隨機下標 for(i=1;i<101;+i)rani-1=i  

6、/先把1100按順序放入數組中 for(i=100;i>0;-i) ransubscript=rand()%i  /產生隨機下標 temp=rani-1; rani-1=ranransubscript; ranransubscript=temp  /交換rani-1與ranransubscript typedef struct BSTNode ElemType data  int bf  /*結點的平

7、衡因子*/ struct BSTNode*lchild,*rchild  /* 左、右孩子指針 */BSTNode,*BSTree  #define EQ(a,b)(a)=(b) #define LT(a,b)(a)<(b) #define LH +1 /* 左高 */ #define EH 0 /* 等高 */ #define RH

8、0;-1 /* 右高 */ void R_Rotate(BSTree*p) /* 對以*p為根的二叉排序樹作右旋處理，處理之后p指向新的樹根結點，即旋轉 */ /* 處理之前的左子樹的根結點。算法9.9 */ BSTree lc  lc=(*p)->lchild  /* lc指向p的左子樹根結點 */ (*p)->lchild=lc->rchild  /*&#

9、160;lc的右子樹掛接為p的左子樹 */ lc->rchild=*p  *p=lc  /* p指向新的根結點 */  void L_Rotate(BSTree*p) /* 對以*p為根的二叉排序樹作左旋處理，處理之后p指向新的樹根結點，即旋轉 */ /* 處理之前的右子樹的根結點。算法9.10 */ BSTree rc  rc=(*p)->rchild  

10、;/* rc指向p的右子樹根結點 */ (*p)->rchild=rc->lchild  /* rc的左子樹掛接為p的右子樹 */ rc->lchild=*p  *p=rc  /* p指向新的根結點 */   void LeftBalance(BSTree*T) /* 對以指針T所指結點為根的二叉樹作左平衡旋轉處理，本算法結束時， */ /* 指針T

11、指向新的根結點。算法9.12 */ BSTree lc,rd  lc=(*T)->lchild  /* lc指向*T的左子樹根結點 */ switch(lc->bf)  /* 檢查*T的左子樹的平衡度，并作相應平衡處理 */ case LH : /* 新結點插入在*T的左孩子的左子樹上，要作單右旋處理 */ (*T)->bf=lc->bf=EH 

12、0;R_Rotate(T); break  case RH : /* 新結點插入在*T的左孩子的右子樹上，要作雙旋處理 */ rd=lc->rchild  /* rd指向*T的左孩子的右子樹根 */ switch(rd->bf)  /* 修改*T及其左孩子的平衡因子 */ case LH : (*T)->bf=RH  lc->bf=E

13、H  break  case EH : (*T)->bf=lc->bf=EH  break  case RH : (*T)->bf=EH  lc->bf=LH  break  rd->bf=EH  L_Rotate(&(*T)->lchild); /* 對*T的左子樹作左旋平衡處理 */ R_R

14、otate(T); /* 對*T作右旋平衡處理 *   void RightBalance(BSTree*T) /* 對以指針T所指結點為根的二叉樹作右平衡旋轉處理，本算法結束時， */ /* 指針T指向新的根結點 */ BSTree rc,rd  rc=(*T)->rchild  /* rc指向*T的右子樹根結點 */ switch(rc->bf) /*

15、 檢查*T的右子樹的平衡度，并作相應平衡處理 */ case RH : /* 新結點插入在*T的右孩子的右子樹上，要作單左旋處理 */ (*T)->bf=rc->bf=EH  L_Rotate(T); break  case LH : /* 新結點插入在*T的右孩子的左子樹上，要作雙旋處理 */ rd=rc->lchild  /* rd指向*T的右孩

16、子的左子樹根 */ switch(rd->bf) /* 修改*T及其右孩子的平衡因子 */ case RH : (*T)->bf=LH  rc->bf=EH  break  case EH : (*T)->bf=rc->bf=EH  break  case LH : (*T)->bf=EH  

17、rc->bf=RH  break  rd->bf=EH  R_Rotate(&(*T)->rchild); /* 對*T的右子樹作右旋平衡處理 */ L_Rotate(T); /* 對*T作左旋平衡處理 */  Status InsertAVL(BSTree*T,ElemType e,Status*taller) /* 若在平衡的二叉排序樹T中不存在和e有相同關鍵字的結點，則插入一

18、個 */ /* 數據元素為e的新結點，并返回1，否則返回0。若因插入而使二叉排序樹 */ /* 失去平衡，則作平衡旋轉處理，布爾變量taller反映T長高與否。算法9.11 */ if(!*T) /* 插入新結點，樹“長高”，置taller為TRUE */ *T=(BSTree)malloc(sizeof(BSTNode); (*T)->data=e  (*T)->lchild=(*T)->rchild=NULL &#

19、160;(*T)->bf=EH  *taller=TRUE  else if(EQ(e,(*T)->data) /* 樹中已存在和e有相同關鍵字的結點則不再插入 */ *taller=FALSE  return FALSE  if(LT(e,(*T)->data) /* 應繼續在*T的左子樹中進行搜索 */ /* 未插入 */ if(!InsertAVL(&(*

20、T)->lchild,e,taller)return FALSE  /* 已插入到*T的左子樹中且左子樹“長高” */ /* 檢查*T的平衡度 */ if(*taller)switch(*T)->bf) case LH : /* 原本左子樹比右子樹高，需要作左平衡處理 */ LeftBalance(T); *taller=FALSE  break  case EH&

21、#160;: /* 原本左、右子樹等高，現因左子樹增高而使樹增高 */ (*T)->bf=LH  *taller=TRUE  break  case RH : (*T)->bf=EH  /* 原本右子樹比左子樹高，現左、右子樹等高 */ *taller=FALSE  else /* 應繼續在*T的右子樹中進行搜索 */ /* 未插入&#

22、160;*/ if(!InsertAVL(&(*T)->rchild,e,taller)return FALSE  /* 已插入到T的右子樹且右子樹“長高” */ /* 檢查T的平衡度 */ if(*taller)switch(*T)->bf) case LH : (*T)->bf=EH  /* 原本左子樹比右子樹高，現左、右子樹等高 */ *taller=FALSE &

23、#160;break  case EH : /* 原本左、右子樹等高，現因右子樹增高而使樹增高 */ (*T)->bf=RH  *taller=TRUE  break  case RH : /* 原本右子樹比左子樹高，需要作右平衡處理 */ RightBalance(T); *taller=FALSE  return TRUE  &

24、#160;typedef BSTree SElemType;/這個很重要，定義棧的元素類型為二叉樹結點指針BSTree /棧的順序存儲表示 /SElemType為棧元素，由用戶在主函數中定義 #define STACK_INIT_SIZE 100 /* 存儲空間初始分配量 */ #define STACKINCREMENT 10 /* 存儲空間分配增量 */ typedef struct SqStack&#

25、160;SElemType *base; /* 在棧構造之前和銷毀之后，base的值為NULL */ SElemType *top; /* 棧頂指針 */ int stacksize; /* 當前已分配的存儲空間，以元素為單位 */ SqStack; /* 順序棧 */ /順序棧（存儲結構由SqStack.h定義）的基本操作 Status InitStack(SqStack *

26、S)  /* 構造一個空棧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;  Status StackEmpty(S

27、qStack S)  /* 若棧S為空棧，則返回TRUE，否則返回FALSE */ if(S.top=S.base) return TRUE; else return FALSE;  Status Push(SqStack *S,SElemType e)  /* 插入元素e為新的棧頂元素 */ if(*S).top-(*S).base>=(*S).stacksize) /

28、* 棧滿，追加存儲空間 */ (*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; retu

29、rn OK;  Status Pop(SqStack *S,SElemType *e)  /* 若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK；否則返回ERROR */ if(*S).top=(*S).base) return ERROR; *e=*-(*S).top; return OK; void PreOrderTraverse(BSTree T,Status(*Visit)(ElemType

30、 e) /非遞歸先序遍歷二叉樹 BSTree p,e  SqStack S  InitStack(&S); p=T  while(p|!StackEmpty(S) /遍歷左子樹 while(p)  (*Visit)(p->data); Push(&S,p); p=p->lchild  /通過下一次循環中的內嵌while實現右子樹遍歷 if(!StackEmpt

31、y(S) Pop(&S,&e); p=e->rchild    void InOrderTraverse(BSTree T,Status(*Visit)(ElemType e) /* 初始條件: 二叉樹T存在,Visit是對結點操作的應用函數 */ /* 操作結果: 中序遞歸遍歷T,對每個結點調用函數Visit一次且僅一次 */ if(T) InOrderTraverse(T->

32、lchild,(*Visit); /* 先中序遍歷左子樹 */ (*Visit)(T->data); /* 再訪問根結點 */ InOrderTraverse(T->rchild,(*Visit); /* 最后中序遍歷右子樹 */  void PostOrderTraverse(BSTree T,Status(*Visit)(ElemType e) /* 初始條件: 二叉樹T存在,Visit是對

33、結點操作的應用函數 */ /* 操作結果: 后序遞歸遍歷T,對每個結點調用函數Visit一次且僅一次 */ /* T不空 */ if(T) PostOrderTraverse(T->lchild,(*Visit); /* 先后序遍歷左子樹 */ PostOrderTraverse(T->rchild,(*Visit); /* 再后序遍歷右子樹 */ (*Visit)(T->data); /

34、* 最后訪問根結點 */  /*輸出元素*/ Status PrintElement(ElemType e) printf(FORMAT,e); return OK   #include"RandomHundred.c" /功能模塊1void RandomHundred(int ran100);產生100個不大于100且各不相同的整數，存放在ran100中 #include"BSTree.h&qu

35、ot; /平衡二叉排序樹的類型定義 #include"InsertAVL.c" /功能模塊2Status InsertAVL(BSTree *T,ElemType e,Status *taller); /平衡二叉排序樹T插入元素e,taller為長高標志供遞歸調用時檢查 typedef BSTree SElemType;/這個很重要，定義棧的元素類型為二叉樹結點指針BSTree #include"SqStack.h" /順序棧

36、的存儲結構 #include"SqStack.c" /棧的操作:供非遞歸先序遍歷用 #include"Traverse.c" /功能模塊3void PreOrderTraverse(BSTree T,Status (*Visit)(ElemType e);非遞歸先序遍歷二叉樹 /void InOrderTraverse(BSTree T,Status(*Visit)(ElemType e);中序遍歷二叉樹 /void PostOrderTraverse(BSTree T,Status(*Visit)(Elem