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

实习报告一、需求分析1、问题描述利用平衡二‎叉树实现一‎个动态查找‎表。

（1）实现动态查‎找表的三种‎基本功能：查找、插入和删除‎。

（2）初始时，平衡二叉树‎为空树，操作界面给‎出查找、插入和删除‎三种操作供‎选择。

每种操作均‎要提示输入‎关键字。

在查找时，如果查找的‎关键字不存‎在，则把其插入‎到平衡二叉‎树中。

每次插入或‎删除一个结‎点后，应更新平衡‎二叉树的显‎示。

（3）每次操作的‎关键字都要‎从文件中读‎取，并且关键字‎的集合限定‎为短整型数‎字{1，2，3······}，关键字出现‎的顺序没有‎限制，允许出现重‎复的关键字‎，并对其进行‎相应的提示‎。

（4）平衡二叉树‎的显示采用‎图形界面画‎出图形。

2、系统功能打开数据文‎件，用文件中的‎关键字来演‎示平衡二叉‎树操作的过‎程。

3、程序中执行‎的命令包括‎：（1）(L)oad from data file //在平衡的二‎叉树中插入‎关键字；（2）(A)ppend‎new recor‎d//在平衡的二‎叉树中查找‎关键字；（3）(U)pate speci‎a l recor‎d//显示调整过‎的平衡二叉‎树；（4）(D)elete‎speci‎a l recor‎d//删除平衡二‎叉树中的关‎键字；（5）(Q)uit //结束。

4、测试数据：平衡二叉树‎为：图 1 插入关键字‎10之前的‎平衡二叉树‎插入关键字‎：10；调整后：图 2 插入关键字‎10之后的‎平衡二叉树‎删除关键字‎：14；调整后：图 3 删除关键字‎14后的平‎衡二叉树查找关键字‎：11；输出：The data is here!图 3 查找关键字‎11后的平‎衡二叉树二、概要设计本次实验目‎的是为了实‎现动态查找‎表的三种基‎本功能：查找、插入和删除‎。

动态查找表‎可有不同的‎表示方法，在此次实验‎中主要是以‎平衡二叉树‎的结构来表‎示实现的，所以需要两‎个抽象数据‎类型：动态查找表‎和二叉树。

实验报告课程名称数据结构实验学院计算机学院专业班级计科9班学号学生姓名指导教师苏庆2015年 7 月6 日1.题目:平衡二叉树ADT BBSTree{数据对象：D＝{ ai | ai∈ElemSet, i=1,2,...,n, n≥0 }数据关系：R1＝{ <ai-1, ai>|ai-1, ai∈D, i=2,...,n }基本操作：BBSTree MakeBBSTree( )操作结果：创建好一棵树返回：将创建好的树返回Status InsertAVL(BBSTree &T, RcdType e, Status &taller)初始条件：树T已存在，e存在，taller为真操作结果：将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 &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)初始条件：树T1和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进行递归中序遍历输出返回：成功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 LevelOrederTraverse_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 //等高#define 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);depthRight = 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->rchild!=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->lchild = 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 EH: 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: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){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==InsertA VL(T->lchild, e, taller)) return FALSE;if(TRUE==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{if(FALSE==InsertA VL(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; taller = TRUE; break;case RH: RightBalance(T); taller = FALSE; break;}}}return TRUE;}/*平衡二叉树的删除操作*/Status DeleteA VL(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;//如果该结点只有一个孩子，则将自子树取代该结点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->data;if(t->lchild->data==q->data){tag = 1;}DeleteA VL(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(!DeleteA VL(t->lchild, 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 = FALSE;elseshorter = TRUE;break;}}}else if(e>t->data){ //右子树中继续查找if(!DeleteA VL(t->rchild, e, shorter)){return FALSE;}//删除完结点之后，调整结点的平衡因子if(shorter&&(tag==0)) {switch(t->bf){case LH:LeftBalance(t); //左平衡处理if(t->lchild->bf == EH)//注意这里，画图思考一下shorter = FALSE;elseshorter = TRUE;break;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 SearchA VL(BBSTree T, RcdType e){if(T==NULL) return NULL;if(e==T->data){return T;}else if(e>T->data){return SearchA VL(T->rchild, e);}else {return SearchA VL(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 = (ArrayNode*)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; //返回存放数据的头指针}/*根据输入的字符串建一棵平衡二叉树*/BBSTree MakeBBSTree( ){int i=0;Status taller = TRUE;BBSTree T = NULL;Array a;a = GetInputToArray();while(a!=NULL){taller = TRUE;InsertA VL(T, a->data, taller);a = a->next;}return T;}/*递归先序遍历*/Status PreOrder_RecTraverse(BBSTree T){ if(NULL==T) return OK;printf("%d ",T->data);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_RecTraverse(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 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(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;InitStack_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){BBSTree p = root;BBSTree stack[30];int num=0;BBSTree have_visited = NULL;while(NULL!=p||num>0){while(NULL!=p){stack[num++]=p;p=p->lchild;}p=stack[num-1];if(NULL==p->rchild||have_visited==p->rchild){printf("%d ",p->data);num--;have_visited=p;p=NULL;}else{p=p->rchild;}}printf("\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->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);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(")");}}}/*将一棵树转换为一个数组*/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->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->lchild);}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;Array a = NULL;a = GetArrayFromTree(T2);while(a!=NULL){taller = TRUE;InsertA VL(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;Status taller;a = GetArrayFromTree(Tt1);if(Tt1==NULL) return FALSE;else{while(a!=NULL){if(a->data<=x){taller = TRUE;InsertA VL(Tt2, a->data, taller);a = a->next;}else {taller = TRUE;InsertA VL(Tt3, a->data, taller);a = a->next;}}}return TRUE;}4.测试(1)建树操作测试代码:测试数据：1 2 3 4 5 6测试结果：(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.思考与小结在完成平衡二叉树实验的过程中，所遇到的最大问题就是如何实现平衡二叉树删除结点的接口，因为课本没有涉及到这个知识点，所以自己只能通过阅读其他书籍和通过参考网上的资料来对这个过程有了进一步的理解。

