《大话数据结构》P336页左平衡旋转处理代码的疑惑,该如何处理
《大话数据结构》P336页左平衡旋转处理代码的疑惑
先上代码,问题就在★标示的地方
请看下面的插图,不知道是我想错了还是书的问题,请大家指正!
------解决方案--------------------
图没有画错,程序自己再调下吧
AVL树我喜欢用维斯数据结构里的代码,用Height表示层次高度
先上代码,问题就在★标示的地方
- C/C++ code
/* 对以指针T所指结点为根的二叉树作左平衡旋转处理 */ /* 本算法结束时,指针T指向新的根结点 */ void LeftBalance(BiTree *T) { BiTree L,Lr; L=(*T)->lchild; /* L指向T的左子树根结点 */ switch(L->bf) { /* 检查T的左子树的平衡度,并作相应平衡处理 */ case LH: /* 新结点插入在T的左孩子的左子树上,要作单右旋处理 */ (*T)->bf=L->bf=EH; R_Rotate(T); break; case RH: /* 新结点插入在T的左孩子的右子树上,要作双旋处理 */ Lr=L->rchild; /* Lr指向T的左孩子的右子树根 */ switch(Lr->bf) { /* 修改T及其左孩子的平衡因子 */ case LH: (*T)->bf=RH; //★这里我觉得有问题,我觉得(*T)->bf=EH L->bf=EH; break; case EH: (*T)->bf=L->bf=EH; break; case RH: (*T)->bf=EH; L->bf=LH; break; } Lr->bf=EH; L_Rotate(&(*T)->lchild); /* 对T的左子树作左旋平衡处理 */ R_Rotate(T); /* 对T作右旋平衡处理 */ } }
请看下面的插图,不知道是我想错了还是书的问题,请大家指正!
------解决方案--------------------
图没有画错,程序自己再调下吧
AVL树我喜欢用维斯数据结构里的代码,用Height表示层次高度