平衡二叉树的生成-Read

1、湖南人文科技学院计算机系课程设计说明书课程名称：数据结构课程代码：题目:平衡二叉树的生成年级/专业/班：04级计算机科学与技术专业计算机本科三班学生姓名：王伟学号：04356320指导教师：羊四清开题时间：2007年6月10日完成时间：2007年6月22日数据结构课程设计摘要1一、引言2二、设计任务与目的2三、设计方案与实施21、总体设计2基本概念（包括设计到的概念）A.树的概念B.平衡二叉树的概念C.遍历的概念D.动态平衡技术的概念E.最小不平衡子树的概念构造算法插入结点删除结点中序遍历2、详细设计8A.使用的头文件B.常量定义C.全局变量定义D.数据结构定义E.部分关键函数原型说明3、程序

2、清单104、程序调试与体会235、运行结果（截图）23四、结论24五、参考文献24数据结构课程设计摘要树型结构是以分支关系定义的层次结构，它是一种重要的非线性结构。树型结构在客观世界中广泛存在。而平衡二叉树因其特性，它在查找时拥有比普通二叉树更高的效率，所以它拥有很广泛的应用。关键词：二叉树，平衡二叉树，查找AbstractThetreestructureisdefinedwiththebranchrelationoflayerstructure,itisaimportantnonlinearstructure.Thetreestructureisanextensiveexistenceint

3、heobjectiveworld.Andbecauseofitscharacteristic,itownshigherefficiencythangeneralbinarytreewhileinsearching,soitisusedextensively.Keywords:BinaryTree,BalancedBinaryTree,Search数据结构课程设计数据结构课程设计-平衡二叉树的生成设计一、引言平衡二叉树是数据结构中一个非常重要的概念。它对二叉树的优化和提高查询效率有重要的作用，它是动态查找的一个非常重要方法，它在实际生产中有着广泛的应用。二、设计目的与任务通过本课程设计教学所要求

4、达到的目的是：充分理解和掌握二叉树、平衡二叉树的相关概念和知识。掌握平衡二叉树的生成、结点删除、插入等操作过程，并编程实现从键盘上输入一系列数据（整型），建立一棵平衡二叉树，任意插入或删除一个结点后仍然要求构成平衡二叉树，并按中序遍历输出这棵平衡二叉树。三、设计方案与实施1、总体设计基本概念（包括设计到的概念）树的概念树（Tree）是n（n>=0）个结点的有限集。在任意一棵非空树中：1）有且仅有一个特定的称为根的结点；2）当n>1时，其余结点可分为m（m>0）个互不相交的有限集T1,T2.Tm,其中每一个集合又是一棵树，并且称为根的子树（SubTree）。【例】如图1所示：图

5、1图1是有8个结点的树，其中A是根，其余结点分成2个互不相交的子集：T1=B,D,T2=C,E,F,G,H;T1和T2都是根A的子树，且本身也是一棵树。平衡二叉树的概念形态匀称的二叉树称为平衡二叉树(Balancedbinarytree)若T是一棵非空二叉树，其左、右子树为TL和深度。当且仅当TL、TR都是平衡二叉树；|hl-hr|<1;时，则T是平衡二叉树。【例】如图2所示：AA色,其严格定义是：TR,令hl和hr分别为左、右子树的1©数据结构课程设计(a)平衡二叉树(b)非平衡二叉树图2平衡二叉树与非平衡二叉树相应地定义hlhr为二叉平衡树的平衡因子(balancefact

6、or)。因此，平衡二叉树上所有结点的平衡因子可能是-1,0,1。换言之，若一棵二叉树上任一结点的平衡因子的绝对值都不大于1,则该树是就平衡二叉树。遍历的概念遍历二叉树指按某条搜索路径访问树中的每个结点，使得每个结点均被访问一次，而且仅被访问一次。由二叉树的递规定义可知，二叉树的3个基本单元组成：根结点、左子树和右子树。因此，若能依次遍历这3部分，便是遍历了整个二叉树。动态平衡技术的概念Adelson-Velskii和Landis提出了一个动态地保持二叉排序树平衡的方法，其基本思想是:在构造二叉排序树的过程中，每当插入一个结点时，首先检查是否因插入而破坏了树的平衡性,如果是因插入结点而破坏了树的