数据结构实验报告二叉树数据结构实验报告：二叉树引言：数据结构是计算机科学中的重要基础，它为我们提供了存储和组织数据的方式。

二叉树作为一种常见的数据结构，广泛应用于各个领域。

本次实验旨在通过实践，深入理解二叉树的概念、性质和操作。

一、二叉树的定义与性质1.1 定义二叉树是一种特殊的树结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。

二叉树可以为空树，也可以是由根节点和左右子树组成的非空树。

1.2 基本性质（1）每个节点最多有两个子节点；（2）左子树和右子树是有顺序的，不能颠倒；（3）二叉树的子树仍然是二叉树。

二、二叉树的遍历2.1 前序遍历前序遍历是指首先访问根节点，然后按照先左后右的顺序遍历左右子树。

在实际应用中，前序遍历常用于复制一颗二叉树或创建二叉树的副本。

2.2 中序遍历中序遍历是指按照先左后根再右的顺序遍历二叉树。

中序遍历的结果是一个有序序列，因此在二叉搜索树中特别有用。

2.3 后序遍历后序遍历是指按照先左后右再根的顺序遍历二叉树。

后序遍历常用于计算二叉树的表达式或释放二叉树的内存。

三、二叉树的实现与应用3.1 二叉树的存储结构二叉树的存储可以使用链式存储或顺序存储。

链式存储使用节点指针连接各个节点，而顺序存储则使用数组来表示二叉树。

3.2 二叉树的应用（1）二叉搜索树：二叉搜索树是一种特殊的二叉树，它的左子树上的节点都小于根节点，右子树上的节点都大于根节点。

二叉搜索树常用于实现查找、插入和删除等操作。

（2）堆：堆是一种特殊的二叉树，它满足堆序性质。

堆常用于实现优先队列，如操作系统中的进程调度。

（3）哈夫曼树：哈夫曼树是一种带权路径最短的二叉树，常用于数据压缩和编码。

四、实验结果与总结通过本次实验，我成功实现了二叉树的基本操作，包括创建二叉树、遍历二叉树和查找节点等。

在实践中，我进一步理解了二叉树的定义、性质和应用。

二叉树作为一种重要的数据结构，在计算机科学中有着广泛的应用，对于提高算法效率和解决实际问题具有重要意义。

二叉树的操作实验报告二叉树的操作实验报告引言二叉树是计算机科学中常用的数据结构，它具有良好的搜索性能和灵活的插入和删除操作。

本实验旨在通过实际操作，深入理解二叉树的基本操作和特性。

1. 二叉树的定义和基本概念二叉树是一种特殊的树状结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。

二叉树的节点由数据和指向左右子节点的指针组成。

根据节点的位置，可以将二叉树分为左子树、右子树和根节点。

2. 二叉树的遍历二叉树的遍历是指按照一定的顺序访问二叉树中的所有节点。

常用的遍历方式有前序遍历、中序遍历和后序遍历。

前序遍历先访问根节点，然后按照左子树、右子树的顺序遍历；中序遍历先访问左子树，然后根节点，最后右子树；后序遍历先访问左子树，然后右子树，最后根节点。

3. 二叉树的插入操作插入操作是将一个新节点插入到二叉树中的特定位置。

插入操作需要考虑节点的大小关系，小于当前节点则插入到左子树，大于当前节点则插入到右子树。

插入操作可以保持二叉树的有序性。

4. 二叉树的删除操作删除操作是将指定节点从二叉树中删除。

