广工数据结构实验报告--平衡二叉树

1、实验报告课程名称 数据结构实验 学 院 计算机学院 专业班级 计科9班 学 号 学生姓名 指导教师 苏庆 2015 年 7 月 6 日1. 题目:平衡二叉树 ADT BBSTree 数据对象：D ai | aiElemSet, i=1,2,.,n, n0 数据关系：R1 <ai-1, ai>|ai-1, aiD, i=2,.,n 基本操作：BBSTree MakeBBSTree( )操作结果：创建好一棵树返回：将创建好的树返回Status InsertAVL(BBSTree &T, RcdType e, Status &taller)初始条件：树T已存在，e存在，t

2、aller为真操作结果：将e插入到T中返回：成功TRUE，失败FALSEStatus DeleteAVL(BBSTree &t, RcdType e, Status &shorter) 初始条件：树T已存在，e存在，shorter为真操作结果：将e从T中删除返回：成功TRUE，失败FALSEBBSTree SearchAVL(BBSTree T, RcdType e)初始条件：树T已存在，e存在操作结果：从T中找到e返回：以e为根节点的树void L_Rotate(BBSTree &p)初始条件：树p存在操作结果：对p左旋操作void R_Rotate(BBSTree

3、&p)初始条件：树p存在操作结果：对p右旋操作void LeftBalance(BBSTree &T)初始条件：树T存在操作结果：对T左平衡操作void RightBalance(BBSTree &T)初始条件：树T存在操作结果：对T右平衡操作void ExchangeSubTree(BBSTree &T)初始条件：树T存在操作结果：对T所有左右孩子交换int BBSTreeDepth(BBSTree T)初始条件：树T已存在操作结果：求树T的深度返回：树的深度BBSTree Combine2Tree(BBSTree T1, BBSTree T2)初始条件：树T

4、1和T2已存在操作结果：将T1和T2合并返回：合并后的树Status SplitBBSTree(BBSTree Tt1, BBSTree &Tt2, BBSTree &Tt3, int x)初始条件：树Tt1，Tt2，Tt3已存在，x存在操作结果：将Tt1分裂成Tt2和Tt3返回：以e为根节点的树Status PreOrder_RecTraverse(BBSTree T)初始条件：树T已存在操作结果：对树T进行递归先序遍历输出返回：成功TRUE 失败FALSEStatus InOrder_RecTraverse(BBSTree T)初始条件：树T已存在操作结果：对树T进行递归中

5、序遍历输出返回：成功TRUE 失败FALSEStatus LastOrder_RecTraverse(BBSTree T)初始条件：树T已存在操作结果：对树T进行递归后序遍历输出返回：成功TRUE 失败FALSEvoid PreOrderTravese_I(BBSTree T)初始条件：树T已存在操作结果：对树T进行非递归先序遍历输出void InOrderTraverse_I(BBSTree T)初始条件：树T已存在操作结果：对树T进行非递归中序遍历输出void LastOrderTravese_I(BBSTree T)初始条件：树T已存在操作结果：对树T进行非递归后序遍历输出void Le

6、velOrederTraverse_Print(BBSTree T)初始条件：树T已存在操作结果：对树T进行非递归层次遍历输出void BraNotationPrint(BBSTree T)初始条件：树T已存在操作结果：对树T用括号表示法输出ADT BBSTree2. 存储结构定义#include<stdio.h>#include<malloc.h>#define OVERFLOW -1#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define LH +1 /左高 #define EH 0 /等高 #d

7、efine RH -1 /右高 typedef int RcdType;typedef int Status;/*平衡二叉树结构体*/typedef struct BBSTNode RcdType data; int bf; BBSTNode *lchild, *rchild;BBSTNode,*BBSTree;3. 算法设计/*求平衡二叉树的深度*/int BBSTreeDepth(BBSTree T) int depthLeft, depthRight; if(NULL=T) return 0; else depthLeft = BBSTreeDepth(T->lchild); de