7、平衡性，则找出其中最小不平衡子树，在保持排序树特性的前提下,调整最小不平衡子树中各结点之间的连接关系，以达到新的平衡。通常将这样得到的平衡二叉排序树简称为AVL树。数据结构课程设计为了保证二叉排序树的高度为lgn,从而保证二叉排序树上实现的插入、删除和查找等基本操作的平均时间为O(lgn),在往树中插入或删除结点时，要调整树的形态来保持树的平衡。使之既保持BST性质不变又保证树的高度在任何情况下均为O(lgn),从而确保树上的基本操作在最坏情况下的时间均为O(lgn)。注意：1)任一结点的左右子机勺高度均相同(如满二叉树)，则二叉树是完全平衡的。通常，只要二叉树的高度为O(1gn),就可看作是

8、平衡的。2)平衡的二叉排序树指满足BST性质的平衡二叉树。3)AVL树中任一结点的左、右子树的高度之差的绝对值不超过1。在最坏情况下，n个结点的AVL树的高度约为1.44lgn。而完全平衡的二叉树度高约为lgn,AVL树是接近最优的。最小不平衡子树的概念以离插入结点最近、且平衡因子绝对值大于1的结点作根结点的子树。为了简化讨论，不妨假设二叉排序树的最小不平衡子树的根结点为A,则调整该子树的规律可归纳为下列四种情况：(1) LL型：新结点X插在A的左孩子的左子树里。调整方法见图3(a)。图中以B为轴心，将A结点从B的右上方转到B的右下侧，使A成为B的右孩子。数据结构课程设计(2) RR型：新结点

9、X插在A的右孩子的右子树里。调整方法见图3(b)。图中以B为轴心，将A结点从B的左上方转到B的左下侧，使A成为B的左孩子。(3) LR型：新结点X插在A的左孩子的右子树里。调整方法见图3(c)。分为两步进行：第一步以X为轴心，将B从X的左上方转到X的左下侧，使B成为X的左孩子，X成为A的左孩子。第二步跟LL型一样处理(应以X为轴心)。(4) RL型：新结点X插在A的右孩子的左子树里。调整方法见图3(d)。分为两步进行：第一步以X为轴心，将B从X的右上方转到X的右下侧，使B成为X的右孩子，X成为A的右孩子。第二步跟RR型一样处理(应以X为轴心)。构造算法我们希望由任何初始序列构成的二叉排序树都是

10、AVL树。因为AVL树上任何结点的左右子树的深度之差都不超过1,则可以证明它的深度和logN是同数量级的(其中N为结点数)。由此，它的平均查找长度也是和logN同数量级的。如何使构成的二叉排序树成为平衡树呢？先看一个具体的例子(常见图4)。假设表中关键字序列为(13,24,37,90,53)。空树和1个结点13的树显然都是平衡的二叉树。在插入24之后依是平衡的，只是根结点的平衡因子BF由0变为一1;在继续插入37之后，由于结点13的BF值由一1变成一2,由此出现不平衡现象。此时好比一根扁担出现一头重一头轻的现象，若能将扁担的支撑点由13改成至24,扁担的两头就平衡了。由此，可以对树左一个向左逆

