数据结构第九章 第三节.ppt

1、平衡二叉树,(AVL树),（1）它左子树和右子树都是平衡二叉树,（2）左子树和右子树的深度之差的绝对值不超过1,定义: 平衡二叉树或者是一棵空树；或者是具有下列性质的排序二叉树,平衡因子=Height(T-lchild) - Height(T-rchild),俄国数学家 G.M.Adelson-Velskii 和 E.M. Landis, 1962年,1,1,0,0,-1,1,-1,0,1,0,2,-1,0,0,1,0,-1,0,-2,0,0,1,0,0,(13, 24, 37, 90, 53),平衡二叉树的生成过程,24,90,53,A,B,A,0,1,BL,BR,h,AR,h,h,LL平衡

2、旋转,单向右旋,树深度不变,树及右子树为平衡树,B,A,0,-1,BL,BR,h,AL,h,h,RR平衡旋转,A,单向左旋,树深度不变,树及左子树为平衡树,B,A,0,1,BL,h,AR,h,LR平衡旋转,C,0,C,CR,CL,h-1,A,B,A,0,-1,BR,h,AL,h,RL平衡旋转,C,0,CR,CL,h-1,A,C,B,A,0,1,BL,BR,h,AR,h,h,B,A,0,-1,BL,BR,h,AL,h,h,B,A,0,1,BL,h,AR,h,C,0,CR,CL,h-1,B,A,0,-1,BR,h,AL,h,C,0,CR,CL,h-1,LL,RR,LR,RL,1,2,-1,-2,1

3、,2,-1,-1,-2,1,LL,(13, 24, 37, 90, 53),平衡二叉树的生成过程,24,90,53,45, 24, 53, 45, 12, 24, 90, 99, 64, 72, 20,练习,根据下列序列构造平衡二叉树,45, 24, 53, 45, 12, 24, 90, 99, 64, 72, 20,平衡二叉树的生成过程,45, 24, 53, 45, 12, 24, 90, 99, 64, 72, 20,平衡二叉树的生成过程,45,45, 24, 53, 45, 12, 24, 90, 99, 64, 72, 20,平衡二叉树的生成过程,45,45, 24, 53, 45

4、, 12, 24, 90, 99, 64, 72, 20,平衡二叉树的生成过程,45,45, 24, 53, 45, 12, 24, 90, 99, 64, 72, 20,平衡二叉树的生成过程,45,45, 24, 53, 45, 12, 24, 90, 99, 64, 72, 20,平衡二叉树的生成过程,45,45, 24, 53, 45, 12, 24, 90, 99, 64, 72, 20,平衡二叉树的生成过程,45,45, 24, 53, 45, 12, 24, 90, 99, 64, 72, 20,平衡二叉树的生成过程,45,45, 24, 53, 45, 12, 24, 90, 9

5、9, 64, 72, 20,平衡二叉树的生成过程,45,45, 24, 53, 45, 12, 24, 90, 99, 64, 72, 20,平衡二叉树的生成过程,45,45, 24, 53, 45, 12, 24, 90, 99, 64, 72, 20,平衡二叉树的生成过程,45,45, 24, 53, 45, 12, 24, 90, 99, 64, 72, 20,平衡二叉树的生成过程,45,45, 24, 53, 45, 12, 24, 90, 99, 64, 72, 20,平衡二叉树的生成过程,45,45, 24, 53, 45, 12, 24, 90, 99, 64, 72, 20,平

6、衡二叉树的生成过程,45,24,90,45, 24, 53, 45, 12, 24, 90, 99, 64, 72, 20,平衡二叉树的生成过程,45,20,90,45, 24, 53, 45, 12, 24, 90, 99, 64, 72, 20,平衡二叉树的生成过程,45,20,90,1,-1,0,-1,2,-2,插入80,45, 24, 53, 45, 12, 24, 90, 99, 64, 72, 20,平衡二叉树的生成过程,45,20,90,1,-1,0,-1,2,-2,LR,72,插入80,45, 24, 53, 45, 12, 24, 90, 99, 64, 72, 20,平衡二