删除操作需要考虑被删除节点的子节点情况，如果被删除节点没有子节点，则直接删除；如果有一个子节点，则将子节点替代被删除节点的位置；如果有两个子节点，则选择被删除节点的后继节点或前驱节点替代被删除节点。

5. 二叉树的查找操作查找操作是在二叉树中搜索指定的节点。

二叉树的查找操作可以使用递归或迭代的方式实现。

递归方式会自动遍历整个二叉树，直到找到目标节点或遍历完整个树。

迭代方式则需要手动比较节点的值，并根据大小关系选择左子树或右子树进行进一步查找。

6. 二叉树的平衡性二叉树的平衡性是指左子树和右子树的高度差不超过1。

平衡二叉树可以提高搜索效率，避免出现极端情况下的性能下降。

常见的平衡二叉树有AVL树和红黑树。

7. 二叉树应用场景二叉树在计算机科学中有广泛的应用场景。

例如，文件系统的目录结构可以使用二叉树来表示；数据库中的索引结构也可以使用二叉树来实现。

实验报告课程名称：数据结构
第 1 页共4 页
五、实验总结（包括心得体会、问题回答及实验改进意见，可附页）
这次实验主要是建立二叉树，和二叉树的先序、中序、后续遍历算法。

通过这次实验，我巩固了二叉树这部分知识,从中体会理论知识的重要性。

在做实验之前，要充分的理解本次实验的理论依据，这样才能达到事半功倍的效果。

如果在没有真正理解实验原理之盲目的开始实验，只会浪费时间和精力。

例如进行二叉树的遍历的时候，要先理解各种遍历的特点。

先序遍历是先遍历根节点，再依次先序遍历左右子树。

中序遍历是先中序遍历左子树，再访问根节点，最后中序遍历右子树。

而后序遍历则是先依次后续遍历左右子树，再访问根节点。

掌握了这些，在实验中我们就可以融会贯通，举一反三。

其次要根据不光要懂得代码的原理，还要对题目有深刻的了解，要明白二叉树的画法，在纸上先进行自我演练，对照代码验证自己写的正确性。

第 3 页共4 页
第 4 页共4 页。

数据结构二叉树的实验报告数据结构二叉树的实验报告一、引言数据结构是计算机科学中非常重要的一个领域，它研究如何组织和存储数据以便高效地访问和操作。

二叉树是数据结构中常见且重要的一种，它具有良好的灵活性和高效性，被广泛应用于各种领域。

本实验旨在通过实际操作和观察，深入了解二叉树的特性和应用。

二、实验目的1. 理解二叉树的基本概念和特性；2. 掌握二叉树的创建、遍历和查找等基本操作；3. 通过实验验证二叉树的性能和效果。

三、实验过程1. 二叉树的创建在实验中，我们首先需要创建一个二叉树。

通过输入一系列数据，我们可以按照特定的规则构建一棵二叉树。

例如，可以按照从小到大或从大到小的顺序将数据插入到二叉树中，以保证树的有序性。

2. 二叉树的遍历二叉树的遍历是指按照一定的次序访问二叉树中的所有节点。

常见的遍历方式有前序遍历、中序遍历和后序遍历。

前序遍历是先访问根节点，然后再依次遍历左子树和右子树；中序遍历是先遍历左子树，然后访问根节点，最后再遍历右子树；后序遍历是先遍历左子树，然后遍历右子树，最后访问根节点。

3. 二叉树的查找二叉树的查找是指在二叉树中寻找指定的节点。

常见的查找方式有深度优先搜索和广度优先搜索。

深度优先搜索是从根节点开始，沿着左子树一直向下搜索，直到找到目标节点或者到达叶子节点；广度优先搜索是从根节点开始，逐层遍历二叉树，直到找到目标节点或者遍历完所有节点。

四、实验结果通过实验，我们可以观察到二叉树的特性和性能。

在创建二叉树时，如果按照有序的方式插入数据，可以得到一棵平衡二叉树，其查找效率较高。

而如果按照无序的方式插入数据，可能得到一棵不平衡的二叉树，其查找效率较低。

在遍历二叉树时，不同的遍历方式会得到不同的结果。

前序遍历可以用于复制一棵二叉树，中序遍历可以用于对二叉树进行排序，后序遍历可以用于释放二叉树的内存。

在查找二叉树时，深度优先搜索和广度优先搜索各有优劣。

深度优先搜索在空间复杂度上较低，但可能会陷入死循环；广度优先搜索在时间复杂度上较低，但需要较大的空间开销。

