本文共 9076 字，大约阅读时间需要 30 分钟。

平衡二叉树构造

平衡二叉树也即AVL树,他可以提高查找的效率，像并查集的构建过程就用到了平衡二叉树的平衡因子特点(不是平衡二叉树啊)，满足任意节点的左子树的深度减去右子树的深度的值之差(称之为平衡因子)绝对值小于等于1，那么这棵二叉树为平衡二叉树。

在构建过程中会发生左旋与右旋的现象，那么当平衡因子大于1就右旋，平衡因子小于-1就左旋

举例看一下右旋:

class Tree{
       int value;//存储值    int bf;//存储平衡因子    Tree left,right;//左右子树    //初始化一个节点    Tree(int value)    {
           this.value = value;        this.bf = 0;        this.left=this.right=null;    }}

接下来的所有代码都在类AVL中，他有成员boolean taller,Tree root;

//parent是当前要旋转的节点root的父节点,L_or_R的值为-1，代表parent的左节点指向    //root,,L_or_R的值为1，代表parent的y右节点指向root    void  left_rotate(Tree root,Tree parent,int L_or_R)//左旋    {
           Tree right_node = root.right;        Tree temp = right_node.left;        right_node.left = root;        root.right = temp;        if(L_or_R==-1&&parent!=null)             parent.left = right_node;        else if(L_or_R==1&&parent!=null)             parent.right = right_node;    }    //parent是当前要旋转的节点root的父节点    void  right_rotate(Tree root,Tree parent,int L_or_R)//右旋    {
           Tree left_node = root.left;        Tree temp = left_node.right;        left_node.right=root;        root.left=temp;        if(L_or_R==-1&&parent!=null)            parent.left = left_node;        else if(L_or_R==1&&parent!=null)            parent.right = left_node;    }

3.leftBalance与rightBalance的实现

//当调用这个函数是说明root.bf=2了    void leftBalance(Tree root,Tree parent,int L_or_R)    {
           switch (root.left.bf)        {
               /*            这里要解释一下为什么不看左子树平衡因子为0            首先要明白root对应的树是最小不平衡子树            root不平衡是因为他的左子树加了一个节点使得左子树            深度+1，现在我们分情况讨论:记左子树的根节点为left_node            ①left_node.bf原来为-1,那么这要在left_node的左子树上加上节点            使得left_node.bf=0,但这样导致左子树深度没有+1，矛盾            ②left_node.bf原来为0,无论怎么加节点，都无法维持其为0            ③left_node.bf原来为1，那么这要在left_node的右子树上加上节点            使得left_node.bf=0,但这样导致左子树深度没有+1，矛盾             */            //平衡因子为1,见下面的第一张图            case 1:                root.left.bf=root.bf=0;                right_rotate(root,parent,L_or_R);                break;            //平衡因子为-1            case -1:                switch (root.left.right.bf)                {
                       case 1://见下面的第二张图                        root.bf=-1;                        root.left.bf=0;                        break;                    case -1://见下面的第三张图                        root.left.bf=1;                        root.bf=0;                        break;                    case 0:                        root.left.bf=root.bf=0;                }                root.left.right.bf = 0;                left_rotate(root.left,root,-1);                right_rotate(root,parent,L_or_R);                break;        }    }    void rightBalance(Tree root,Tree parent,int L_or_R)    {
           switch(root.right.bf)        {
               case -1:                root.right.bf=root.bf=0;                left_rotate(root,parent,L_or_R);                break;            case 1:                switch (root.right.left.bf)                {
                       case -1:                        root.bf=1;                        root.right.bf=0;                        break;                    case 1:                        root.bf=0;                        root.right.bf=-1;                        break;                    case 0:                        root.bf=root.right.bf=0;                        break;                }                root.right.left.bf=0;                right_rotate(root.right,root,1);                left_rotate(root,parent,L_or_R);                break;        }    }