7、叉树的生成过程,45,20,-1,72,插入80,0,1,插入75,1,-1,-2,45, 24, 53, 45, 12, 24, 90, 99, 64, 72, 20,平衡二叉树的生成过程,45,20,72,90,64,插入80,插入75,A,B,A,0,1,BL,BR,h,AR,h,h,LL平衡旋转,lc=p-lchild,p-lchild=lc-rchild,lc-rchild=p,A,LL,void R_Rotate(BSTree /p指向新的根结点 ,LL平衡旋转,A,void R_Rotate(BSTree /p指向新的根结点 ,p,p,LL,A,B,A,BL,BR,AR,h+1,

8、h,h,0,0,void R_Rotate(BSTree /p指向新的根结点 ,p,lc,p,lc,LL,A,B,A,BL,BR,AR,h+1,h,h,0,0,void R_Rotate(BSTree /p指向新的根结点 ,p,lc,p,lc,LL,A,B,A,BL,BR,AR,h+1,h,h,0,0,void R_Rotate(BSTree /p指向新的根结点 ,p,lc,lc,LL,B,A,0,-1,BL,BR,h,AL,h,h,RR平衡旋转,A,rc=p-rchild,p-rchild=rc-lchild,rc-lchild=p,RR平衡旋转,A,RR,void L_Rotate(BST

9、ree /p指向新的根结点 ,RR平衡旋转,A,void L_Rotate(BSTree /p指向新的根结点 ,RR,RR平衡旋转,A,B,A,BR,AL,BL,h+1,h,h,0,0,void L_Rotate(BSTree /p指向新的根结点 ,RR,RR平衡旋转,A,B,A,BR,AL,BL,h+1,h,h,0,0,void L_Rotate(BSTree /p指向新的根结点 ,RR,RR平衡旋转,A,B,A,BR,AL,BL,h+1,h,h,0,0,void L_Rotate(BSTree /p指向新的根结点 ,RR,C,A,B,A,-1,BL,CR,h,AR,h,h-1,CL,1,h

10、,2,C,LR平衡旋转,LR平衡旋转,C,A,B,A,-1,BL,CR,h,AR,h,h-1,CL,1,h,2,C,lc=p-lchild,rd=lc-rchild,lc-rchild=rd-lchild,rd-lchild=lc,lc=rd,L-Rotate(p-lchild),LR平衡旋转,C,A,B,A,BL,CR,h,AR,h,h-1,CL,1,h,2,C,lc=p-lchild,rd=lc-lchild,L-Rotate(p-lchild),lc-rchild=p,p-lchild= lc-rchild,p=lc,R-Rotate(p),-1,LR平衡旋转,C,A,B,A,BL,CR

11、,h,AR,h,h-1,CL,1,h,2,C,lc=p-lchild,rd=lc-lchild,L-Rotate(p-lchild),R-Rotate(p),-1,B,1,2,BL,BR,h+1,AR,h,h,B,A,A,B,A,BL,BR,AR,h+1,h,h,0,0,LL,C,LR,A,B,-1,-2,BL,BR,h,AL,h,h+1,A,RR,h,B,A,1,-2,BR,h,AL,h,1,CR,CL,h-1,C,C,RL,typedef struct BSTNode ElemType data; int bf; /结点的平衡因子 BSTNode *lchild,*rchild; /左、右

12、孩子指针 BSTNode, *BSTree;,#define LH +1 / 左高 #define EH 0 / 等高 #define RH -1 / 右高,void LeftBalance(BSTree ,B,1,2,BL,BR,h+1,AR,h,h,B,A,A,B,A,BL,BR,AR,h+1,h,h,0,0,LL,case RH: / 新结点插入在T的左孩子的右子树上，要作双旋处理 rd=lc-rchild; / rd指向T的左孩子的右子树根 switch(rd-bf) / 修改T及其左孩子的平衡因子 case LH: T-bf=RH; lc-bf=EH; break; case EH:

13、 T-bf=lc-bf=EH; break; case RH: T-bf=EH; lc-bf=LH; break; /switch(rd-bf) rd-bf=EH; L_Rotate(T-lchild); R_Rotate(T); /switch(lc-bf) ,C,LR,case RH: / 新结点插入在T的左孩子的右子树上，要作双旋处理 rd=lc-rchild; / rd指向T的左孩子的右子树根 switch(rd-bf) / 修改T及其左孩子的平衡因子 case LH: T-bf=RH; lc-bf=EH; break; case EH: T-bf=lc-bf=EH; break; c

14、ase RH: T-bf=EH; lc-bf=LH; break; /switch(rd-bf) rd-bf=EH; L_Rotate(T-lchild); R_Rotate(T); /switch(lc-bf) ,C,LR,case RH: / 新结点插入在T的左孩子的右子树上，要作双旋处理 rd=lc-rchild; / rd指向T的左孩子的右子树根 switch(rd-bf) / 修改T及其左孩子的平衡因子 case LH: T-bf=RH; lc-bf=EH; break; case EH: T-bf=lc-bf=EH; break; case RH: T-bf=EH; lc-bf=L

15、H; break; /switch(rd-bf) rd-bf=EH; L_Rotate(T-lchild); R_Rotate(T); /switch(lc-bf) ,C,LR,case RH: / 新结点插入在T的左孩子的右子树上，要作双旋处理 rd=lc-rchild; / rd指向T的左孩子的右子树根 switch(rd-bf) / 修改T及其左孩子的平衡因子 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; /switch(rd-bf)

16、 rd-bf=EH; L_Rotate(T-lchild); R_Rotate(T); /switch(lc-bf) ,C,LR,case RH: / 新结点插入在T的左孩子的右子树上，要作双旋处理 rd=lc-rchild; / rd指向T的左孩子的右子树根 switch(rd-bf) / 修改T及其左孩子的平衡因子 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; /switch(rd-bf) rd-bf=EH; L_Rotate(T-lc

17、hild); R_Rotate(T); /switch(lc-bf) ,C,B,A,-1,BL,CR,h,AR,h,h,CL,0,h,2,C,C,A,BL,AR,h,0,0,B,h,0,LR,CR,CL,case RH: / 新结点插入在T的左孩子的右子树上，要作双旋处理 rd=lc-rchild; / rd指向T的左孩子的右子树根 switch(rd-bf) / 修改T及其左孩子的平衡因子 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; /

18、switch(rd-bf) rd-bf=EH; L_Rotate(T-lchild); R_Rotate(T); /switch(lc-bf) ,C,B,A,-1,BL,CR,h,AR,h,h-1,CL,1,h,2,C,C,A,BL,AR,h,0,0,B,CL,h,CR,1,LR,h,case RH: / 新结点插入在T的左孩子的右子树上，要作双旋处理 rd=lc-rchild; / rd指向T的左孩子的右子树根 switch(rd-bf) / 修改T及其左孩子的平衡因子 case LH: T-bf=RH; lc-bf=EH; break; case EH: T-bf=lc-bf=EH; br

19、eak; case RH: T-bf=EH; lc-bf=LH; break; /switch(rd-bf) rd-bf=EH; L_Rotate(T-lchild); R_Rotate(T); /switch(lc-bf) ,C,B,A,-1,BL,CR,h,AR,h,h-1,CL,1,h,2,C,C,A,BL,AR,h,0,0,B,CL,h,CR,1,LR,h,Status InsertAVL(BSTree / 否则，应继续在*T的左子树中进行搜索,if LT(e.key, T-data.key) / 应继续在T的左子树中进行搜索 if(!InsertAVL(T-lchild,e,tall

20、er) return FALSE; / 未插入 if(taller) /已插入到T的左子树中且左子树“长高” switch(T-bf) / 检查T的平衡度 case LH: /原本左子树比右子树高，需要作左平衡处理 LeftBalance(T); taller=FALSE; break; case EH: /原本左、右子树等高，现因左子树增高而使树增高 T-bf=LH; taller=TRUE; break; case RH: T-bf=EH; /原本右子树比左子树高，现左、右子树等高 taller=FALSE; break; else(转下页) / 应继续在*T的右子树中进行搜索,BL,BR

21、,B,T,h,A,AR,if LT(e.key, T-data.key) / 应继续在T的左子树中进行搜索 if(!InsertAVL(T-lchild,e,taller) return FALSE; / 未插入 if(taller) /已插入到T的左子树中且左子树“长高” switch(T-bf) / 检查T的平衡度 case LH: /原本左子树比右子树高，需要作左平衡处理 LeftBalance(T); taller=FALSE; break; case EH: /原本左、右子树等高，现因左子树增高而使树增高 T-bf=LH; taller=TRUE; break; case RH: T

22、-bf=EH; /原本右子树比左子树高，现左、右子树等高 taller=FALSE; break; else(转下页) / 应继续在*T的右子树中进行搜索,BL,BR,B,T,h,A,AR,if LT(e.key, T-data.key) / 应继续在T的左子树中进行搜索 if(!InsertAVL(T-lchild,e,taller) return FALSE; / 未插入 if(taller) /已插入到T的左子树中且左子树“长高” switch(T-bf) / 检查T的平衡度 case LH: /原本左子树比右子树高，需要作左平衡处理 LeftBalance(T); taller=FAL

23、SE; break; case EH: /原本左、右子树等高，现因左子树增高而使树增高 T-bf=LH; taller=TRUE; break; case RH: T-bf=EH; /原本右子树比左子树高，现左、右子树等高 taller=FALSE; break; else(转下页) / 应继续在T的右子树中进行搜索,BL,BR,B,T,h,A,1,AR,if LT(e.key, T-data.key) / 应继续在T的左子树中进行搜索 if(!InsertAVL(T-lchild,e,taller) return FALSE; / 未插入 if(taller) /已插入到T的左子树中且左子树

24、“长高” switch(T-bf) / 检查T的平衡度 case LH: /原本左子树比右子树高，需要作左平衡处理 LeftBalance(T); taller=FALSE; break; case EH: /原本左、右子树等高，现因左子树增高而使树增高 T-bf=LH; taller=TRUE; break; case RH: T-bf=EH; /原本右子树比左子树高，现左、右子树等高 taller=FALSE; break; else(转下页) / 应继续在T的右子树中进行搜索,BL,BR,B,T,h,A,1,AR,if LT(e.key, T-data.key) / 应继续在T的左子树中

25、进行搜索 if(!InsertAVL(T-lchild,e,taller) return FALSE; / 未插入 if(taller) /已插入到T的左子树中且左子树“长高” switch(T-bf) / 检查T的平衡度 case LH: /原本左子树比右子树高，需要作左平衡处理 LeftBalance(T); taller=FALSE; break; case EH: /原本左、右子树等高，现因左子树增高而使树增高 T-bf=LH; taller=TRUE; break; case RH: T-bf=EH; /原本右子树比左子树高，现左、右子树等高 taller=FALSE; break;

26、 else(转下页) / 应继续在T的右子树中进行搜索,BL,BR,B,T,h,A,1,AR,if LT(e.key, T-data.key) / 应继续在T的左子树中进行搜索 if(!InsertAVL(T-lchild,e,taller) return FALSE; / 未插入 if(taller) /已插入到T的左子树中且左子树“长高” switch(T-bf) / 检查T的平衡度 case LH: /原本左子树比右子树高，需要作左平衡处理 LeftBalance(T); taller=FALSE; break; case EH: /原本左、右子树等高，现因左子树增高而使树增高 T-bf

27、=LH; taller=TRUE; break; case RH: T-bf=EH; /原本右子树比左子树高，现左、右子树等高 taller=FALSE; break; else(转下页) / 应继续在T的右子树中进行搜索,BL,BR,B,T,h,A,0,AR,if LT(e.key, T-data.key) / 应继续在T的左子树中进行搜索 if(!InsertAVL(T-lchild,e,taller) return FALSE; / 未插入 if(taller) /已插入到T的左子树中且左子树“长高” switch(T-bf) / 检查T的平衡度 case LH: /原本左子树比右子树高

28、，需要作左平衡处理 LeftBalance(T); taller=FALSE; break; case EH: /原本左、右子树等高，现因左子树增高而使树增高 T-bf=LH; taller=TRUE; break; case RH: T-bf=EH; /原本右子树比左子树高，现左、右子树等高 taller=FALSE; break; else(转下页) / 应继续在T的右子树中进行搜索,BL,BR,B,T,h,A,0,1,AR,if LT(e.key, T-data.key) / 应继续在T的左子树中进行搜索 if(!InsertAVL(T-lchild,e,taller) return F

29、ALSE; / 未插入 if(taller) /已插入到T的左子树中且左子树“长高” switch(T-bf) / 检查T的平衡度 case LH: /原本左子树比右子树高，需要作左平衡处理 LeftBalance(T); taller=FALSE; break; case EH: /原本左、右子树等高，现因左子树增高而使树增高 T-bf=LH; taller=TRUE; break; case RH: T-bf=EH; /原本右子树比左子树高，现左、右子树等高 taller=FALSE; break; else(转下页) / 应继续在T的右子树中进行搜索,BL,BR,B,T,h,A,-1,A

30、R,if LT(e.key, T-data.key) / 应继续在T的左子树中进行搜索 if(!InsertAVL(T-lchild,e,taller) return FALSE; / 未插入 if(taller) /已插入到T的左子树中且左子树“长高” switch(T-bf) / 检查T的平衡度 case LH: /原本左子树比右子树高，需要作左平衡处理 LeftBalance(T); taller=FALSE; break; case EH: /原本左、右子树等高，现因左子树增高而使树增高 T-bf=LH; taller=TRUE; break; case RH: T-bf=EH; /原

31、本右子树比左子树高，现左、右子树等高 taller=FALSE; break; else(转下页) / 应继续在T的右子树中进行搜索,BL,BR,B,T,h,A,-1,0,AR,else / 应继续在T的右子树中进行搜索 if(!InsertAVL(T-rchild,e,taller) return FALSE; / 未插入 if(taller) /已插入到T的右子树且右子树“长高” switch(T-bf) /检查T的平衡度 case LH: /原本左子树比右子树高，现左、右子树等高 T-bf=EH; taller=FALSE; break; case EH: /原本左、右子树等高，现因右子

32、树增高而使树增高 T-bf=RH; taller=TRUE; break; case RH: /原本右子树比左子树高，需要作右平衡处理 RightBalance(T); taller=FALSE; / switch(T-bf) / if(taller) /else return TRUE; ,BL,BR,B,T,h,A,1,AL,else / 应继续在T的右子树中进行搜索 if(!InsertAVL(T-rchild,e,taller) return FALSE; / 未插入 if(taller) /已插入到T的右子树且右子树“长高” switch(T-bf) /检查T的平衡度 case LH

33、: /原本左子树比右子树高，现左、右子树等高 T-bf=EH; taller=FALSE; break; case EH: /原本左、右子树等高，现因右子树增高而使树增高 T-bf=RH; taller=TRUE; break; case RH: /原本右子树比左子树高，需要作右平衡处理 RightBalance(T); taller=FALSE; / switch(T-bf) / if(taller) /else return TRUE; ,BL,BR,B,T,h,A,1,AL,else / 应继续在T的右子树中进行搜索 if(!InsertAVL(T-rchild,e,taller) re

34、turn FALSE; / 未插入 if(taller) /已插入到T的右子树且右子树“长高” switch(T-bf) /检查T的平衡度 case LH: /原本左子树比右子树高，现左、右子树等高 T-bf=EH; taller=FALSE; break; case EH: /原本左、右子树等高，现因右子树增高而使树增高 T-bf=RH; taller=TRUE; break; case RH: /原本右子树比左子树高，需要作右平衡处理 RightBalance(T); taller=FALSE; / switch(T-bf) / if(taller) /else return TRUE;

35、,BL,BR,B,T,h,A,1,AL,else / 应继续在T的右子树中进行搜索 if(!InsertAVL(T-rchild,e,taller) return FALSE; / 未插入 if(taller) /已插入到T的右子树且右子树“长高” switch(T-bf) /检查T的平衡度 case LH: /原本左子树比右子树高，现左、右子树等高 T-bf=EH; taller=FALSE; break; case EH: /原本左、右子树等高，现因右子树增高而使树增高 T-bf=RH; taller=TRUE; break; case RH: /原本右子树比左子树高，需要作右平衡处理 R

36、ightBalance(T); taller=FALSE; / switch(T-bf) / if(taller) /else return TRUE; ,BL,BR,B,T,h,A,1,AL,else / 应继续在T的右子树中进行搜索 if(!InsertAVL(T-rchild,e,taller) return FALSE; / 未插入 if(taller) /已插入到T的右子树且右子树“长高” switch(T-bf) /检查T的平衡度 case LH: /原本左子树比右子树高，现左、右子树等高 T-bf=EH; taller=FALSE; break; case EH: /原本左、右子

37、树等高，现因右子树增高而使树增高 T-bf=RH; taller=TRUE; break; case RH: /原本右子树比左子树高，需要作右平衡处理 RightBalance(T); taller=FALSE; / switch(T-bf) / if(taller) /else return TRUE; ,BL,BR,B,T,h,A,1,AL,else / 应继续在T的右子树中进行搜索 if(!InsertAVL(T-rchild,e,taller) return FALSE; / 未插入 if(taller) /已插入到T的右子树且右子树“长高” switch(T-bf) /检查T的平衡度

38、 case LH: /原本左子树比右子树高，现左、右子树等高 T-bf=EH; taller=FALSE; break; case EH: /原本左、右子树等高，现因右子树增高而使树增高 T-bf=RH; taller=TRUE; break; case RH: /原本右子树比左子树高，需要作右平衡处理 RightBalance(T); taller=FALSE; / switch(T-bf) / if(taller) /else return TRUE; ,BL,BR,B,T,h,A,1,AL,0,else / 应继续在T的右子树中进行搜索 if(!InsertAVL(T-rchild,e,

39、taller) return FALSE; / 未插入 if(taller) /已插入到T的右子树且右子树“长高” switch(T-bf) /检查T的平衡度 case LH: /原本左子树比右子树高，现左、右子树等高 T-bf=EH; taller=FALSE; break; case EH: /原本左、右子树等高，现因右子树增高而使树增高 T-bf=RH; taller=TRUE; break; case RH: /原本右子树比左子树高，需要作右平衡处理 RightBalance(T); taller=FALSE; / switch(T-bf) / if(taller) /else ret

40、urn TRUE; ,BL,BR,B,T,h,A,0,AL,else / 应继续在T的右子树中进行搜索 if(!InsertAVL(T-rchild,e,taller) return FALSE; / 未插入 if(taller) /已插入到T的右子树且右子树“长高” switch(T-bf) /检查T的平衡度 case LH: /原本左子树比右子树高，现左、右子树等高 T-bf=EH; taller=FALSE; break; case EH: /原本左、右子树等高，现因右子树增高而使树增高 T-bf=RH; taller=TRUE; break; case RH: /原本右子树比左子树高，

41、需要作右平衡处理 RightBalance(T); taller=FALSE; / switch(T-bf) / if(taller) /else return TRUE; ,BL,BR,B,T,h,A,0,AL,1,else / 应继续在T的右子树中进行搜索 if(!InsertAVL(T-rchild,e,taller) return FALSE; / 未插入 if(taller) /已插入到T的右子树且右子树“长高” switch(T-bf) /检查T的平衡度 case LH: /原本左子树比右子树高，现左、右子树等高 T-bf=EH; taller=FALSE; break; case

42、 EH: /原本左、右子树等高，现因右子树增高而使树增高 T-bf=RH; taller=TRUE; break; case RH: /原本右子树比左子树高，需要作右平衡处理 RightBalance(T); taller=FALSE; / switch(T-bf) / if(taller) /else return TRUE; ,BL,BR,B,T,h,A,-1,AL,else / 应继续在T的右子树中进行搜索 if(!InsertAVL(T-rchild,e,taller) return FALSE; / 未插入 if(taller) /已插入到T的右子树且右子树“长高” switch(T

43、-bf) /检查T的平衡度 case LH: /原本左子树比右子树高，现左、右子树等高 T-bf=EH; taller=FALSE; break; case EH: /原本左、右子树等高，现因右子树增高而使树增高 T-bf=RH; taller=TRUE; break; case RH: /原本右子树比左子树高，需要作右平衡处理 RightBalance(T); taller=FALSE; / switch(T-bf) / if(taller) /else return TRUE; ,BL,BR,B,T,h,A,-1,AL,-2,else / 应继续在T的右子树中进行搜索 if(!Insert

44、AVL(T-rchild,e,taller) return FALSE; / 未插入 if(taller) /已插入到T的右子树且右子树“长高” switch(T-bf) /检查T的平衡度 case LH: /原本左子树比右子树高，现左、右子树等高 T-bf=EH; taller=FALSE; break; case EH: /原本左、右子树等高，现因右子树增高而使树增高 T-bf=RH; taller=TRUE; break; case RH: /原本右子树比左子树高，需要作右平衡处理 RightBalance(T); taller=FALSE; / switch(T-bf) / if(ta

45、ller) /else return TRUE; ,BL,BR,B,T,h,A,1,AL,平衡二叉树的查找分析,n,hmax=?,h,nmin =?,0,0,1,1,2,2,3,4,4,45,12,53,5,37,61,24,99,47,7,Nh=Nh-1+Nh-2+1,h,Nh ?,Nh=Nh-1+Nh-2+1,Nh=Fh+2 - 1,Nh=Fh+2 - 1,含有n个结点的平衡二叉树的最大深度,思考题,45,12,53,5,37,61,24,99,90,78,（3）如何判定一棵给定的二叉树是否是平衡二叉树,写出相应的算法,（1）如何输出二叉树排序树中的最大元素和最小元素？ （2）如何判定一棵

46、给定的二叉树是否是排序二叉树，写出相应的算法,思考题,Status JudgeBBST(BiTree T) if(!T) return 1; else a=JudgeBBST(T-lchild); b=JudgeBBST(T-rchild); k=BiTreeDepth(T-lchild) - BiTreeDepth(T-rchild); if(a=1 /else /JudgeBBST,思考题,int PingHeng (BiTree T) if(flag=YES) if(T=NULL) return 0; else l=PingHeng(T-lchild); r=PingHeng(T-rch

47、ild); if(abs(l-r) flag=NO; else flag=YES; return max(l,r)+1; return -1; /else else return -1; /else /PingHeng,flag为全局变量， 调用函数PingHeng(root, flag)后， 如果 flag=Yes, 则为平衡二叉树。,思考题,int JudgeBST (BiTree bt) int b1, b2; if(bt=NULL) return 1; else b1=JudgeBST(bt-lchild); if(b1=0| predt=bt-data) return 0; pred

48、t=bt-data; b2=JudgeBST(bt-rchild); return b2; ,predt为保存当前结点中序遍历的前趋值,故只要始终保持前一个元素的值比后一个元素的值大，即可判断这是一棵平衡二叉树。,45,12,53,5,37,61,24,99,90,78,思考题,45,12,53,5,37,61,24,99,90,78,int IsSortBiTree(BSTree T, int ,思考题,45,12,53,5,37,61,24,99,90,78,int IsAVL_Tree(BSTree T, int ,思考题,45,12,53,5,37,61,24,99,90,78,fla

49、g(1) = 1,1,int IsAVL_Tree(BSTree T, int ,思考题,45,12,53,5,37,61,24,99,90,78,T(1),flag(1) = 1,1,int IsAVL_Tree(BSTree T, int ,思考题,45,12,53,5,37,61,24,99,90,78,T(1),flag(1) = 1,1,int IsAVL_Tree(BSTree T, int ,思考题,45,12,53,5,37,61,24,99,90,78,T(1),flag(1) = 1,1,int IsAVL_Tree(BSTree T, int ,h1(1) = ?,h2(

50、1) =?,思考题,45,12,53,5,37,61,24,99,90,78,T(1),flag(2) = 1,2,int IsAVL_Tree(BSTree T, int ,h1(2) = ?,h2(2) =?,思考题,45,12,53,5,37,61,24,99,90,78,T(1),flag(2) = 1,2,T(2),int IsAVL_Tree(BSTree T, int ,h1(2) = ?,h2(2) =?,思考题,45,12,53,5,37,61,24,99,90,78,T(1),flag(2) = 1,2,T(2),int IsAVL_Tree(BSTree T, int ,

51、h1(2) = ?,h2(2) =?,思考题,45,12,53,5,37,61,24,99,90,78,T(1),flag(2) = 1,2,T(2),int IsAVL_Tree(BSTree T, int ,h1(2) = ?,h2(2) =?,思考题,flag(3) = 1,3,int IsAVL_Tree(BSTree T, int ,45,12,53,5,37,61,24,99,90,78,T(1),T(2),h1(3) = ?,h2(3) =?,思考题,45,12,53,5,37,61,24,99,90,78,T(1),flag(3) = 1,3,T(2),T(3),int IsAVL_Tree(BSTree T, int ,h1(3) = ?,h2(3) =?,思考题,45,12,53,5,37,61,24,99,90,78,T(1),flag(3) = 1,3,T(2),T(3),int IsAVL_Tree(BSTree T, int ,h1(3) = ?,h2(3) =?,思考题,45,12,53,5,37,61,24,99,90,78,T(1),flag(3) = 1,3,T(2),T(3),i