平衡二叉樹的生成過程(存儲版)
【正文】 =r。}void AVLTree::RL_Rotate(TreeNode *amp。 p=rlchild。//旋轉(zhuǎn)后，原根結(jié)點和左孩子結(jié)點平衡因子都 為0 RR_Rotate(T)。 case RH://新結(jié)點插入在T的左孩子的右子樹的右子樹上 TBF=EH。 switch(rcBF) { case RH://新結(jié)點插入在T的右孩子的右子樹上，導(dǎo)致右子平衡因子為右高,進行左旋轉(zhuǎn)處理 TBF=rcBF=EH。//旋轉(zhuǎn)后，原根和右孩子結(jié)點的平衡因子等高 break。 TreeNode *root=NULL。 coutendlendl。 (root,data)。//對T作左旋轉(zhuǎn)處理 } }int main(){ const char *file=。//旋轉(zhuǎn)后，原根結(jié)點的右孩子結(jié)點平衡因子為等高 break。T)//右平衡處理{//初始條件：原來平衡二叉排序樹T的右子樹比左子樹高，又在右子樹中插入結(jié)點，導(dǎo)致右子樹更高 //操作結(jié)果：對不平衡的樹T作右平衡旋轉(zhuǎn)處理 TreeNode *rc,*ld。 case EH://新結(jié)點插入到T的左孩子的右孩子（葉子） TBF=lcBF=EH。 lc=Tlchild。//最小失衡樹的根結(jié)點進行左旋轉(zhuǎn) }void AVLTree::LR_Rotate(TreeNode *amp。 prchild=r。 p=rrchild。 break。//對樹進行左平衡處理 break。root,int data){ if(root==NULL) { root=(TreeNode*)malloc(sizeof(TreeNode))。}int AVLTree::GetHeight(TreeNode *root){ int len。r)。r)。 TreeNode *rchild。（4）RL型RL型：插入位置為右子樹的左孩子，進行兩次調(diào)整，先右旋轉(zhuǎn)調(diào)整為RR型，再左旋轉(zhuǎn)，從RR型調(diào)整到平衡二叉樹；處理情況與LR類似。當(dāng)失去平衡的最小子樹被調(diào)整為平衡子樹后，原有其他所有不平衡子樹無需調(diào)整，整個二叉排序樹就又成為一棵平衡二叉樹（1）插入點位置必須滿足二叉查找樹的性質(zhì)，即任意一棵子樹的左結(jié)點都小于根結(jié)點，右結(jié)點大于根結(jié)點（2）找出插入結(jié)點后不平衡的最小二叉樹進行調(diào)整，如果是整個樹不平衡，才進行整個樹的調(diào)整。平衡二叉樹又稱為AVL樹，它或者是一棵空樹，或者是有下列性質(zhì)的二叉樹：它的左子樹和右子樹都是平衡二叉樹，且左右子樹的深度之差的絕對值不超過1。（2）RR型RR型：插入位置為右子樹的右孩子，進行向左旋轉(zhuǎn)由于在A的右子樹C的右子樹插入了結(jié)點F，A的平衡因子由1變?yōu)?，成為不平衡的最小二叉樹根結(jié)點。
公司管理相關(guān)推薦
鄂ICP備17016276號-1