8、pthRight = BBSTreeDepth(T->rchild); return 1+(depthLeft > depthRight ? depthLeft : depthRight); /*交换二叉树所有结点的左右子树*/void ExchangeSubTree(BBSTree &T) BBSTree temp; if(NULL!=T) ExchangeSubTree(T->lchild); /使用递归交换左子树 ExchangeSubTree(T->rchild); /使用递归交换右子树 if(T->lchild!=NULL)|(T->rch

9、ild!=NULL) /如果T的子树有一个不 为空，则交换左右子树 temp = T->lchild; T->lchild = T->rchild; T->rchild = temp; /*左旋调整*/void L_Rotate(BBSTree &p) BBSTree rc = p->rchild; p->rchild = rc->lchild; rc->lchild = p; p = rc;/*右旋调整*/void R_Rotate(BBSTree &p) BBSTree lc = p->lchild; p->lch

10、ild = lc->rchild; lc->rchild = p; p = lc;/*左平衡处理操作*/void LeftBalance(BBSTree &T) BBSTree lc, rd; lc = T->lchild; switch(lc->bf) case LH: T->bf = lc->bf = EH; R_Rotate(T); break; case RH: rd = lc->rchild; switch(rd->bf) case LH: T->bf = RH; lc->bf = EH; break; case E

11、H: T->bf = lc->bf = EH; break; case RH: T->bf = EH; lc->bf = LH; break; rd->bf = EH; L_Rotate(T->lchild); R_Rotate(T); break; /*右平衡处理操作*/void RightBalance(BBSTree &T) BBSTree rd,lc; rd=T->rchild; switch(rd->bf) case RH: T->bf=rd->bf=EH; L_Rotate(T); break; case LH:

12、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); break; /*平衡二叉树的插入操作*/Status InsertAVL(BBSTree &T, RcdType e, Status &taller) if(NULL=T)