//返回值为真代表插入成功,返回值为假代表插入失败    //root代表要插入的平衡树的根节点    //value代表要插入的节点的值    //taller代表插入后root的深度是否变大,且在整个递归中沿用同一个taller,故必须使用taller为全局变量    boolean insert_node(Tree root ,int value ,Tree parent,int L_or_R)    {
           //递归出口在这里，当递归到尽头时，必然会是root为null        if(root==null)        {
               if(L_or_R==-1)                parent.left = new Tree(value);            else                parent.right = new Tree(value);            taller = true;        }        else        {
               //判断value是否已经存在了,在递归中自然会把可能相等的点遍历到            if(root.value==value)            {
                   taller = false;//没有插入自然高度没有变化                return false;            }            else            {
                   if(value

5.正式插入

void Insert_AllNodes(int[] arr)    {
           Tree root1 = new Tree(1);//创建这个的原因是为了防止调用insert_node由于整棵树的根节点parent为空发生空指针异常        for (int i : arr) {
               insert_node(root1.left,i,root1,-1);        }        root = root1.left;//这里的root是AVL类的全局root    }

6.测试

@Test    public  void Test()    {
           int[] arr ={
   3,2,1,4,5,6,7,10,9,8};        Insert_AllNodes(arr);        FirstTransfer(root);        MiddleTransfer(root);    }

void MiddleTransfer(Tree node)    {
           if(node!=null)        {
               MiddleTransfer(node.left);            System.out.println(node.value);            MiddleTransfer(node.right);        }    }    void FirstTransfer(Tree node)    {
           if(node!=null)        {
               System.out.println(node.value);            FirstTransfer(node.left);            FirstTransfer(node.right);        }    }

最终完整版代码:

import org.junit.Test;public class AVL {
       boolean taller = true;    Tree root;    //parent是当前要旋转的节点root的父节点,L_or_R的值为-1，代表parent的左节点指向    //root,,L_or_R的值为1，代表parent的y右节点指向root    void  left_rotate(Tree root,Tree parent,int L_or_R)//左旋    {
           Tree right_node = root.right;        Tree temp = right_node.left;        right_node.left = root;        root.right = temp;        if(L_or_R==-1&&parent!=null)             parent.left = right_node;        else if(L_or_R==1&&parent!=null)             parent.right = right_node;    }    //parent是当前要旋转的节点root的父节点    void  right_rotate(Tree root,Tree parent,int L_or_R)//右旋    {
           Tree left_node = root.left;        Tree temp = left_node.right;        left_node.right=root;        root.left=temp;        if(L_or_R==-1&&parent!=null)            parent.left = left_node;        else if(L_or_R==1&&parent!=null)            parent.right = left_node;    }    //当调用这个函数是说明root.bf=2了    void leftBalance(Tree root,Tree parent,int L_or_R)    {
           switch (root.left.bf)        {
               /*            这里要解释一下为什么不看左子树平衡因子为0            首先要明白root对应的树是最小不平衡子树            root不平衡是因为他的左子树加了一个节点使得左子树            深度+1，现在我们分情况讨论:记左子树的根节点为left_node            ①left_node.bf原来为-1,那么这要在left_node的左子树上加上节点            使得left_node.bf=0,但这样导致左子树深度没有+1，矛盾            ②left_node.bf原来为0,无论怎么加节点，都无法维持其为0            ③left_node.bf原来为1，那么这要在left_node的右子树上加上节点            使得left_node.bf=0,但这样导致左子树深度没有+1，矛盾             */            //平衡因子为1,见下面的第一张图            case 1:                root.left.bf=root.bf=0;                right_rotate(root,parent,L_or_R);                break;            //平衡因子为-1            case -1:                switch (root.left.right.bf)                {
                       case 1://见下面的第二张图                        root.bf=-1;                        root.left.bf=0;                        break;                    case -1://见下面的第三张图                        root.left.bf=1;                        root.bf=0;                        break;                    case 0:                        root.left.bf=root.bf=0;                }                root.left.right.bf = 0;                left_rotate(root.left,root,-1);                right_rotate(root,parent,L_or_R);                break;        }    }    void rightBalance(Tree root,Tree parent,int L_or_R)    {
           switch(root.right.bf)        {
               case -1:                root.right.bf=root.bf=0;                left_rotate(root,parent,L_or_R);                break;            case 1:                switch (root.right.left.bf)                {
                       case -1:                        root.bf=1;                        root.right.bf=0;                        break;                    case 1:                        root.bf=0;                        root.right.bf=-1;                        break;                    case 0:                        root.bf=root.right.bf=0;                        break;                }                root.right.left.bf=0;                right_rotate(root.right,root,1);                left_rotate(root,parent,L_or_R);                break;        }    }    //返回值为真代表插入成功,返回值为假代表插入失败    //root代表要插入的平衡树的根节点    //value代表要插入的节点的值    //taller代表插入后root的深度是否变大,且在整个递归中沿用同一个taller,故必须使用taller为全局变量    boolean insert_node(Tree root ,int value ,Tree parent,int L_or_R)    {
           //递归出口在这里，当递归到尽头时，必然会是root为null        if(root==null)        {
               if(L_or_R==-1)                parent.left = new Tree(value);            else                parent.right = new Tree(value);            taller = true;        }        else        {
               //判断value是否已经存在了,在递归中自然会把可能相等的点遍历到            if(root.value==value)            {
                   taller = false;//没有插入自然高度没有变化                return false;            }            else            {
                   if(value

转载地址：http://fplzi.baihongyu.com/