目录

1、什么是树

2、相关术语

3、二叉树

3.1、二叉树的类型

3.2、二叉树的性质

3.3、二叉树的结构

3.4、二叉树的遍历

3.4.1、遍历的分类

3.4.1.1、前序遍历

3.4.1.2、中序遍历

3.4.1.3、后序遍历

3.4.1.4、层次遍历

4、通用树（N叉树）

4.1、通用树的表示

4.2、代码实现

5、线索二叉树

5.1、常规二叉树遍历的问题

5.2、线索二叉树的动机

5.3、线索二叉树的类型

5.4、线索二叉树的代码实现

5.5、线索二叉树的示例

5.6、线索二叉树的操作

5.6.1、中序线索二叉树中查找中序后继

5.6.2、中序线索二叉树的中序遍历

5.6.3、中序线索二叉树中查找前序后继

5.6.4、中序线索二叉树的前序遍历

5.6.5、中序线索二叉树插入结点

6、表达式树

6.1、表达式树举例

6.2、表达式树代码实现

7、二叉搜索树

7.1、二叉搜索树的作用

7.2、二叉搜索树的性质

7.3、二叉搜索树的代码实现

7.4、二叉搜索树的操作

7.4.1、在二叉搜索树中寻找元素

7.4.2、在二叉搜索树中寻找最小元素

7.4.3、在二叉搜索树中寻找最大元素

7.4.4、在二叉搜索树中寻找中序序列前驱和后继

7.4.5、在二叉搜索树中插入元素

7.4.6、在二叉搜索树中删除元素

8、平衡二叉搜索树

8.1、完全平衡二叉搜索树

8.2、AVL树

8.2.1、AVL树的性质

8.2.2、AVL树的最小/最大结点

8.2.3、AVL树的定义

8.2.4、AVL树的旋转

8.2.4.1、单旋转

8.2.4.2、双旋转

8.2.5、AVL树的插入操作

正文

1、什么是树

• 树是一种类似链表的数据结构，不过链表的结点是以线性方式简单地指向其后继指点，而树的一个结点可以指向许多个结点。树是一种典型的非线性结构。树结构是表达具有层次特性的图结构的一种方法。

2、相关术语

图2-1 树

• 根结点：根结点就是一个没有双亲结点的结点。一棵树中最多有一个根结点（如图2-1的结点A就是根结点）。
• 边：边表示从双亲结点到孩子结点的链接（如图2-1的所有链接）。
• 叶子结点：没有孩子结点的结点叫做叶子结点（如图2-1中的E、J、K、H、I ）。
• 兄弟结点：拥有相同的双亲结点的所有孩子结点叫做兄弟结点（如图2-1中的B、C、D是A的兄弟结点）。
• 祖先结点：如果存在一条从根结点到q的路径，且结点p出现在这条路径上，那么就可以把p叫做q的祖先结点（如图2-1中A、C、G是K的祖先结点）。
• 结点的大小：结点的大小是指子孙的个数，包括其自身（如图2-1中子树C的大小为3）。

图2-2 树的层

• 树的层：位于相同深度的所有结点的集合叫做树的层（如图2-2中的1和4具有相同的层）。
• 结点的深度：是指从根结点到该结点的路径长度（如图2-2中的5深度为2，3-4-5）。
• 结点的高度：是指从结点到最深结点的路径长度。树的高度是指根结点到树中最深结点的路径长度。只含有根结点的树的高度是0（如图2-2树的高度为2）。

图2-3 斜树

• 斜树：如果树中除了叶子结点外，其余每个结点都只有一个孩子结点，则这种树称为斜树（如图2-3）。

3、二叉树

• 如果一棵树中的每个结点有0、1或2个孩子结点，那么这个树就称为二叉树。空树也是一棵有效的二叉树。一棵二叉树可以看作由根结点和两棵不相交的子树组成，如图3-1所示。

  
  
  图3-1 二叉树示例

3.1、二叉树的类型

• 严格二叉树：二叉树中的每个结点要么有两个孩子结点，要么没有孩子结点（如图3-2所示）。

  
  
  图3-2 严格二叉树

• 满二叉树：二叉树的每个结点恰好有两个孩子结点且所有叶子结点在同一层（如图3-3所示）。

  
  
  图3-3 满二叉树

• 完全二叉树：假定二叉树的高度为h。对于完全二叉树，如果将所有结点从根结点开始从左至右，从上至下，依次编号（假定根结点编号为1），那么将得到从1~n（n为结点总数）的完整序列。如果所有叶子结点的深度为h或者h-1，且结点在编号过程中没有漏掉任何数字，那么就叫做完全二叉树（如图3-4所示）。

  
  
  图3-4 完全二叉树

