平衡二叉樹的生成過程-資料下載頁
2025-04-09 11:42本頁面
【正文】 因子為等高 lcBF=LH。//旋轉(zhuǎn)后，原根結(jié)點(diǎn)的左孩子結(jié)點(diǎn)平衡因子為左高 } rdBF=EH。//旋轉(zhuǎn)后的新結(jié)點(diǎn)的平衡因子為等高 //雙旋轉(zhuǎn)處理 LL_Rotate(Tlchild)。//對T的左子樹左旋轉(zhuǎn)處理 RR_Rotate(T)。//對T作右旋轉(zhuǎn)處理 } }void AVLTree::RightBalance(TreeNode *amp。T)//右平衡處理{//初始條件：原來平衡二叉排序樹T的右子樹比左子樹高，又在右子樹中插入結(jié)點(diǎn)，導(dǎo)致右子樹更高 //操作結(jié)果：對不平衡的樹T作右平衡旋轉(zhuǎn)處理 TreeNode *rc,*ld。 rc=Trchild。 switch(rcBF) { case RH://新結(jié)點(diǎn)插入在T的右孩子的右子樹上，導(dǎo)致右子平衡因子為右高,進(jìn)行左旋轉(zhuǎn)處理 TBF=rcBF=EH。//旋轉(zhuǎn)后，原根結(jié)點(diǎn)和右孩子結(jié)點(diǎn)的平衡因子均為0 LL_Rotate(T)。 break。 case LH://新結(jié)點(diǎn)插入在T的右孩子的左子樹上，導(dǎo)致右子樹的平衡因子為左高，進(jìn)行雙旋處理 ld=rclchild。 switch(ldBF) { case RH://新結(jié)點(diǎn)插入在T的右孩子的左子樹的右子樹上 TBF=LH。//旋轉(zhuǎn)后，原根結(jié)點(diǎn)的平衡因子為左高 rcBF=EH。//旋轉(zhuǎn)后，原根結(jié)點(diǎn)的右孩子結(jié)點(diǎn)平衡因子為等高 break。 case EH://新結(jié)點(diǎn)插入到T的右孩子的左孩子（葉子） TBF=rcBF=EH。//旋轉(zhuǎn)后，原根和右孩子結(jié)點(diǎn)的平衡因子等高 break。 case LH://新結(jié)點(diǎn)插入到T的右孩子的左子樹的左子樹 TBF=EH。//旋轉(zhuǎn)后，原根結(jié)點(diǎn)的平衡因子等高 rcBF=RH。//旋轉(zhuǎn)后，原根結(jié)點(diǎn)的右孩子結(jié)點(diǎn)的平衡因子為右高 } ldBF=EH。//旋轉(zhuǎn)后的新根結(jié)點(diǎn)的平衡因子為等高 //雙旋轉(zhuǎn)處理 RR_Rotate(Trchild)。//對T的右子樹作右旋轉(zhuǎn)處理 LL_Rotate(T)。//對T作左旋轉(zhuǎn)處理 } }int main(){ const char *file=。 AVLTree AVL=AVLTree()。 TreeNode *root=NULL。 int data。 ifstream fin。 (file)。 if(()) { while(1) { findata。 if(data==1)break。 (root,data)。 } } (root)。 coutendlendl。 ()。 return 1。 }
公司管理相關(guān)推薦
鄂ICP備17016276號-1