11、时针“旋转”的操作，令结点24为根，而结点13为它的左子树，此时，结点13和24的平衡因子都为0,而且依保持二叉排序树的特性。在继续插入90和53之后，由于结点37的BF值由一1变成一2,排序树中出现了新的不平衡现象，需要调整。当此时由于结点53插在结点90结点的左子树上，因此不能和上作简单调整。对于以结点37为根的子树来说，即要保持二叉排序树的特性，又要平衡，则必须以53作为根结点，而使37为它的左子树的根，90成为它的左子树的根。这好比对树作了两次“旋转”操作一一先向右顺时针，后向左逆日针(见图4(f)(h),使二叉排序树由不平衡转化为平衡。一般情况下，假设由于在二叉排序树上插入结点而失去

12、平衡后进行调整的规律可归纳为最小不平衡子树的概念中提到的4中操作。数据结构课程设计(a)(b)(e)图4平衡二叉树的生成过程(a)空树；(b)插入13;(c)插入24;(d)插入37;(e)向左逆时针右旋转平衡；(f)相继插入90和53;(g)第一次向右顺时针旋转；(h)第二次向左逆时针旋转平衡4种插入中，(1)和(3)对称，(2)和(4)对称。旋转操作的正确性容易由“保持二叉排序树的特性：中序遍历所得关键字序列自小到大有序”证明之。当平衡二叉树因插入或者删除结点而失去平衡时，仅需对最小不平衡子树进行平衡旋转处理即可。因为经过旋转处理之后的子树深度和插入或删除之前相同，因而不影响插入或删除路径

13、上所有祖先结点的平衡。插入结点在平衡二叉排序树BBST上插入一个新数据元素e的递规算法可以描述如下：(1)若BBST为空树，则插入一个数据元素为e的新结点作为BBST的根结点，树的深度增加1;(2)若e的关键字和BBST的根结点的关键字相等，则不进行插入；(3)若e的关键字小于BBST的根结点的关键字，而且在BBST的左子树中不存在和e有相同关键字的结点，则将e插入在BBST勺左子树上，并且当插入之后的左子树深度增加1时，分别就下列情况处理之：1. BBST的根结点的平衡因子为一1(右子树深度大于左子树深度)：则将根结点的平衡因子数据结构课程设计更改为0,BBST勺深度不变；2. BBST的根

14、结点的平衡因子为0（左，右子树深度相等）：则将根结点的平衡因子更改为1,BBST的深度增力口1;3. BBST的根结点的平衡因子为1（左子树深度大于右子树深度）：若BBST的左子树根结点的平衡因子为1,则需要进行单向右旋平衡处理，并且在右旋处理之后将根结点和右子树根结点的平衡因子更改为0,树的深度不变；若BBST的左子树根结点的平衡因子为一1,这需进行先向左后向右的双向旋转平衡处理，并且在旋转处理之后，修改根结点和其左、右子树根结点的平衡因子，树的深度不变；（4）若e的关键字大于BBST的根结点的关键字，而且在BBST的右子树中不存在和e相同关键字的结点，则将e插入在BBST的右子树上，并且当

15、插入之后的右子树深度增加1时，分别就不同情况处理。删除结点删除结点过程与插入结点的操作类似，基本过程是：平衡二叉树-找到要删除的结点-删除一个结点-变成二叉树-旋转-»变回平衡二叉树。具体过程将详细设计中的代码。中序遍历右遍历的定义可知，中序遍历二叉树的递规算法可以定义为：若二叉树为空，则空操作；否则1）中序遍历左子树2）访问根结点3）中序遍历右子树如中序遍历图5的二叉树，结点的访问顺序为：a-b-c-d-e-f-g2、详细设计A.使用的头文件#include<stdlib.h>#include<iostream.h>cout函数要使用数据结构课程设计#inc

16、lude<iomanip.h>/setw函数要使用B.常量定义# defineLH1/左高# defineEH0/等高# defineRH-1/右高# defineTRUE1# defineFALSE0C.全局变量定义inttaller=0;/taller反映T长高与否intshorter=0;/shorter反映T变矮与否D.数据结构定义/根据平衡二叉树特点可以定义平衡二叉树的存储结构二叉排序树的类型定义typedefstructBSTNodeintdata;/结点值intbf;结点的平衡因子structBSTNode*lchild,*rchild;分别指向左右孩子的指针BSTN

17、ode,*BSTree;同时声明一个BSTNode和一个指针类型的*BSTreeE.部分关键函数原型说明voidMidOrder(BSTreeT)/值，不返回值BSTreeR_Rotate(BSTreep)/结点即旋转处理之前的左子树根结点BSTreeL_Rotate(BSTreep)/结点即旋转处理之前的右子树根结点BSTreeLeftBalance(BSTreeT)算法结束时指针T指向新的根结点BSTreeRightBalance(BSTreeT)算法结束时指针T指向新的根结点BSTreeInsertAVL(BSTreeT,inte)BSTreeLeftBalance1(BSTreep)衡

18、旋转处理，本算法结束时指针BSTreeRightBalance1(BSTreep)衡旋转处理，本算法结束时指针树的中序遍历白递归算法，一并输出它的平衡因子和左右结点对以p为根的二叉排序树作右旋处理，处理之p指向新的树根对以p为根的二叉排序树作左旋处理，处理之p指向新的树根/对以指针T所指结点为根的二叉树作左平衡旋转处理，本/对以指针T所指结点为根的二叉树作右平衡旋转处理，本/向平衡树中插入一个结点，返回插入后的新根结点BSTreeDelete(BSTreeq,BSTreer)/删除结点时对以指针T指向新的根结点/删除结点时对以指针T指向新的根结点/对结点进行删除处理,T所指结点为根的二叉树作左

19、平T所指结点为根的二叉树作右平本算法结束时指针q指向新的数据结构课程设计找到要删除的结点，并调用删除函数对其进行删除，本/建立关键字值为nodeValue的新结点，返回根结点根结点BSTreeDeleteAVL(BSTreep,inte)算法结束时指针p指向新的根结点BSTreeCreatNode(intnodeValue)3、程序清单#include<stdlib.h>#include<iostream.h>/cout#include<iomanip.h>/setw# defineLH1/左高# defineEH0/等高# defineRH-1/右高# d

20、efineTRUE1# defineFALSE0inttaller=0;/taller反映T长高与否intshorter=0;/shorter反映T变矮与否二叉排序树的类型定义typedefstructBSTNodeintdata;/结点值intbf;结点的平衡因子structBSTNode*lchild,*rchild;分别指向左右孩子的指针BSTNode,*BSTree;同时声明一个BSTNode和一个指针类型的*BSTree/树的中序遍历的递归算法，一并输出它的平衡因子和左右结点值voidMidOrder(BSTreeT)中序遍历的特点是：当二叉树为空，则空操作；否则/1.中序遍历左子树

21、；/2.访问根结点；/3.中序遍历右子树。if(T->lchild)MidOrder(T->lchild);if(T->data)以适当的形式格式化输出各个结点及其附加信息可以方便用户重构二叉树cout<<setw(4)<<T->data<<setw(6)<<T->bf;if(T->lchild)cout<<setw(8)<<T->lchild->data;elsecout<<setw(8)<<"-"if(T->rchild)

22、cout<<setw(8)<<T->rchild->data;elsecout<<setw(8)<<"-"cout<<endl;if(T->rchild)MidOrder(T->rchild);-10-数据结构课程设计/树的先序遍历的递归算法，一并输出它的平衡因子和左右结点值voidRootOrder(BSTreeT)(先序遍历的特点是：当二叉树为空，则空操作；否则/1.访问根结点；/2.先序遍历左子树；/3.先序遍历右子树。if(T->data)(cout<<setw(4

23、)<<T->data<<setw(6)<<T->bf;if(T->lchild)cout<<setw(8)<<T->lchild->data;elsecout<<setw(8)<<"-"if(T->rchild)cout<<setw(8)<<T->rchild->data;elsecout<<setw(8)<<"-"cout<<endl;)if(T->lchi

24、ld)RootOrder(T->lchild);if(T->rchild)RootOrder(T->rchild);)/对以p为根的树作右旋处理，处理之p指向新的树根结点即旋转处理之前的左子树根结点BSTreeR_Rotate(BSTreep)(BSTNode*lc;声明BSTNode*临时变量lc=p->lchild;/lc指向的*p的左子树根结点p->lchild=lc->rchild;/lc的右子树挂接为*p的左子树lc->rchild=p;p=lc;/p指向新的根结点returnp;返回新的根结点)/对以p为根的树作左旋处理，处理之p指向新的树

25、根结点即旋转处理之前的右子树根结点BSTreeL_Rotate(BSTreep)(BSTNode*rc;声明BSTNode*临时变量rc=p->rchild;/rc指向的*p的右子树根结点p->rchild=rc->lchild;/rc的左子树挂接为*p的右子树rc->lchild=p;p=rc;/p指向新的根结点returnp;返回新的根结点)/对以指针T所指结点为根的二叉树作左平衡旋转处理，本算法结束时指针T指向新的根结点BSTreeLeftBalance(BSTreeT)(BSTNode*lc,*rd;-11-数据结构课程设计lc=T->lchild;/lc

26、指向*T的左子树根结点switch(lc->bf)检查*T的左子树平衡度，并做相应的平衡处理(caseLH:新结点插入在*T的左孩子的左子树上，要做单右旋处理T->bf=lc->bf=EH;T=R_Rotate(T);break;caseRH:新结点插入在*T的左孩子的右子树上，要做双旋处理rd=lc->rchild;/rd指向*T的左孩子的右子树根switch(rd->bf)修改*T及其左孩子的平衡因子(caseLH:T->bf=RH;lc->bf=EH;break;caseEH:T->bf=lc->bf=EH;break;caseRH:

27、T->bf=EH;lc->bf=LH;break;rd->bf=EH;T->lchild=L_Rotate(T->lchild);/X*T的左孩子做左旋平衡处理T=R_Rotate(T);/X*T做右旋处理returnT;/对以指针T所指结点为根的二叉树作右平衡旋转处理，本算法结束时指针T指向新的根结点BSTreeRightBalance(BSTreeT)(BSTreerc,ld;rc=T->rchild;/rc指向*T的右子树根结点switch(rc->bf)检查*T的右子树平衡度，并做相应的平衡处理(caseRH:新结点插入在*T的右孩子的右子树上

28、，要做单右旋处理T->bf=rc->bf=EH;T=L_Rotate(T);break;caseLH:新结点插入在*T的右孩子的左子树上，要做双旋处理ld=rc->lchild;/ld指向*T的右孩子的左子树根switch(ld->bf)修改*T及其右孩子的平衡因子(caseLH:-12-数据结构课程设计T->bf=LH;rc->bf=EH;break;caseEH:T->bf=rc->bf=EH;break;caseRH:T->bf=EH;rc->bf=RH;break;)ld->bf=EH;T->rchild=R_Ro

29、tate(T->rchild);/X*T的右孩子做右旋平衡处理T=L_Rotate(T);/X*T做左旋处理)returnT;)e的新结点，则作平衡旋转/若在平衡的二叉排序树T中不存在和e有相同关键字的结点，则插入一个数据元素为并返回插入后所建成的平衡二叉排序树，否则返回NULL.若因插入而使二叉数失去平衡处理，布尔变量taller反映T长高与否BSTreeInsertAVL(BSTreeT,inte)BSTreep;插入新结点，树长高置taller为TRUEif(!T)T=(BSTree)malloc(sizeof(BSTNode);T->data=e;T->lchild=

30、T->rchild=NULL;T->bf=EH;taller=TRUE;)else/树中存在和e有相同关键字的结点则不再插入if(e=T->data)taller=FALSE;returnNULL;)/值小于则继续在树的左子树中搜索if(e<T->data)p=InsertAVL(T->lchild,e);/插入到左子树且左子树长高if(p)-13-数据结构课程设计T->lchild=p;if(taller)(switch(T->bf)(caseLH:T=LeftBalance(T);taller=FALSE;break;caseEH:树增高T-

31、>bf=LH;taller=TRUE;break;caseRH:T->bf=EH;taller=FALSE;break;继续在*T的右子树中搜索else(/插入到右子树且使右子树长高p=InsertAVL(T->rchild,e);if(P)(T->rchild=p;if(taller)(switch(T->bf)(caseLH:T->bf=EH;taller=FALSE;break;caseEH:树增高T->bf=RH;taller=TRUE;break;caseRH:检查*T的平衡度原本左子树比右子树高，需要做左平衡处理原本左、右子树同高，现因左子

32、树争高而使原本右子树比左子树高，现在左右子树等高检查*T的平衡度原本左子树比右子树高，现在左右子树等高原本左、右子树同高，现因右子树增高而使原本右子树比左子树高，需要做右平衡处理T=RightBalance(T);-14-数据结构课程设计taller=FALSE;break;)returnT;p指向新的根)/删除结点时以指针p所指结点为根的树作左平衡旋转处理，本算法结束时指针结点BSTreeLeftBalance1(BSTreep)(BSTreep1,p2;左子树比右子树高if(p->bf=1)(p->bf=0;shorter=1;)elseif(p->bf=0)(p->

33、;bf=-1;shorter=0;)else(p1=p->rchild;if(p1->bf=0)(p->rchild=p1->lchild;p1->lchild=p;p1->bf=1;p->bf=-1;p=p1;shorter=0;)elseif(p1->bf=-1)(p->rchild=p1->lchild;p1->lchild=p;p1->bf=p->bf=0;p=p1;-15-数据结构课程设计shorter=1;)else(p2=p1->lchild;p1->lchild=p2->rchild

34、;p2->rchild=p1;p->rchild=p2->lchild;p2->lchild=p;if(p2->bf=0)(p->bf=0;p1->bf=0;)elseif(p2->bf=-1)(p->bf=1;p1->bf=0;)else(p->bf=0;p1->bf=-1;)p2->bf=0;p=p2;shorter=1;)returnp;)T指向新删除结点时以指针T所指结点为根的二叉树作右平衡旋转处理，本算法结束时指针的根结点BSTreeRightBalance1(BSTreep)(BSTreep1,p2;if

35、(p->bf=-1)(p->bf=0;shorter=1;)elseif(p->bf=0)(-16-数据结构课程设计p->bf=1;shorter=0;)else(p1=p->lchild;if(p1->bf=0)(p->lchild=p1->rchild;p1->rchild=p;p1->bf=-1;p->bf=1;p=p1;shorter=0;)elseif(p1->bf=1)(p->lchild=p1->rchild;p1->rchild=p;p1->bf=p->bf=0;p=p1;sh

36、orter=1;)else(p2=p1->rchild;p1->rchild=p2->lchild;p2->lchild=p1;p->lchild=p2->rchild;p2->rchild=p;if(p2->bf=0)(p->bf=0;p1->bf=0;)elseif(p2->bf=1)(p->bf=-1;p1->bf=0;)else(p->bf=0;p1->bf=1;-17-数据结构课程设计)p2->bf=0;P=P2；shorter=1;)returnp;)/M结点进行删除处理BSTreeDe

37、lete(BSTreeq,BSTreer)(if(r->rchild=NULL)根结点的右子树为空则将左子树提高并标记树变矮了(q->data=r->data;q=r;r=r->lchild;free(q);shorter=1;)else继续递规搜索并删除(r->rchild=Delete(q,r->rchild);)returnr;)找到要删除的结点，并调用删除函数对其进行删除BSTreeDeleteAVL(BSTreep,inte)(BSTreeq;抛弃空删除if(p=NULL)returnNULL;elseif(e<p->data)/欲删除

38、值小于当前结点值则继续在左子树中搜索(p->lchild=DeleteAVL(p->lchild,e);if(shorter=1)p=LeftBalance1(p);returnp;)elseif(e>p->data)/欲删除值大于当前结点值则继续在右子树中搜索(p->rchild=DeleteAVL(p->rchild,e);if(shorter=1)p=RightBalance1(p);returnp;-18-数据结构课程设计)else找到了(q=p；将p存储到临时变量q里面if(p->rchild=NULL)如果p的右子树为空则将其左子树提高一层

39、(p=p->lchild;free(q);shorter=1;并标记树变矮了)else/如果p的左子树为空则将其右子树提(Wj一'层if(p->lchild=NULL)(p=p->rchild;free(q);shorter=1;)else(将删除后的子树后的得到的新的子树的根结点赋值给q左子树q->lchild=Delete(q,q->lchild);如果树高到变矮了则要执行删除后的左平衡处理if(shorter=1)q=LeftBalance1(q);p=q;)returnp;)/建立新结点BSTreeCreatNode(intnodeValue)(B

40、STreenode;node=(BSTree)malloc(sizeof(BSTree);node->data=nodeValue;node->bf=0;node->lchild=NULL;node->rchild=NULL;returnnode;)/在屏幕打印菜单函数intPrintMenu()(<<endl;intuserChose;cout<<"-19-数据结构课程设计cout<<"1.创建一棵二叉平衡树"<<endl;cout<<"2.向平衡树插入新结点"

41、;<<endl;cout<<"3.从树中删除一个结点"<<endl;cout<<"4.中序遍历输出平衡树"<<endl;cout<<"5.先序遍历输出平衡树"<<endl;cout<<"n.选择其它将退出程序"<<endl;cout<<""<<endl;cout<<"请选择你的操作："；cin>>userChose;ret

42、urnuserChose;新建二叉树函数BSTreeBuildTree(BSTreer)如果传入根结点不为空，则树已构建过，退出函数if(r!=NULL)cout<<"二叉平衡树已经创建！"；returnNULL;根结点为空则开始构建cout<<"请输入结点值，输入零则结束"<<endl;intnodeValue;cin>>nodeValue;while(nodeValue)插入任何不为0的整数值BSTreenode=CreatNode(nodeValue);/如果根为空，则将此结点设置为根结点，否则将此结

43、点作为非根结点插入if(r=NULL)r=node;elser=InsertAVL(r,nodeValue);cin>>nodeValue;/获取用户输入的新值returnr;voidmain()定义一个空根结点BSTreeroot=NULL;/在屏幕打印菜单，让用户选择建立、遍历、插入、删除等功能intuserChoseMenu;inte;while(userChoseMenu=PrintMenu()根据用户不同选择作出不同处理switch(userChoseMenu)-20-数据结构课程设计case 1 :cout<<"你选择了1,请依次输入新树的值，回车

44、输入下一个，遇0结束输入。"<<endl;root=BuildTree(root);break;case 2 :cout<<"你选择了2,请输入要插入的结点值！"<<endl;cin>>e;root=InsertAVL(root,e);break;case 3 :cout<<"你选择了3,请输入要删除的结点值！"<<endl;cin>>e;root=DeleteAVL(root,e);break;case 4 :cout<<"你选择了4,中序遍历输出二叉平衡树。"<<endl;cout<<""<<endl;cout<<"数据"<<"平衡因子"<<"左子树"<<"右子树"<<endl;MidOrder(root);cout&l