3.2、二叉树的性质

假定树的高度为h，且根结点的深度为0。

图3-5 二叉树性质

从图3-5可得出如下性质：

• 满二叉树的结点个数n为[2^(h+1)] -1。因为该树总共有h层，每一层结点都是满的。
• 满二叉树的叶子结点个数是2^h。

3.3、二叉树的结构

• 表示一个结点的方法之一是定义两个指针，一个指向左孩子结点，另一个指向右孩子结点，中间为数据字段（如图3-6所示）。

  
  
  图3-6 二叉树的结构
• 代码实现：

public class BinaryTreeNode {
    private int data;
    private BinaryTreeNode left;
    private BinaryTreeNode right;

    public int getData(){
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public BinaryTreeNode getLeft() {
        return left;
    }

    public void setLeft(BinaryTreeNode left) {
        this.left = left;
    }

    public BinaryTreeNode getRight() {
        return right;
    }

    public void setRight(BinaryTreeNode right) {
        this.right = right;
    }
}

3.4、二叉树的遍历

访问树中所有结点的过程叫做遍历，遍历的目标是按照某种特定的顺序访问树的所有结点。

3.4.1、遍历的分类

• 前序遍历（DLR）:访问当前结点，遍历左子树，再遍历右子树。
• 中序遍历（LDR）:先遍历左子树，访问当前结点，再遍历右子树。
• 后序遍历（LRD）:先遍历左子树，再遍历右子树，访问当前结点。

• 层次遍历。
  以下图所示的树为例。

  
  
  图3-7 二叉树的遍历

3.4.1.1、前序遍历

• 基于前序遍历，图3-7所示树的前序遍历结果如下：

C:\Application\java\jdk\bin\java.exe ..."
前序遍历结果：
1
2
4
5
3
6
7

Process finished with exit code 0

• 递归前序遍历，代码实现如下：

    public void PreOrder(BinaryTreeNode root){
        if(root!=null){
            System.out.print(root.getData());
            PreOrder(root.getLeft());
            PreOrder(root.getRight());
        }
    }

• 非递归前序遍历，需要采用一个栈来记录当前结点，以便在完成左子树遍历后能返回到右子树进行遍历。首先处理当前结点，在遍历左子树之前，把当前结点保留到栈中，当遍历完左子树之后，该元素出栈，然后找到其右子树进行遍历，直至栈空。代码实现如下：

   public void PreOrderNonRecursive(BinaryTreeNode root){
        if(root==null){
            return;
        }
        Stack s=new Stack();
        while (true){
            while (root!=null){
                System.out.print(root.getData());
                s.push(root);
                root=root.getLeft();
            }
            if(s.isEmpty()){
                break;
            }
            root=(BinaryTreeNode) s.pop();
            root=root.getRight();
        }
    }

3.4.1.2、中序遍历

• 基于中序遍历，图3-7所示树的中序遍历结果如下：

C:\Application\java\jdk\bin\java.exe ..."
中序遍历结果：
4
2
5
1
6
3
7

Process finished with exit code 0

• 递归中序遍历，代码实现如下：

    public void InOrder(BinaryTreeNode root){
        if(root!=null){
            InOrder(root.getLeft());
            System.out.print(root.getData());
            InOrder(root.getRight());
        }
    }

• 非递归中序遍历，与前序遍历的区别是，首先要移动到结点的左子树，完成左子树的遍历后，再将当前结点出栈进行处理。

    public void InOrderNonRecursive(BinaryTreeNode root){
        if(root==null){
            return;
        }
        Stack s=new Stack();
        while (true){
            while (root!=null){
                s.push(root);
                root=root.getLeft();
            }
            if(s.isEmpty()){
                break;
            }
            root=(BinaryTreeNode)s.pop();
            System.out.print(root.getData()+"\n");
            root=root.getRight();
        }
    }

3.4.1.3、后序遍历

• 基于后序遍历，图3-7所示树的后序遍历结果如下：

C:\Application\java\jdk\bin\java.exe ..."
后序遍历结果：
4
5
2
6
7
3
1

Process finished with exit code 0

• 递归后序遍历，代码实现如下：

    public void PostOrder(BinaryTreeNode root){
        if(root!=null){
            PostOrder(root.getLeft());
            PostOrder(root.getRight());
            System.out.print(root.getData());
        }
    }

• 非递归后序遍历，在前序和中序遍历中，当元素出栈后就不需要再访问这个结点了。但是后序遍历中，每个结点需要访问两次。这意味着，在遍历完左子树后，需要访问当前结点，之后遍历完右子树时，还需要访问当前结点。但只有在第二次访问时才处理该结点。
• 解决办法是，当从栈中出栈一个元素时，检查这个元素与栈顶元素的右子结点是否相同。如果相同，则说明已经完成了左右子树的遍历。此时只要再将栈顶元素出栈并输出该结点元素。