return s;
}
void dispbtnode1(btnode *b)
{
btnode *st[maxsize],*p;
int level[maxsize][2],top=-1,n,i,width=4;
char type;
if(b!=NULL)
{
top++;
st[top]=b;
level[top][0]=width;
level[top][0]=n+width;
level[top][1]=1;
}
if(p->lchild!=NULL)
{
top++;
st[top]=p->lchild;
level[top][0]=n+width;
level[top][1]=0;
}
}
}
}
2）先序，中序、后序遍历功能实现，因为想自己更能读懂理解程序，没有使用递归算法。
}
btnode *rchildnode(btnode *p)
{
return p->rchild ;
}
btnode * revers(btnode *b)//交换左右子树
{
if(b!=NULL)
{
if(b->rchild !=NULL||b->lchild !=NULL)
{
btn;lchild );
（3）根据二叉树的基本运算，设计先序遍历和中序遍历（或者中序遍历和后序遍历），确定二叉树的算法。
（4）在不改变原有二叉树结构的条件下，将二叉树左右孩子进行交换，并采用凹入表示法和括号表示法输出原有二叉树及交换子树后的二叉树。

数据结构实验报告—二叉树数据结构实验报告—二叉树引言二叉树是一种常用的数据结构，它由节点和边构成，每个节点最多有两个子节点。

在本次实验中，我们将对二叉树的基本结构和基本操作进行实现和测试，并深入了解它的特性和应用。

实验目的1. 掌握二叉树的基本概念和特性2. 熟练掌握二叉树的基本操作，包括创建、遍历和查找等3. 了解二叉树在实际应用中的使用场景实验内容1. 二叉树的定义和存储结构：我们将首先学习二叉树的定义，并实现二叉树的存储结构，包括节点的定义和节点指针的表示方法。

2. 二叉树的创建和初始化：我们将实现二叉树的创建和初始化操作，以便后续操作和测试使用。

3. 二叉树的遍历：我们将实现二叉树的前序、中序和后序遍历算法，并测试其正确性和效率。

4. 二叉树的查找：我们将实现二叉树的查找操作，包括查找节点和查找最大值、最小值等。

5. 二叉树的应用：我们将探讨二叉树在实际应用中的使用场景，如哈夫曼编码、二叉搜索树等。

二叉树的定义和存储结构二叉树是一种特殊的树形结构，它的每个节点最多有两个子节点。

节点被表示为一个由数据和指向其左右子节点的指针组成的结构。

二叉树可以分为三类：满二叉树、完全二叉树和非完全二叉树。

二叉树可以用链式存储结构或顺序存储结构表示。

- 链式存储结构：采用节点定义和指针表示法，通过将节点起来形成一个树状结构来表示二叉树。

- 顺序存储结构：采用数组存储节点信息，通过计算节点在数组中的位置来进行访问和操作。

二叉树的创建和初始化二叉树的创建和初始化是二叉树操作中的基础部分。

我们可以通过手动输入或读取外部文件中的数据来创建二叉树。

对于链式存储结构，我们需要自定义节点和指针，并通过节点的方式来构建二叉树。

对于顺序存储结构，我们需要定义数组和索引，通过索引计算来定位节点的位置。

一般来说，初始化一个二叉树可以使用以下步骤：1. 创建树根节点，并赋初值。

2. 创建子节点，并到父节点。

3. 重复步骤2，直到创建完整个二叉树。

数据结构二叉树实验报告二叉树是一种常用的数据结构，它在计算机科学中有着广泛的应用。

本文将介绍二叉树的定义、基本操作以及一些常见的应用场景。

一、二叉树的定义和基本操作二叉树是一种特殊的树形结构，它的每个节点最多有两个子节点。

一个节点的左子节点称为左子树，右子节点称为右子树。

二叉树的示意图如下：```A/ \B C/ \D E```在二叉树中，每个节点可以有零个、一个或两个子节点。

如果一个节点没有子节点，我们称之为叶子节点。

在上面的示例中，节点 D 和 E 是叶子节点。

二叉树的基本操作包括插入节点、删除节点、查找节点和遍历节点。

插入节点操作可以将一个新节点插入到二叉树中的合适位置。

删除节点操作可以将一个指定的节点从二叉树中删除。

查找节点操作可以在二叉树中查找指定的节点。

遍历节点操作可以按照一定的顺序遍历二叉树中的所有节点。

二、二叉树的应用场景二叉树在计算机科学中有着广泛的应用。

下面将介绍一些常见的应用场景。

1. 二叉搜索树二叉搜索树是一种特殊的二叉树，它的每个节点的值都大于其左子树中的节点的值，小于其右子树中的节点的值。

二叉搜索树可以用来实现快速的查找、插入和删除操作。

它在数据库索引、字典等场景中有着重要的应用。

2. 堆堆是一种特殊的二叉树，它的每个节点的值都大于或小于其子节点的值。

堆可以用来实现优先队列，它在任务调度、操作系统中的内存管理等场景中有着重要的应用。

3. 表达式树表达式树是一种用来表示数学表达式的二叉树。

在表达式树中，每个节点可以是操作符或操作数。

表达式树可以用来实现数学表达式的计算，它在编译器、计算器等场景中有着重要的应用。

4. 平衡二叉树平衡二叉树是一种特殊的二叉树，它的左子树和右子树的高度差不超过1。

平衡二叉树可以用来实现高效的查找、插入和删除操作。

它在数据库索引、自平衡搜索树等场景中有着重要的应用。

三、总结二叉树是一种常用的数据结构，它在计算机科学中有着广泛的应用。

本文介绍了二叉树的定义、基本操作以及一些常见的应用场景。

数据结构二叉树综合实验报告数据结构二叉树综合实验报告1.引言在计算机科学中，二叉树是一种常见的数据结构，它由节点组成，每个节点最多有两个子节点，分别称为左子节点和右子节点。

二叉树具有广泛的应用场景，如在搜索算法、图形处理和编译器设计中等。

本报告旨在介绍我们进行的二叉树综合实验，包括实验目的、实验过程中的具体步骤和实验结果分析等。

2.实验目的本实验的主要目的是通过设计和实现二叉树的基本操作，加深对二叉树的理解，并掌握二叉树的基本算法和应用。

具体的实验目标包括：- 熟悉二叉树的基本概念和性质；- 掌握二叉树的创建、插入和删除操作；- 实现二叉树的遍历算法，包括前序、中序和后序遍历；- 实现二叉树的搜索功能；- 进行基于二叉树的排序实验。

3.实验步骤3.1 二叉树的创建首先，我们需要创建一个空的二叉树。

通过定义二叉树的节点结构和指针，可以动态地分配内存空间用于创建节点，并建立节点之间的连接关系。

3.2 节点的插入在已有的二叉树中，我们可以向其中插入新的节点。

插入操作通常涉及到比较节点的键值大小，然后根据比较结果决定插入新节点的位置。

3.3 节点的删除除了插入节点，我们也可能需要从二叉树中删除节点。

删除操作通常需要考虑节点的子节点情况，例如，被删除的节点是否有左子节点、右子节点或者同时存在。

3.4 二叉树的遍历二叉树的遍历操作可以按照不同的顺序进行，包括前序（根-左-右）、中序（左-根-右）和后序（左-右-根）遍历。

在实验中，我们需要实现这三种遍历算法，并观察它们的输出结果。

3.5 二叉树的搜索在已有的二叉树中，我们可根据节点的键值进行搜索操作。

通过比较键值，我们可以判断在左子树或右子树中进行进一步的搜索，直至找到目标节点或确定目标节点不存在于二叉树中。

3.6 基于二叉树的排序二叉树可以作为一种排序算法的基础结构。

在实验中，我们可以通过节点的插入操作构建一个包含数据集的二叉树，并通过中序遍历获取有序的数据。

数据结构实验报告二叉树二叉树是一种重要的数据结构，广泛应用于计算机科学和算法设计中。

在本次实验中，我们通过实际编程实践，深入理解了二叉树的基本概念、性质和操作。

一、二叉树的定义和基本性质二叉树是一种特殊的树结构，每个节点最多有两个子节点。

它具有以下基本性质：1. 根节点：二叉树的顶部节点称为根节点，它没有父节点。

2. 子节点：每个节点最多有两个子节点，分别称为左子节点和右子节点。

3. 叶节点：没有子节点的节点称为叶节点。

4. 深度：从根节点到某个节点的路径长度称为该节点的深度。

5. 高度：从某个节点到其叶节点的最长路径长度称为该节点的高度。

6. 层次遍历：按照从上到下、从左到右的顺序遍历二叉树的节点。

二、二叉树的实现在本次实验中，我们使用C++语言实现了二叉树的基本操作，包括创建二叉树、插入节点、删除节点、查找节点等。

通过这些操作，我们可以方便地对二叉树进行增删改查。

三、二叉树的遍历二叉树的遍历是指按照某种顺序访问二叉树的所有节点。

常用的遍历方式有三种：前序遍历、中序遍历和后序遍历。

1. 前序遍历：先访问根节点，然后依次递归遍历左子树和右子树。

2. 中序遍历：先递归遍历左子树，然后访问根节点，最后递归遍历右子树。

3. 后序遍历：先递归遍历左子树，然后递归遍历右子树，最后访问根节点。

四、二叉树的应用二叉树在计算机科学和算法设计中有广泛的应用。

以下是一些常见的应用场景：1. 二叉搜索树：二叉搜索树是一种特殊的二叉树，它的左子树的值都小于根节点的值，右子树的值都大于根节点的值。

它可以高效地支持插入、删除和查找操作，常用于有序数据的存储和检索。

2. 堆：堆是一种特殊的二叉树，它的每个节点的值都大于（或小于）其子节点的值。

堆常用于实现优先队列等数据结构。

3. 表达式树：表达式树是一种用二叉树表示数学表达式的方法。

通过对表达式树的遍历，可以实现对数学表达式的计算。

4. 平衡树：平衡树是一种特殊的二叉树，它的左右子树的高度差不超过1。

数据结构设计性实验报告课程名称数据结构实验■题目名称平衡二叉树_____________ 学生学院_ 计算机学院 _______________专业班级_学号_________________学生姓名___________________指导教师______________2015年6月14日目录一、设计任务、要求以及所用环境及工具. (4)实验设计任务. (4)实验要求. (4)编程环境. (4)抽象数据类型及接口简要描述. (5)抽象数据类型. (5)接口简要描述. (7)算法设计 (8)程序测试 (17)测试代码. (17)测试结果. (18)测试分析. (20)思考与小结 (21)设计任务、要求以及所用环境及工具实验设计任务以教材中讨论的各种抽象数据类型为对象，利用C语言的数据类型表示和实现其中某个实验要求实验要求如下：1 •首先了解设计的任务，然后根据自己的基础和能力从中选择一题。

一般来说，选择题目应以在规定的时间内能完成，并能得到应有的锻炼为原则。

若学生对教材以外的相关题目较感兴趣，希望选作实验的题目时，应征得指导教师的认可，并写出明确的抽象数据类型定义及说明。

2. 实验前要作好充分准备，包括：理解实验要求，掌握辅助工具的使用，了解该抽象数据类型的定义及意义，以及其基本操作的算法并设计合理的存储结构。

3. 实验时严肃认真，要严格按照要求独立进行设计，不能随意更改。

注意观察并记录各种错误现象，纠正错误，使程序满足预定的要求，实验记录应作为实验报告的一部分。

4. 实验后要及时总结，写出实验报告，并附所打印的问题解答、程序清单，所输入的数据及相应的运行结果。

编程环境抽象数据类型及接口简要描述本次数据结构实验设计我选择的是二叉平衡树 （AVL ）,使用C++面向对象编程语言实现。

利用C++泛型编程技术完成 AVL 类AVLTree 。

抽象数据类型1. 平衡二叉树结点的 ADT 为： template <type name T> class AVLTreeNode {public :T _key; II 结点关键字int _bf;II 结点平衡因子 AVLTreeNode *_lchild ; II 结点的左孩指针 AVLTreeNode *_rchild ; II 结点的右孩指针II 构造函数AVLTreeNode(T key ‘AVLTreeNode *lchild , AVLTreeNode *rchild :_key(key),_l child(lchild),_rchild(rchild),_bf(bf){};};R L：tzdHET募権怪 4.*___ J □"三耙■耐3E P|C*<底总¥i4 C4 +ATk Viitad C--4CLU和mi*ECiy.i G91D.EiW• La 话亦需 ▼Z ••穷A下完成。

其操作包括：s.push(SElemType e)//入栈
s.pop()//出栈
s.empty()//判断栈是否为空，是空时返回TRUE
s.top（）//返回栈顶元素
q.push(SElemType e)//入队列
q.pop()//出队列
q.empty()//判断队列是否为空，是空时返回TRUE
q．front()//返回队头元素
T->data=e;
T->lchild=T->rchild=NULL;
T->bf=EH;
taller=true;
}
else{
if(e==T->data){
taller=false;
return 0;
}
if(e<T->data){
if(!InsertAVL(T->lchild,e,taller)) return 0;
p->rchild=rc->lchild;
rc->lchild=p;
p=rc;
}
void Left_Balance(BSTree &T){ //插入结点时向左平衡
BSTree lc,rd;
lc=T->lchild;
switch(lc->bf){
case LH:T->bf=lc->bf=EH;R_Rotate(T);break;
if(Visit(T->data))
if(PreOrderTraverse(T->lchild,Visit))
if(PreOrderTraverse(T->rchild,Visit)) return OK;
return ERROR;

二叉树实验报告总结(共10篇)二叉树实验报告实验报告课程名称算法与数据结构专业学号姓名实验日期算法与数据结构实验报告一、实验目的1.了解二叉树的结构特点及有关概念，掌握二叉树建立的基本算法2.了解二叉树遍历的概念，掌握遍历二叉的算法3.进一步掌握树的结构及非线性特点，递归特点和动态性。

二、实验内容二叉树的实现和运算三、实验要求1．用C++/C完成算法设计和程序设计并上机调试通过。

2．撰写实验报告，提供实验结果和数据。

3．分析算法，并简要给出算法设计小结和心得。

四、算法步骤用户以三元组形式输入二叉树的结点元素及其位置关系，建立二叉树，并打印输出该二叉树。

用户输入选择结点，程序调用BiTNode* Find Node(char tag, BiTNode* node)函数，返回子树的根结点，然后调用BiTreeDepth(BiTree T)函数，求出子树的深度，并输出该值。

3.用户可以选择是否继续执行程序，若继续，则输入1，否则输入0，结束程序。

五、主程序代码：int main(void){BiTree T;TElemType e1;char node; // node为用户选择输入的结点//int b,choose; // b为以选定结点为子树的深度，choose为实现多次选择输入的标志//BiTNode* a; // a为选定结点为子树的根结点//choose=1; // 多次选择的标志，当choose为1时运行程序，为0时结束程序// InitBiTree(T);printf(构造空二叉树后,树空否？%d(1:是0:否), 树的深度=%d\n,BiTreeEmpty(T),BiTreeDepth(T));e1 = Root(T);if(e1 != Nil)#ifdef CHARprintf(二叉树的根为: %c\n,e1);#endif#ifdef INTprintf(二叉树的根为: %d\n,e1);#endifelseprintf(树空，无根\n); //三元组构建二叉树striile(x!=end){AddNode(T, x[0], x[1], x[2]);GetUserWord(x);} //输出树PrintTreeLevel( T );//以三元组形式输入任意二叉树（以大写字母表示结点），求以任意一选定结点为子树的深度。

《数据结构〉课程实验报告实验名称树与二叉树实验序号5实验日期姓名院系班级学号指导教师成绩专业教师评语一、实验目得与要求(1)掌握树得相关概念，包括树、结点得度、树得度、分支结点、叶子结点、儿子结点、双亲结点、树得深度、森林等定义。

(2)掌握树得表示，包括树形表示法、文氏图表示法、凹入表示法与括号表示法等。

(3)掌握二叉树得概念，包括二叉树、满二叉树与完全二叉树得定义。

(4)掌握二叉树得性质。

(5)重点掌握二叉树得存储结构，包括二叉树顺序存储结构与链式存储结构。

(6)重点掌握二叉树得基本运算与各种遍历算法得实现。

(7)掌握线索二叉树得概念与相关算法得实现。

(8)掌握哈夫曼树得定义、哈夫曼树得构造过程与哈夫曼编码产生方法。

(9)掌握并查集得相关概念与算法。

(1 0)灵活掌握运用二叉树这种数据结构解决一些综合应用问题。

二、实验项目摘要1编写一程序，实现二叉树得各种基本运算，并在此基础上设计一个主程序完成如下功能：(1)输出二叉树b;(2)输出H结点得左、右孩子结点值；(3)输出二叉树b得深度；(4)输出二叉树b得宽度；(5)输出二叉树b得结点个数；(6)输出二叉树b得叶子结点个数。

2编写一程序，实现二叉树得先序遍历、中序遍历与后序遍历得各种递归与非递归算法，以及层次遍历得算法。

三、实验预习内容二叉树存储结构，二叉树基本运算（创建二叉树、寻找结点、找孩子结点、求高度、输出二叉树）三、实验结果与分析7-1#incl u d e < s tdio、h>#incl u d e<m a1 l o c、h># d e f in e M axS i z e 100typedef cha r E l emT y p e;ty p ed e f struct n o d e｛o ElemTy p e data;。

str u c t n ode * 1 c h i 1 d ;0struct no d e * r chi l d;0}BT N ode;void Cr e a teBTNod e(BTNod e *&b,c h ar *s t r)｛o B TNod e* S t[M a x S ize] , *p=NULL;o i n t t o p=-1,k,j = 0:ch a r ch;b=N U L L;oo0ch= s tr廿］；wh i l e C ch!='\O')叶s wit c h(ch)｛o ca s e'(':to p ++; St[t o p]=p;k=l;b rea k;。

实验报告二叉树篇一：二叉树实验报告山东工商学院《数据结构》实验指导及报告书XX / XX 学年姓名：学号：班级：指导教师：Xx学院XX年11月25日第一学期实验三二叉树一、实验目的1、掌握二叉树的基本特性2、掌握二叉树的先序、中序、后序的递归遍历算法3、理解二叉树的先序、中序、后序的非递归遍历算法4、通过求二叉树的深度、叶子结点数和层序遍历等算法，理解二叉树的基本特性二、实验预习说明以下概念1、二叉树：是另一种树型结构，它的特点是每个结点至多只有两棵子树，并且二叉树有左右之分，其次序不能任意颠倒。

2、递归遍历：1、非递归遍历：4、层序遍历：三、实验内容和要求1、阅读并运行下面程序，根据输入写出运行结果，并画出二叉树的形态。

#include #include#define MAX 20typedef struct BTNode{ /*节点结构声明*/char data ;/*节点数据*/ struct BTNode *lchild;struct BTNode *rchild ; /*指针*/ }*BiTree;BiTree createBiTree(BiTree t){ /* 先序遍历创建二叉树*/ char s;printf("\nplease input data:(exit for #)"); s=getche();if(s=='#'){t=NULL; return t;}t=(BiTree)malloc(sizeof(struct BTNode));if(t==NULL){printf("Memory alloc failure!"); exit(0);} t->data=s;t->lchild=createBiTree(t->lchild); /*递归建立左子树*/ t->rchild=createBiTree(t->rchild); /*递归建立右子树*/ return t; }void PreOrder(BiTree p){ /* 先序遍历二叉树*/ if ( p!= NULL ) {printf("%c", p->data);PreOrder( p->lchild ) ;PreOrder( p->rchild ) ; } }void InOrder(BiTree p){ /* 中序遍历二叉树*/ if( p!= NULL ) {InOrder( p->lchild ) ;printf("%c", p->data);InOrder( p->rchild) ; } }void PostOrder(BiTree p){ /* 后序遍历二叉树*/ if ( p!= NULL ) {PostOrder( p->lchild ) ;PostOrder( p->rchild) ;printf("%c", p->data); } }void Preorder_n(BiTree p){ /*先序遍历的非递归算法*/ BiTree stack[MAX],q; int top=0,i;for(i=0;i while(q!=NULL){printf("%c",q->data);if(q->rchild!=NULL) stack[top++]=q->rchild;if(q->lchild!=NULL)q=q->lchild;elseif(top>0) q=stack[--top]; else q=NULL; } }void release(BiTree t){ /*释放二叉树空间*/ if(t!=NULL){release(t->lchild); release(t->rchild);free(t); } }int main(){BiTree t=NULL; int e,m,g;t=createBiTree(t);printf("\n\nPreOrder the tree is:"); PreOrder(t);printf("\n\nInOrder the tree is:"); InOrder(t);printf("\n\nPostOrder the tree is:"); PostOrder(t);printf("\n\n先序遍历序列（非递归）:");Preorder_n(t);printf("\n\n输出结点总数:"); e=PreOrder_num(t); printf("%d",e);printf("\n\n输出树的深度:"); m=BTNodeDepth(t); printf("%d\n",m);printf("\n\n输出树叶子总数:"); g=LeafNodes(t); printf("%d\n",g); release(t); return 0; }?运行程序输入：ABC##DE#G##F### 运行结果：画出该二叉树的形态：2、在上题中补充求二叉树中求结点总数算法（提示：可在某种遍历过程中统计遍历的结点数），并在主函数中补充相应的调用验证正确性。

数学与计算机科学学院数据结构程序设计报告平衡二叉树学生姓名:学号:班级:指导老师:报告日期:1.题目与要求1). 问题的提出编写已个平衡二叉树，主要是对插入一个元素导致树不平衡的情况进行平衡化处理以及相关的处理。

2）设计的知识点队列的插入，删除，二叉树的建立于销毁，平衡树的平衡化，以及C语言中基础应用于结构等。

3）功能要求(1).通过不断插入的方式创建一棵平衡二叉树，包括输入结点的关键字和相关信息。

(2)按要求输出创建的平衡二叉树结点，包括顺序（中序）输出和按层次输出。

(3)插入新增的结点，若结点不存在则插入平衡二叉树，并进行相关调整。

(4)销毁二叉树。

(5)退出菜单界面如下：2.功能设计算法设计选择创建平衡二叉树后，利用循环不断插入结点，并进行调整，当输入节点为0时停止进入菜单界面。

在平横二叉树排序树BSTree上插入一个新的数据元素ｅ的递归算法可如下描述：（１）若BSTree为空树，则插入一个数据元素为e的新结点作为BSTree的根结点，树的深度增1；（２）若e的关键字和BSTree的根节点的关键字相等，则不进行插入；（３）若e的关键字小于BSTree的根结点的关键字，而且在其左子树中不存在和e形同的关键字的结点，则将e插入在其左子树上，并且当插入之后的左子树的深度加1时，分别就下列不同情况处理之：a.BSTree的跟结点的平衡因子为-1（右子树的深度大于左子树的深度）：则将跟结点的平衡因子更改为0，BBST的深度不变；b.BBST的根结点的平衡因子为0（左，右子树的深度相等）：则将根结点的平衡因子更改为1，BBST的深度增1；c.BBST的根结点的平衡因子为1（左子树的深度大于右子树的深度）：若BBST的左子树根结点的平衡因子为1，则需进行向左旋平衡处理，并且在右旋之后，将根节点和其右子树根节点的平衡因子更改为0，树的深度不变；若BBST的左子树根结点的平衡因子为-1，则需进行向左，向右的双向旋转平衡处理，并且在旋转处理之后，修改根结点和其左右子树的平衡因子，数的深度不变；（４）若e的关键字大于BBST的根结点的关键字，而且在BBST的右子树中不存在和e有相同的关键字的的节点，则将e插入在BBST的右子树上，并且当插入之后的右子树深度增加（+1）时，分别就不同情况处理之。