Java源码集合类TreeMap学习1——数据结构4平衡二叉树创建代码

﹏ヽ暗。殇╰゛Y 2022-06-16 11:29 145阅读 0赞

平衡二叉排序树上插入一个新的元素递归[算法][Link 1]，还是比较复杂的，特别是代码的实现上想要理解还是要动手去一步步去手动执行代码。个人理解这个算法和看示例代码也是费了很大一番功夫，理解程度上还是初级阶段。总之还是要自己去多实践才能更好理解。

#include<stdio.h>
    #include<malloc.h>  
      
    #define OK 1  
    #define ERROR 0  
    #define OVERFLOW -1
    #define LH +1   // 左高   
    #define EH 0    // 等高   
    #define RH -1   // 右高     
    
    typedef int Status;  
    typedef int TElemType;  
      
    typedef struct BSTNode{  
        TElemType data;	//数据域  
    	int 	  bf;	//结点的平衡因子
        struct BSTNode *lchild, *rchild;//左右孩子指针  
    
    }BSTNode, *BSTree;
    
    //右旋
    void R_Rotate(BSTree &p);
    //左旋
    void L_Rotate(BSTree &p);
    //左平衡处理
    void LeftBalance(BSTree &T);
    //右平衡处理
    void RightBalance(BSTree &T);
    //二叉平衡树插入一个新的元素
    int InsertAVL(BSTree &T, TElemType e, bool &taller);
    //先序遍历二叉树的各个结点  
    Status PreOrderTraverse(BSTree T, Status(* Visit)(TElemType e)); 
    //打印输出结点数据
    Status Visit(TElemType e); 
    
    int main()
    {
    	int array[] = {30,39,21,25,24};
    	BSTree T = NULL;
    	bool taller = true;
    
    	for(int i = 0; i < 5; i++)
    	{
    		InsertAVL(T, array[i], taller);
    	}
    
    	Status status = PreOrderTraverse(T, Visit);
    	printf("%d\n",status);
    	return 0;
    }
    
    void R_Rotate(BSTree &p){
    	// 对以*p为根的二叉排序树作右旋处理，处理之后p指向新的树根结点，即旋转   
    	// 处理之前的左子树的根结点。	
        BSTree lc;  
        lc = p->lchild; // lc指向p的左子树根结点   
        p->lchild = lc->rchild; // lc的右子树挂接为p的左子树   
        lc->rchild = p;  
        p = lc; // p指向新的根结点   
    }
     
    void L_Rotate(BSTree &p){
    	// 对以*p为根的二叉排序树作左旋处理，处理之后p指向新的树根结点，即旋转   
    	// 处理之前的右子树的根结点。	
        BSTree rc;  
        rc = p->rchild; // rc指向p的右子树根结点   
        p->rchild = rc->lchild; // rc的左子树挂接为p的右子树   
        rc->lchild = p;  
        p = rc; // p指向新的根结点   
    }
    
    void LeftBalance(BSTree &T){
    	// 对以指针T所指结点为根的二叉树作左平衡旋转处理，本算法结束时，   
    	// 指针T指向新的根结点。 	
        BSTree lc,rd;  
        lc = T->lchild; // lc指向*T的左子树根结点   
        switch(lc->bf){ // 检查*T的左子树的平衡度，并作相应平衡处理   
    		case LH: 	// 新结点插入在*T的左孩子的左子树上，要作单右旋处理   
    			T->bf = lc->bf = EH;  
    			R_Rotate(T);  
    			break;  
    		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;  
    			}  
    			rd->bf = EH;  
    			L_Rotate(T->lchild); // 对*T的左子树作左旋平衡处理   
    			R_Rotate(T); 		// 对*T作右旋平衡处理   
        }  
    }  
      
    
    void RightBalance(BSTree &T){
    	// 对以指针T所指结点为根的二叉树作右平衡旋转处理，本算法结束时，   
    	// 指针T指向新的根结点  	
        BSTree rc,rd;  
        rc = T->rchild; // rc指向*T的右子树根结点   
        switch(rc->bf)  
        { 	// 检查*T的右子树的平衡度，并作相应平衡处理   
    		case RH: // 新结点插入在*T的右孩子的右子树上，要作单左旋处理   
    			 T->bf = rc->bf = EH;  
    			L_Rotate(T);  
    			break;  
    		case LH: // 新结点插入在*T的右孩子的左子树上，要作双旋处理   
    			rd = rc->lchild; // rd指向*T的右孩子的左子树根   
    			switch(rd->bf)  
    			{ // 修改*T及其右孩子的平衡因子   
    				case RH:  
    					T->bf = LH;  
    					rc->bf = EH;  
    					break;  
    				case EH:  
    					T->bf = rc->bf = EH;  
    					break;  
    				case LH:  
    					T->bf = EH;  
    					rc->bf = RH;  
    			}  
    			rd->bf = EH;  
    			R_Rotate(T->rchild); // 对*T的右子树作右旋平衡处理   
    			L_Rotate(T); // 对*T作左旋平衡处理   
        }  
    }  
    
    int InsertAVL(BSTree &T, TElemType e, bool &taller){ 
    	// 若在平衡的二叉排序树T中不存在和e有相同关键字的结点，则插入一个   
    	// 数据元素为e的新结点，并返回1，否则返回0。若因插入而使二叉排序树   
    	// 失去平衡，则作平衡旋转处理，布尔变量taller反映T长高与否。   
        if(!T){ // 插入新结点，树“长高”，置taller为1   
            T = (BSTree)malloc(sizeof(BSTNode));  
            T->data = e;  
            T->lchild = T->rchild = NULL;  
            T->bf = EH;  
            taller = true;  
        }else{  
            if(e ==  T->data){
    			// 树中已存在和e有相同关键字的结点则不再插入   
                taller = false;
                return 0;  
            }  
            if(e <  T->data)  
            { // 应继续在*T的左子树中进行搜索   
                if(!InsertAVL(T->lchild,e,taller)) // 未插入   
                    return 0;  
                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的右子树中进行搜索   
                if(!InsertAVL(T->rchild,e,taller)) // 未插入   
                {  return 0;  }
                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  
    			}//else  
    		}//else 
    	}	
        return 1;  
    }
    
    //先序遍历
    Status PreOrderTraverse(BSTree T, Status(* Visit)(TElemType e))    
    {    
        if (T)    
        {    
            Visit(T->data);    
            PreOrderTraverse(T->lchild, Visit);    
            PreOrderTraverse(T->rchild, Visit);    
        }    
        return OK;    
    }    
    
    //结点访问
    Status Visit(TElemType e)  
    {  
        printf("%d\n", e);  
        return OK;  
    }

运行的环境：win7旗舰版32位，Microsoft Visual C++ 6.0

参考：《数据结构(C语言版)》严蔚敏 吴伟明编著

[Link 1]: http://lib.csdn.net/base/datastructure