     public void PostOrderNonRecursive(BinaryTreeNode root){
        Stack stack=new Stack();
        while (true){
            if(root!=null){
                //寻找最左叶子结点
                stack.push(root);
                root=root.getLeft();
            }else {
                if(stack.isEmpty()){
                    return;
                }else {
                    //判断当前结点是否有右子节点
                    if(stack.top().getRight==null){
                        root=stack.pop();
                        System.out.print(root.getData()+"\n");
                        //判断该结点是否为栈顶右子节点
                        while(root==stack.top().getRight()){
                            System.out.print(stack.top().getData()+"\n");
                            root=stack.pop();
                            if(stack.isEmpty()){
                                return;
                            }
                        }
                    }
                }
                if(!stack.isEmpty()){
                    //遍历结点右子树
                    root=stack.top().getRight();
                }else {
                    root=null;
                }
            }
        }
    }

3.4.1.4、层次遍历

• 基于层次遍历，图3-7所示树的层次遍历结果如下：

C:\Application\java\jdk\bin\java.exe ..."
层次遍历结果：
1
2
3
4
5
6
7

Process finished with exit code 0

• 层次遍历，代码实现如下：

public void LevelOrder(BinaryTreeNode root){
        BinaryTreeNode temp;
        LLBinaryTreeQueue queue=LLBinaryTreeQueue.creteQueue();
        if(root==null){
            return;
        }
        queue.enQueue(root);
        while (!queue.isEmpty()){
            temp=queue.deQueue();
            //处理当前结点
            System.out.print(temp.getData()+"\n");
            if(temp.getLeft()!=null){
                queue.enQueue(temp.getLeft());
            }
            if(temp.getRight()!=null){
                queue.enQueue(temp.getRight());
            }
        }
    }

4、通用树（N叉树）

• 上一节中，讨论了每个结点最多两个孩子结点的二叉树，这种树可以用两个指针来表示。但是若一棵树中每个结点可以有任意多个子结点，该如何表示？例如下图：

  
  
  图4-1 N叉树

4.1、通用树的表示

• 同一个双亲结点（兄弟）的孩子结点从左至右排列。

• 双亲结点只指向第一个孩子结点，删除从双亲结点到其他孩子结点的链接。

  
  
  图4-2 解决示例

4.2、代码实现

public class TreeNode {
    private int data;
    private TreeNode firstChild;
    private TreeNode nextSibling;

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public TreeNode getFirstChild() {
        return firstChild;
    }

    public void setFirstChild(TreeNode firstChild) {
        this.firstChild = firstChild;
    }

    public TreeNode getNextSibling() {
        return nextSibling;
    }

    public void setNextSibling(TreeNode nextSibling) {
        this.nextSibling = nextSibling;
    }
}

5、线索二叉树

• 在3.4中介绍了二叉树的前序、中序和后序遍历，这些遍历方式使用栈作为辅助数据结构，而层次遍历中使用队列作为辅助数据结构。线索二叉树遍历将摈弃这些辅助数据结构。

5.1、常规二叉树遍历的问题

• 栈和队列需要的存储空间很大。
• 任意一棵二叉树往往存在大量的空指针。例如：拥有n个结点的二叉树有n+1个空指针。
• 很难直接找到一个给定结点的后继结点（前序、中序和后序后继）。

5.2、线索二叉树的动机

• 在空指针中存储一些有用的信息，就不需要将这些信息存储在栈/队列中，空左指针将包含前驱信息，而空右指针将包含后继信息。这些特殊的指针就叫做线索。

5.3、线索二叉树的类型

根据线索中存储的信息是依据前序、中序或后序排列，线索二叉树有以下3种类型：

• 前序线索二叉树：空左指针存储前序序列前驱信息，空右指针存储前序序列后继信息。
• 中序线索二叉树：空左指针存储中序序列前驱信息，空右指针存储中序序列后继信息。
• 后序线索二叉树：空左指针存储后序序列前驱信息，空右指针存储后序序列后继信息。
  注：5.4中代码实现为中序线索二叉树。

5.4、线索二叉树的结构

如图所示：

图5-1 线索二叉树结构示例

图5-2 常规二叉树与线索二叉树区别

代码实现：

public class ThreadedBinaryTreeNode {
    private ThreadedBinaryTreeNode left;
    private int LTag;
    private int data;
    private int RTag;
    private ThreadedBinaryTreeNode right;