13、T = (BBSTree)malloc(sizeof(BBSTNode); T->data = e; T->bf = EH; T->lchild = NULL; T->rchild = NULL; else if(e=T->data) /书中已存在和e相等的结点 taller = FALSE; return FALSE; else if(e<T->data) if(FALSE=InsertAVL(T->lchild, e, taller) return FALSE; if(TRUE=taller) switch(T->bf) case LH

14、: LeftBalance(T); taller = FALSE; break; case EH: T->bf = LH; taller = TRUE; break; case RH: T->bf = EH; taller = FALSE; break; else if(FALSE=InsertAVL(T->rchild, e, taller) return FALSE; if(TRUE=taller) switch(T->bf) case LH: T->bf = EH; taller = FALSE; break; case EH: T->bf = RH;

15、 taller = TRUE; break; case RH: RightBalance(T); taller = FALSE; break; return TRUE;/*平衡二叉树的删除操作*/Status DeleteAVL(BBSTree &t, RcdType e, Status &shorter) /当被删结点是有两个孩子，且其前驱结点是左孩子时，tag=1 static int tag = 0; if(t = NULL) return FALSE; /如果不存在元素，返回失败 else if(e=t->data) BBSTNode *q = NULL; /如果

16、该结点只有一个孩子，则将自子树取代该结点 if(t->lchild = NULL) q = t; t = t->rchild; free(q); shorter = TRUE; else if(t->rchild = NULL) q = t; t = t->lchild; free(q); shorter = TRUE; /如果被删结点有两个孩子，则找到结点的前驱结点， /并将前驱结点的值赋给该结点，然后删除前驱结点 else q = t->lchild; while(q->rchild) q = q->rchild; t->data = q-&

17、gt;data; if(t->lchild->data=q->data) tag = 1; DeleteAVL(t->lchild, q->data, shorter); if(tag=1) BBSTree r = t->rchild; if(NULL=r) t->bf = 0; else switch(r->bf) case EH: t->bf=-1;break; default: RightBalance(t);break; else if(e<t->data) /左子树中继续查找 if(!DeleteAVL(t->l

18、child, e, shorter) return FALSE; /删除完结点之后，调整结点的平衡因子 if(shorter&&(tag=0) switch(t->bf) case LH: t->bf = EH; shorter = TRUE; break; case EH: t->bf = RH; shorter = FALSE; break; /如果本来就是右子树较高，删除之后就不平衡，需要做右平 衡操作 case RH: RightBalance(t); /右平衡处理 if(t->rchild->bf = EH) shorter = FALS

19、E; else shorter = TRUE; break; else if(e>t->data) /右子树中继续查找 if(!DeleteAVL(t->rchild, e, shorter) return FALSE; /删除完结点之后，调整结点的平衡因子 if(shorter&&(tag=0) switch(t->bf) case LH: LeftBalance(t); /左平衡处理 if(t->lchild->bf = EH)/注意这里，画图思考一下 shorter = FALSE; else shorter = TRUE; break

20、; case EH: t->bf = LH; shorter = FALSE; break; case RH: t->bf = EH; shorter = TRUE; break; if(tag=1) int depthLeft = BBSTreeDepth(t->lchild); int depthRight = BBSTreeDepth(t->rchild); t->bf = depthLeft - depthRight; return TRUE; /*平衡二叉树的查找操作*/BBSTree SearchAVL(BBSTree T, RcdType e) if

21、(T=NULL) return NULL; if(e=T->data) return T; else if(e>T->data) return SearchAVL(T->rchild, e); else return SearchAVL(T->lchild, e); /*获取输入存到数组a*/Array GetInputToArray() Array head, p, q; char k; head = p = q = NULL; int m; if(k!='n') scanf("%d",&m); p = (ArrayN

22、ode*)malloc(sizeof(ArrayNode); head = p; p->data = m; k = getchar(); while(k!='n') scanf("%d",&m); q = (ArrayNode*)malloc(sizeof(ArrayNode); q->data = m; p->next = q; p = p->next; k = getchar(); if(p!=NULL) p->next = NULL; return head; /返回存放数据的头指针 /*根据输入的字符串建一棵平衡

23、二叉树*/BBSTree MakeBBSTree( ) int i=0; Status taller = TRUE; BBSTree T = NULL; Array a; a = GetInputToArray(); while(a!=NULL) taller = TRUE; InsertAVL(T, a->data, taller); a = a->next; return T;/*递归先序遍历*/Status PreOrder_RecTraverse(BBSTree T) if(NULL=T) return OK; printf("%d ",T->da

24、ta); PreOrder_RecTraverse(T->lchild); PreOrder_RecTraverse(T->rchild);/*递归中序遍历*/Status InOrder_RecTraverse(BBSTree T) if(T->lchild) InOrder_RecTraverse(T->lchild); printf("%d ",T->data); if(T->rchild) InOrder_RecTraverse(T->rchild);/*递归后序遍历*/Status LastOrder_RecTravers

25、e(BBSTree T) if(T->lchild) LastOrder_RecTraverse(T->lchild); if(T->rchild) LastOrder_RecTraverse(T->rchild); printf("%d ",T->data);/*找到最左结点*/BBSTree GoFarLeft(BBSTree T, LStack &S) if(NULL=T) return NULL; while(T->lchild!=NULL) Push_LS(S, T); T = T->lchild; return

26、T;/*非递归中序遍历*/void InOrderTraverse_I(BBSTree T) LStack S; InitStack_LS(S); BBSTree p = NULL; p = GoFarLeft(T, S); while(p!=NULL) printf("%d ",p->data); if(p->rchild!=NULL) p = GoFarLeft(p->rchild, S); else if(StackEmpty_LS(S)!=TRUE) Pop_LS(S, p); else p = NULL; BBSTree VisitFarLeft

27、(BBSTree T, LStack &S) if(NULL=T) return NULL; /如果T为空，则返回空 printf("%d ",T->data); /先序，先读取结点数据 while(T->lchild!=NULL) Push_LS(S, T); /入栈 T = T->lchild; /遍历下一个左子树 printf("%d ", T->data); /下一个结点的读取数据 return T;/*非递归先序遍历*/void PreOrderTravese_I(BBSTree T) LStack S; Ini

28、tStack_LS(S); BBSTree p; p = VisitFarLeft(T, S); /先将左边的数据先序读取 while(p!=NULL) if(p->rchild!=NULL) /如果最左下结点的右子树不为空 p = VisitFarLeft(p->rchild, S); /执行遍历该结点的左子树 else if(StackEmpty_LS(S)!=TRUE) Pop_LS(S,p); /如果S不为空栈，出栈 else p = NULL; /如果为空栈，p赋予空 /*非递归后序遍历*/void LastOrderTravese_I(BBSTree root) BBS

29、Tree p = root; BBSTree stack30; int num=0; BBSTree have_visited = NULL; while(NULL!=p|num>0) while(NULL!=p) stacknum+=p; p=p->lchild; p=stacknum-1; if(NULL=p->rchild|have_visited=p->rchild) printf("%d ",p->data); num-; have_visited=p; p=NULL; else p=p->rchild; printf(&quo

30、t;n");/*非递归层次遍历输出一棵二叉树*/void LevelOrederTraverse_Print(BBSTree T) if(T=NULL) printf("The tree is empty!"); if(T!=NULL) LQueue Q; InitQueue_LQ(Q); BBSTree p = T; printf("%d ",p->data); EnQueue_LQ(Q,p); while(DeQueue_LQ(Q,p) if(p->lchild!=NULL) printf("%d ", p-

31、>lchild->data); EnQueue_LQ(Q, p->lchild); if(p->rchild!=NULL) printf("%d ", p->rchild->data); EnQueue_LQ(Q, p->rchild); /*括号表示法输出平衡二叉树*/void BraNotationPrint(BBSTree T) if(NULL=T) printf(" 空!"); else if(T!=NULL) if(T!=NULL) printf("%i",T->data);

32、if(T->lchild|T->rchild) printf("("); if(T->lchild|T->rchild) if(T->lchild) BraNotationPrint(T->lchild); else if(T->rchild) printf("#"); printf(","); if(T->rchild) BraNotationPrint(T->rchild); else if(T->lchild) printf("#"); printf

33、(")"); /*将一棵树转换为一个数组*/Array GetArrayFromTree(BBSTree T) Status firstTime = TRUE; Array head = NULL; ArrayNode *b = NULL; ArrayNode *q = NULL; if(T=NULL) printf("The tree is empty!"); if(T!=NULL) LQueue Q; InitQueue_LQ(Q); BBSTree p = T; q = (Array)malloc(sizeof(ArrayNode); q->

34、data = p->data; if(firstTime=TRUE) head = q; firstTime = FALSE; b = q; else b->next = q; b = b->next; EnQueue_LQ(Q,p); while(DeQueue_LQ(Q,p) if(p->lchild!=NULL) q = (Array)malloc(sizeof(ArrayNode); q->data = p->lchild->data; b->next = q; b = b->next; EnQueue_LQ(Q, p->lc

35、hild); if(p->rchild!=NULL) q = (Array)malloc(sizeof(ArrayNode); q->data = p->rchild->data; b->next = q; b = b->next; EnQueue_LQ(Q, p->rchild); if(b!=NULL) b->next = NULL; return head;/*将两棵平衡二叉树合并成一颗平衡二叉树*/BBSTree Combine2Tree(BBSTree T1, BBSTree T2) Status taller = TRUE; Arra

36、y a = NULL; a = GetArrayFromTree(T2); while(a!=NULL) taller = TRUE; InsertAVL(T1, a->data, taller); a = a->next; return T1; /*将一棵平衡二叉树分裂成两棵平衡二叉树*/*参数1：要进行分裂的树参数2：分裂出来的小于等于x的子树参数3：分裂出来的 大于x的子树 参数4：关键字x */Status SplitBBSTree(BBSTree Tt1, BBSTree &Tt2, BBSTree &Tt3, int x) Array a = NULL;

37、 Status taller; a = GetArrayFromTree(Tt1); if(Tt1=NULL) return FALSE; else while(a!=NULL) if(a->data<=x) taller = TRUE; InsertAVL(Tt2, a->data, taller); a = a->next; else taller = TRUE; InsertAVL(Tt3, a->data, taller); a = a->next; return TRUE;4. 测试(1) 建树操作测试代码: 测试数据：1 2 3 4 5 6测试结

38、果： (2) 插入操作测试代码：测试数据：1 2 3 4 5 6 插入8测试结果：测试数据：1 2 3 4 5 6 插入4测试结果：(3) 删除操作测试代码：测试数据：1 2 3 4 5 6 删除6测试结果：测试数据：1 2 3 4 5 6 删除2测试结果：测试数据：1 2 3 4 5 6 删除4测试结果：(4) 查找操作测试代码：测试数据：1 2 3 4 5 6 查找5测试结果：(5) 输出测试代码：测试数据：1 2 3 4 5 6 测试结果：5. 思考与小结在完成平衡二叉树实验的过程中，所遇到的最大问题就是如何实现平衡二叉树删除结点的接口，因为课本没有涉及到这个知识点，所以自己只能通过阅读

39、其他书籍和通过参考网上的资料来对这个过程有了进一步的理解。其次自己想了一个树的括号表示法来将一棵树打印出来，这对于一棵树的表示是挺有用的。总的来说，平衡二叉树这个知识点涉及到的算法大概就是添加结点，删除结点，查找结点这三个方面，而其他的接口都是以这三个为基础，实现进一步的拓展。6. 源代码 /* (1)根据输入字符串创建一棵平衡二叉树 BBSTree MakeBBSTree(); (2)平衡二叉树插入元素操作 Status InsertAVL(BBSTree &T, RcdType e, Status &taller); (3)层次遍历输出二叉树 void LevelOrede

40、rTraverse_Print(BBSTree T); (4)括号表示法输出二叉树 void BraNotationPrint(BBSTree T); (5)平衡二叉树删除元素操作 Status DeleteAVL(BBSTree &t, RcdType e, Status &shorter); (6)求平衡二叉树的深度 int BBSTreeDepth(BBSTree T); (7)交换所有结点的左右子树 void ExchangeSubTree(BBSTree &T) (8)递归先序遍历 Status PreOrder_RecTraverse(BBSTree T)；

41、 (9)递归中序遍历 Status InOrder_RecTraverse(BBSTree T);(10)递归后序遍历 Status LastOrder_RecTraverse(BBSTree T);(11)非递归先序遍历 void PreOrderTraverse_I(BBSTree T);(12)非递归中序遍历 void InOrderTraverse_I(BBSTree T);(13)非递归后序遍历 void LastOrderTraverse_I(BBSTree T); */#include<stdio.h>#include<malloc.h>#define O

42、VERFLOW -1#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define LH +1 /左高 #define EH 0 /等高 #define RH -1 /右高 typedef int RcdType;typedef int Status;/*存放输入数据的数组结构体*/typedef struct ArrayNode RcdType data; ArrayNode *next; ArrayNode, *Array;/*平衡二叉树结构体*/typedef struct BBSTNode RcdType data; in

43、t bf; BBSTNode *lchild, *rchild;BBSTNode,*BBSTree;/*链队列结构体*/typedef struct LQNode BBSTree elem; struct LQNode *next;LQNode, *QueuePtr;/*队列结点结构体*/typedef struct QueuePtr front; QueuePtr rear;LQueue;/*栈结点结构体*/typedef struct LSNode BBSTree data; /数据域 struct LSNode *next; /指针域 LSNode, *LStack; /结点和链栈类型/*初始化一个链栈*/Status InitStack_LS(LStack &S)