    public ThreadedBinaryTreeNode getLeft() {
        return left;
    }

    public void setLeft(ThreadedBinaryTreeNode left) {
        this.left = left;
    }

    public int getLTag() {
        return LTag;
    }

    public void setLTag(int LTag) {
        this.LTag = LTag;
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public int getRTag() {
        return RTag;
    }

    public void setRTag(int RTag) {
        this.RTag = RTag;
    }

    public ThreadedBinaryTreeNode getRight() {
        return right;
    }

    public void setRight(ThreadedBinaryTreeNode right) {
        this.right = right;
    }
}

5.5、线索二叉树的示例

• 假设一棵二叉树的中序序列为：2、5、1、16、11、31，先序序列为：1，5，2，11，16，31。

• 构建如下图5-3所示，虚线箭头表示线索。此时，最左边结点（2）的左指针和最右边结点（31）是悬空的。

  
  
  图5-3 示例

• 在线索二叉树中，使用一个哑结点Dummy，如图5-4所示。

  
  
  图5-4 哑结点

• 根据上述约定，图5-3可以进一步表示为图5-5所示。

  
  
  图5-5 示例（2）

5.6、线索二叉树的操作

5.6.1、中序线索二叉树中查找中序后继

• 策略：如果当前结点的RTag=0，则返回Right；如果当前结点的RTag=1，说明当前结点有右子树，依据中序遍历规则，先遍历左子树，再访问当前结点，最后遍历右子树。可以推出，需要找到右子树的最左孩子结点（相当于遍历右子树的最先结点），即为当前结点的后继。
• 代码实现：

ThreadedBinaryTreeNode InorderSuccessor(ThreadedBinaryTreeNode P){
        ThreadedBinaryTreeNode position;
        if(P.getRTag()==0){
            return P.getRight();
        }else {
            position=P.getRight();
            while (position.getLTag()==1){
                position=position.getLeft();
            }
            return position;
        }
    }

5.6.2、中序线索二叉树的中序遍历

• 策略：从哑结点开始，递归调用InorderSuccessor()来访问每一个结点，直至再次达到哑结点。
• 代码实现：

void InorderTraversal(ThreadedBinaryTreeNode root){
        ThreadedBinaryTreeNode p=InorderPrecursor(root);
        while (p!=root){
            p=InorderPrecursor(p);
            System.out.print(p.getData());
        }
    }

5.6.3、中序线索二叉树中查找前序后继

• 策略：如果当前结点的LTag=1，则返回Left；如果当前结点的LTag=0，说明当前结点没有左子树，那么返回右子树包含当前结点的最近结点的右孩子结点。
• 代码实现：

ThreadedBinaryTreeNode PreorderSuccessor(ThreadedBinaryTreeNode p){
        ThreadedBinaryTreeNode position;
        if(p.getLTag()==1){
            return p.getLeft();
        }else {
            position=p;
            while (position.getRTag()==0){
                position=position.getRight();
            }
            return p.getRight();
        }
    }

5.6.4、中序线索二叉树的前序遍历

• 策略：与中序遍历相同，从哑结点开始，递归调用PreorderSuccessor()函数访问每一个结点，直至再次回到哑结点。
• 代码实现：

void PreorderTraversal(ThreadedBinaryTreeNode root){
        ThreadedBinaryTreeNode p=PreorderSuccessor(root);
        while (p!=root){
            p=PreorderSuccessor(p);
            System.out.print(p.getData());
        }
    }

5.6.5、中序线索二叉树插入结点

假设有两个结点P和Q，现在要将Q连接到P的右边。

• 策略：
  （情况一）：结点P没有右孩子结点。在这种情况下，只需要将Q连接到P上，同时改变其左指针和右指针即可。如图5-6所示。

  
  
  图5-6 情况一
  
  

  （情况二）：结点P有右孩子结点（假设为R）。在此情况下，需要遍历R的左子树，并找到最左边的结点，然后更新这个结点的左指针和右指针。如图5-7所示。

  
  
  图5-7 情况二

• 代码实现：

void InsertRightInoderTBT(ThreadedBinaryTreeNode p,ThreadedBinaryTreeNode q){
        ThreadedBinaryTreeNode temp;
        q.setRight(p.getRight());
        q.setRTag(p.getRTag());
        q.setLeft(p);
        q.setLTag(0);
        p.setRTag(1);
        if(q.getRTag()==1){
            //第二种情况
            temp=q.getRight();
            while (temp.getLTag()==1){
                temp=temp.getLeft();
            }
            temp.setLeft(q);
        }
    }

6、表达式树

• 用来表示表达式的树叫做表达式树。在表达式树中，叶子结点是操作数，而非叶子结点是操作符。下图为表达式树：（A+B*C）/D所对应的一个简单表达式树。

  
  
  图6-1 表达式树

6.1、表达式树举例

• 策略：假定每次读入一个符号。如果符号是操作数，就创建一个结点，并把指向该结点的指针入栈。如果符号是操作符，则从栈中弹出两个指向树T1和T2的指针，并产生一棵新树，该树以读到的操作符作为根结点，两个指针分别作为根结点的左孩子结点和右孩子结点，再将指向新树的指针入栈。

• 实现：输入后缀表达式为：A B C * + D /。
  （1）、前3个符号是操作数，所以产生3个结点，并入栈，如图6-2所示。

  
  
  图6-2 操作数入栈
  
  

  （2）、接下来读入操作符：*，因此栈中指向两棵树的指针出栈，形成一棵新树，最后指向新树的指针入栈，如图6-3所示。

  
  
  图6-3 读入操作符‘*’
  
  （3）、接下来读入操作符：+，因此栈中指向两棵树的指针出栈，形成一棵新树，最后指向新树的指针入栈，如图6-4所示。
  
  图6-4 读入操作符‘+’
  
  （4）、接下来读入操作数：D，产生包含一个结点的树，将指向该树的指针入栈，如图6-5所示。
  
  图6-5 读入操作数‘D’
  
  

  （5）、最后读入操作符：/，将栈中指针所对应的两棵树合并，并将指向最后树的指针入栈，如图6-6所示。

  
  
  图6-6 读入操作符‘/’

6.2、表达式树代码实现

BinaryTreeNodeChar BuildExprTree(char[] postfixExpr,int size){
        LLBinaryTreeStack s=new LLBinaryTreeStack();
        for(int i=0;i<size;i++){
            if(postfixExpr[i]!='+'&&postfixExpr[i]!='-'&&postfixExpr[i]!='*'&&postfixExpr[i]!='/'){
                BinaryTreeNodeChar newNode=new BinaryTreeNodeChar(postfixExpr[i],null,null);
                s.push2(newNode);
            }
            else {
                BinaryTreeNodeChar T2=s.pop2();
                BinaryTreeNodeChar T1=s.pop2();
                BinaryTreeNodeChar newNode=new BinaryTreeNodeChar(postfixExpr[i],T1,T2);
                s.push2(newNode);
            }
        }
        return s.top2();
    }

7、二叉搜索树

7.1、二叉搜索树的作用

• 二叉搜索树（BST），主要是用来实现搜索操作，在这种表示中，对结点所包含的数据进行了一定的约束。因此它使得最坏情况下平均搜索的时间复杂度降低至O(logn)。

7.2、二叉搜索树的性质

• 一个结点的左子树只能包含键值小于该结点键值的结点。
• 一个结点的右子树只能包含键值大于该结点键值的结点。
• 左子树和右子树必须都是二叉搜索树。

7.3、二叉搜索树的代码实现

public class BinarySearchTreeNode {
    private int data;
    private BinarySearchTreeNode left;
    private BinarySearchTreeNode right;

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public BinarySearchTreeNode getLeft() {
        return left;
    }

    public void setLeft(BinarySearchTreeNode left) {
        this.left = left;
    }

    public BinarySearchTreeNode getRight() {
        return right;
    }

    public void setRight(BinarySearchTreeNode right) {
        this.right = right;
    }
}

7.4、二叉搜索树的操作

7.4.1、在二叉搜索树中寻找元素

• 从根结点开始，基于二叉搜索树的性质移动到左子树或者右子树继续搜索。如果待搜索数据和根结点数据一致，则返回当前结点。如果待搜索数据小于当前结点数据，则搜索当前结点的左子树；否则，搜索当前结点的右子树。如果数据不存在，则返回空指针。代码如下：

    BinarySearchTreeNode FindRecursive(BinarySearchTreeNode root,int data){
        if(root==null){
            return null;
        }
        if(data<root.getData()){
            return FindRecursive(root.getLeft(),data);
        }else if(data>root.getData()){
            return FindRecursive(root.getRight(),data);
        }
        return root;
    }

• 上述算法的非递归代码实现如下：

    BinarySearchTreeNode Find(BinarySearchTreeNode root,int data){
        if(root==null){
            return null;
        }
        while (root!=null){
            if(data==root.getData()){
                return root;
            }else if(data<root.getData()){
                root=root.getLeft();
            }else {
                root=root.getRight();
            }
        }
        return null;
    }

7.4.2、在二叉搜索树中寻找最小元素

• 在二叉搜索树中，最左边的结点为最小元素，因为它没有左子结点。代码实现如下：

    BinarySearchTreeNode FindMinRecursive(BinarySearchTreeNode root){
        if(root==null){
            return null;
        }else {
            if(root.getLeft()==null){
                return root;
            }else {
                return FindMinRecursive(root.getLeft());
            }
        }
    }

• 上述算法的非递归代码实现如下：

    BinarySearchTreeNode FindMin(BinarySearchTreeNode root){
        if(root==null){
            return null;
        }
        while (root.getLeft()!=null){
            root=root.getLeft();
        }
        return root;
    }

7.4.3、在二叉搜索树中寻找最大元素

• 在二叉搜索树中，最右边的结点为最大元素，因为它没有右子结点。代码实现如下：

    BinarySearchTreeNode FindMaxRecursive(BinarySearchTreeNode root){
        if(root==null){
            return null;
        }else {
            if(root.getRight()==null){
                return root;
            }else {
                return FindMaxRecursive(root.getRight());
            }
        }
    }

• 上述算法的非递归代码实现如下：

    BinarySearchTreeNode FindMax(BinarySearchTreeNode root){
        if(root==null){
            return null;
        }
        while (root.getRight()!=null){
            root=root.getRight();
        }
        return root;
    }

7.4.4、在二叉搜索树中寻找中序序列前驱和后继

• 假定二叉搜索树中所有关键字值是唯一的，那么树中结点X的中序序列前驱和后继是什么？如果X有两个孩子结点，那么中序序列前驱为其左子树中值最大的元素，而其后继为其右子树中的最小元素。如图7-1所示。

  
  
  图7-1 示例1

• 如果它没有左孩子结点，则该结点中序序列前驱是其第一个左祖先结点。如图7-2所示。

  
  
  图7-2 示例2

7.4.5、在二叉搜索树中插入元素

• 策略：为了在二叉搜索树中插入数据，首先需要找到插入该数据的位置。以图7-3为例，虚线结点表示要插入的元素（5）。遍历这棵树，在键值4的节点处，需要访问其右子树，但是由于结点4没有右子树，所以5没有在树中，因此这就是要插入的位置。

  
  
  图7-3 插入元素示例

• 代码实现：

    BinarySearchTreeNode Insert(BinarySearchTreeNode root,int data){
        if(root==null){
            root=new BinarySearchTreeNode();
            root.setData(data);
            root.setLeft(null);
            root.setRight(null);
        }else {
            if(data<root.getData()){
                root.setLeft(Insert(root.getLeft(),data));
            }else if(data>root.getData()){
                root.setRight(Insert(root.getRight(),data));
            }
        }
        return root;
    }

7.4.6、在二叉搜索树中删除元素

• 首先找到待删除元素的位置。

• 如果待删除元素为叶子结点，则返回NULL给其双亲结点，即将其相应的孩子结点指针设置为NULL。如下图7-4所示。在下面的树中删除5，将其双亲结点2的孩子指针设置为NULL。

  
  
  图7-4 删除叶子结点

• 如果待删除结点有一个孩子结点，在这中情况下，只需要将待删除结点的孩子结点返回给双亲结点。如下图7-5所示。要删除4，4的左子树设置为其双亲结点的一棵子树。

  
  
  图7-5 删除包含一个孩子结点

• 如果待删除结点有两个孩子结点，从其左子树中找到最大元素来代替这个结点的主键，然后再删除那个结点。左子树中最大元素是没有右孩子，第二次删除操作是很容易完成的。如图7-6所示。要删除8，它是根节点的右孩子结点，主键是8。用它的左子树（7）最大主键代替它，然后再删除7这个结点。

  
  
  图7-6 删除包含两个孩子结点
  
  

  【备注：图7-6结点8的右子结点应改成10】

• 代码实现：

    BinarySearchTreeNode Delete(BinarySearchTreeNode root,int data){
        BinarySearchTreeNode temp;
        if(root==null){
            System.out.print("Element not there in tree");
        }
        else if(data<root.getData()){
            root.left=Delete(root.getLeft(),data);
        }
        else if(data>root.getData()){
            root.right=Delete(root.getRight(),data);
        }
        else {//找到该元素
            if(root.getLeft()!=null&&root.getRight()!=null){
                //用左子树的最大值代替
                temp=FindMax(root.getLeft());
                root.setData(temp.getData());
                root.left=Delete(root.getLeft(),root.getData());
            }else{
                //一个孩子结点
                if(root.getLeft()==null){
                    root=root.getRight();
                }
                if(root.getRight()==null){
                    root=root.getLeft();
                }
            }
        }
        return root;
    }

8、平衡二叉搜索树

• 不同类型的树在最坏情况下搜索操作的复杂度为O(n)。而高度平衡树用符号HB(k)表示，其中k为左右子树的高度差，通过限制树的高度可以将最坏情况下的时间复杂度降至O(logn)。

8.1、完全平衡二叉搜索树

• 在HB(k)中，如果k=0那么就叫做完全平衡二叉树，即左右子树高度差最多为0。如下图8-1所示。

  
  
  图8-1 完全平衡二叉树

8.2、AVL树

• 在HB(k)中，如果k=1，那么这样的二叉搜索树叫做AVL树，左子树和右子树高度差不超过1。

8.2.1、AVL树的性质

• 它是一棵二叉搜索树。
• 对任意结点X，其左子树的高度与其右子树的高度差不超过1。

如下图8-2 所示，左边的树不是AVL树，右边的是AVL树。

图8-2 AVL树示例

8.2.2、AVL树的最小/最大结点树

假定AVL树的高度是h，N(h)表示高度为h的AVL树的结点数。

• 为了得到高度为h的AVL树的最小结点数，应该尽可能少的结点来填充这棵树。即假定填充左子树的高度为h-1，那么右子树的高度只能填充到h-2。这样，最小结点数为：N(h)=N(h-1)+N(h-2)+1（1表示根结点）。求解该递归式可以得到：

  
  

• 为了获得最大结点数，需要将左子树和右子树都填充到高度为h-1。这样，最大结点数：N(h)=N(h-1)+N(h-1)+1。求解该递归式可以得到：

  
  

8.2.3、AVL树的定义

• 因为AVL树是一棵BST树，所以AVL树的定义类似于BST树的定义。同时把高度也作为定义中的一部分。代码实现如下：

public class AVLTreeNode {
    private int data;
    private int height;
    private AVLTreeNode left;
    private AVLTreeNode right;

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public int getHeight() {
        return height;
    }

    public void setHeight(int height) {
        this.height = height;
    }

    public AVLTreeNode getLeft() {
        return left;
    }

    public void setLeft(AVLTreeNode left) {
        this.left = left;
    }

    public AVLTreeNode getRight() {
        return right;
    }

    public void setRight(AVLTreeNode right) {
        this.right = right;
    }
}

8.2.4、AVL树的旋转

• 定义：当树的结构发生变化时（例如插入或删除结点），就需要改变树的结构来保证AVL树的性质。这个操作可以用旋转来实现。因为插入/删除一个结点，将导致子树的高度增加1或减少1，可能会导致某个结点X的左子树和右子树的高度差为2，而旋转是用来保持AVL树性质的技术。
• 策略：在插入结点后，只有插入结点到根路径上的结点的平衡因子（左右子树的高度差）才可能改变。为了恢复AVL树的性质，需要在该路径上找到第一个不满足AVL树性质的结点，从这个结点到根结点的路径上的每个结点也就都存在这个问题。所以，如果修复第一个结点的问题，那么其他结点都将自动满足AVL树的性质。
• 类型：假定X结点是必须要重新平衡的结点，有以下4种情况可能违反AVL树性质。
  1）在结点X的左孩子结点的左子树中插入元素。
  2）在结点X的左孩子结点的右子树中插入元素。
  3）在结点X的右孩子结点的左子树中插入元素。
  4）在结点X的右孩子结点的右子树中插入元素。

8.2.4.1、单旋转

• 左左旋转（LL旋转）（8.2.4情况1）：从插入结点处开始，向上遍历树，并更新这个路径上每个结点的平衡信息。例如图8-3所示，在左边原始AVL树插入7后，结点9变为非平衡的（结点7插入在结点9的左孩子的左子树中）。执行左左旋转，得到右边这棵树。

  
  
  图8-3 左左旋转
  
  

  如图8-4所示，好比在结点X，对它的左孩子结点W的左子树A中插入一个结点，平衡被破坏，执行左左旋转后，得到右边这棵树。结点X重新平衡；子树A因为插入新结点，高度增加1，同时X变为W的右孩子结点，结点W重新平衡。

  
  
  图8-4 左左旋转（2）
  
  代码实现如下：

    AVLTreeNode SingleRotateLeft(AVLTreeNode X){
        AVLTreeNode W=X.getLeft();
        //将结点W的右子树设置为结点X的左孩子
        X.setLeft(W.getRight());
        //将结点X设置为W的右孩子
        W.setRight(X);
        //计算结点X的高度
        X.setHeight(Math.max(Height(X.getLeft()),Height(X.getRight()))+1);
        //计算结点W的高度
        W.setHeight(Math.max(Height(W.getLeft()),X.getHeight())+1);
        return W;
    }

• 右右旋转（RR旋转）（8.2.4情况4）:例如图8-5所示，在左边原始AVL树插入20后，结点10变为非平衡的（结点20插入在结点10的右孩子的右子树中）。执行右右旋转，得到右边这棵树。

  
  
  图8-5 右右旋转
  
  

  如图8-6所示，好比在结点W，对它的右孩子结点X的右子树C中插入一个结点，平衡被破坏，执行右右旋转后，得到右边这棵树。结点W重新平衡；子树C因为插入新结点，高度增加1，同时W变为X的左孩子结点，结点X重新平衡。

  
  
  图8-6 右右旋转（2）
  
  代码实现如下：

    AVLTreeNode SingleRotateRight(AVLTreeNode W){
        AVLTreeNode X=W.getRight();
        //将结点X的左子树设置为W的右孩子
        W.setRight(X.getLeft());
        //将结点W设置为结点X的左孩子
        X.setLeft(W);
        //计算结点W的高度
        W.setHeight(Math.max(Height(W.getLeft()),Height(W.getRight()))+1);
        //计算结点X的高度
        X.setHeight(Math.max(Height(X.getRight()),W.getHeight())+1);
        return X;
    }

8.2.4.2、双旋转

• 左右旋转（LR旋转）（8.2.4情况2）：例如图8-7所示，在左边原始AVL树插入7后，结点8变为非平衡的（结点7插入在结点8的左孩子的右子树中）。执行两次单旋转，得到右边这棵树。

  
  
  图8-7 左右旋转
  
  

  如图8-8所示，好比在结点Z，对它的左孩子结点X的右子树C中插入一个结点，平衡被破坏。此时先对X结点进行右旋转，完成之后再对Z结点进行左旋转。最后便重新得到一棵AVL树。

  
  
  图8-8 左右旋转（2）
  
  代码实现如下：

    AVLTreeNode DoubleRotatewithLeft(AVLTreeNode Z){
        Z.setLeft(SingleRotateRight(Z.getLeft()));
        return SingleRotateLeft(Z);
    }

• 右左旋转（RL旋转）（8.2.4情况3）：例如图8-9所示，在左边原始AVL树插入5后，结点4变为非平衡的（结点6插入在结点4的右孩子的左子树中）。执行两次单旋转，得到右边这棵树。
  【备注：图8-9的中间部分的根结点应为：4】

  
  
  图8-9 右左旋转
  
  

  如图8-10所示，好比在结点X，对它的右孩子结点Z的左子树B中插入一个结点，平衡被破坏。此时先对Z结点进行左旋转，完成之后再对X结点进行右旋转。最后便重新得到一棵AVL树。

  
  
  图8-10 右左旋转（2）

代码实现如下：

    AVLTreeNode DoubleRotatewithRight(AVLTreeNode X){
        X.setLeft(SingleRotateLeft(X.getRight()));
        return SingleRotateRight(X);
    }

8.2.5、AVL树的插入操作

• AVL树的插入类似BST树的插入。在插入一个元素后，需要检查高度是否平衡。如果不平衡，需要调用相应的旋转函数。代码实现如下：

    AVLTreeNode Insert(AVLTreeNode root,AVLTreeNode parent,int data){
        if(root==null){
            root=new AVLTreeNode();
            root.setData(data);
            root.setHeight(0);
            root.setLeft(null);
            root.setRight(null);
        }
        else if(data<root.getData()){
            root.setLeft(Insert(root.getLeft(),root,data));
            if((Height(root.getLeft())-Height(root.getRight()))==2){
                if(data<root.getLeft().getData()){
                    //插入在左孩子的左子树中,对root执行左左旋转操作
                    root=SingleRotateLeft(root);
                }else {
                    //插入在左孩子的右子树中，对root执行左右旋转操作
                    root=DoubleRotatewithLeft(root);
                }
            }
        }
        else if(data>root.getData()){
            root.setRight(Insert(root.getRight(),root,data));
            if((Height(root.getRight())-Height(root.getLeft()))==2){
                if(data>root.getRight().getData()){
                    //插入在右孩子的右子树中，对root执行右右旋转操作
                    root=SingleRotateRight(root);
                }else {
                    //插入在右孩子的左子树中，对root执行右左旋转操作
                    root=DoubleRotatewithRight(root);
                }
            }
        }
        /*
            否则，数据已经在树中，不必做任何操作
         */
        root.setHeight(Math.max(Height(root.getLeft()),Height(root.getRight()))+1);
        return root;
    }