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

二叉排序树（BST）

题目引入

1. 需求：对数列{7，3，10，12，1，5，9}进行高效的查询和添加。

• 分析：
  • 使用数组：数组未排序，优点直接在尾部添加，速度快，查找速度慢：数组已经排序，使用二分查找，速度较快，但是添加元素，中间插入，数组会整体后移，速度慢。
  • 使用链式存储 — 链表：添加和删除节点的速度快，但是查找速度慢
  • 使用二叉排序树：检索速度快，查找速度快，同时比那与添加和修改。

二叉排序树的介绍

1. 二叉排序树：BST（Binary Sort（）Search Tree），对于二叉排序树的任何一个非叶子节点，要求左子节点的值比当前节点的值小，右子节点比当前的值大。（左小右大）
2. 特别的说明：如果擦加入的值与某点相同，就放在左子结点，确保不出现两个相同节点在同一层，互为左右节点。

添加节点—代码实现：

class BinarySortTree

public void add(Node node) {
           if (root == null) {
               root = node;        } else {
               root.add(node);        }    }

class Node

public void add(Node node){
           if (node == null){
               return;        }        if(node.value < this.value){
               if (this.left == null){
                   this.left = node;            }else{
                   this.left.add(node);            }        }else{
               if (this.right == null){
                   this.right = node;            }else{
                   this.right.add(node);            }        }    }

总结与分析：

1. 一个方法操作对象除了有形参列表，还有调用方法的对象，所以，在处理添加方法时，没有必要再增加一个形参对象root，直接操作当前调用方法的this。
2. 在调用左右各子节点的成员变量时，必须要判定左右各子结点是否为空，在进行判定。

删除节点—代码实现：

思路分析

1. 三种情况：
   • 删除叶子节点
   • 删除只有一个子树的结点
   • 删除有两个子树的结点
2. 思路分析：
   1. 删除叶子节点

      1. 找到要删除的结点targetNode的父节点parent，有以下两种情况
         • 没有父节点，根节点
         • 有父节点，非根节点
      2. 确定targetNode是parent的左子节点还是右子节点
         • 左子节点：parent.left = null
         • 右子节点：parent.right = null

   2. 删除有一棵子树的结点

      1. 找到targetNode的父节点parent
      2. 确定targetNode是父节点的左子节点还是右子节点，和targetNode的子节点是targetNode的左子节点，还是右子节点；
         • targetNode是parent的左子节点，targetNode仅有左子树，parent.left = targetNode.left;
         • targetNode是parent的左子节点，targetNode仅有右子树，parent.left = targetNode.right:
         • targetNode是parent的右子节点，targetNode仅有左子树，parent.right = targetNode.left;
         • targetNode是parent的右子节点，targetNode仅有右子树，parent.right = targetNode.right;

   3. 删除的目标节点TargetNode右两个子树

      • 找到待删除结点TargetNode的父节点parent
      • 确定待删除结点TargetNode是parent的左节点还是右节点
      • TargetNode是parent的左节点，从TargetNode左子树选出最大的结点取代TargetNode，或者是从右子树找出最小的结点，取代TargetNode结点
      • TargetNode是parent的右节点，从TargetNode的左子树选出最大的结点取代TargetNode,并删除；或者从TargetNode的右子树选出最小结点取代TargetNode结点。

代码实现

1. 找到待删除结点的父节点
   class Node：查找待删除结点的对应结点

public Node search(int value){
           if (this == null){
               return null;        }        if (value == this.value){
               return this;        }else if(value < this.value){
               //如果查找的值小于当前节点的值，那就向左进行递归            //还有一个问题：不知道但前指针存不存在，有可能为零            if (this.left == null){
                   return null;            }            return this.left.search(value);        }else{
               //如果当前的值大于当前节点的值，那就向右进行递归            //问题：不知道右子节点存不存在            if (this.right == null){
                   return null;            }            return this.right.search(value);        }    }    //查找待删除结点的父节点

查找待删除结点的父节点

/** * * @param value 需要查找的节点值 * @return  返回的是要删除的节点的父节点，如果没有就返回null */public Node searchParent(int value){
       //如果当前结点就是需要返回的父节点,说明子节点就是需要查找的结点    if ((this.left != null && this.left.value == value)            || (this.right != null && this.right.value == value)){
           return this;    }else if(this.left != null && value < this.value){
           return this.left.searchParent(value);        //如果返回的不是当前的结点，那就进行说明返回的是左子结点，或者是右子节点，        //故而应当是左子节点调用，或者是右子节点调用    }else if(this.right != null && value >= this.value){
           return this.right.searchParent(value);    }else {
           return null;    }}

删除target Node的左子树的最大节点，或者是右子树的最小节点

/**     * 找到当前子树的最小值，同时还要删除该结点     * @param node node传入的结点（为左二叉排序树的根节点）     * @return 返回以Node为根节点的二叉排序树的最小结点Z     * 个人认为：返回最小节点，然后在删除     */    public Node delRightTreeMin(Node node){
           Node target = node;        while (target.left != null){
               target = target.left;        }        Node temp = target;        //退出循环的target指向最小节点        delNode(target.value);        return target;        //找到了最小的值，那就返回该节点    }

class BestSearchTree

//查找要删除节点    public Node search(int value){
           if (root == null){
               return null;        }else{
               return root.search(value);        }    }    //查找要删除节点的父节点    public Node searchParent(int value){
           if(root == null){
               return null;        }else{
               return root.searchParent(value);        }    }

第二部分 根据情况进行分类删除

public void delNode(int value){
           if (root == null){
               return ;        }else{
               //1. 需求先去找到待删除的节点 targetNode            Node targetNode = search(value);            //2. 如果没有找到要删除的结点            if (targetNode == null){
                   return;            }            //情况一，没有父节点，根节点就是要找的点            if ((root.left == null && root.right == null) && root == targetNode){
                   root = null;                return;            }                if (parent.left != null && parent.left == targetNode){
                       parent.left = null;                }else if(parent.right != null && parent.right == targetNode){
                       parent.right = null;                }            }else if(targetNode.left != null && targetNode.right != null){
                   Node minNode = delRightTreeMin(targetNode.right);                if (parent.left != null && parent.left == targetNode){
                       parent.left = minNode;                }else if(parent.right != null && parent.right == targetNode){
                       parent.right = minNode;                }                //在父节点的层面上进行删除，                minNode.left = targetNode.left;                minNode.right = targetNode.right;                //在子节点层面上的操作          }else{
                   //情况四：删除只有一棵子树的特点                if (targetNode.right != null){
                       //仅有左子树，右子树为空                    if ( parent.left == targetNode){
                           parent.left = targetNode.right;                    }                    if ( parent.right == targetNode){
                           parent.right = targetNode.right;                    }                }else{
                       if ( parent.left == targetNode){
                           parent.left = targetNode.left;                    }                    if (parent.right == targetNode){
                           parent.right = targetNode.left;                    }                }            }        }    }

分析与总结

1. 技巧：双向查找，同时查找待删除结点和待删除结点的父节点，更加便于进行删除操作
2. 在顺序二叉树中，删除双子节点的非叶子节点，要用左子树的最大值，或者是右子树的最小值来代替，找到对应代替的值，删除，然后代替待删除结点targetNode
3. 对于情况较复杂的判定条件，直接用else来囊括，而不是用if（）具体判定条件
4. 思维导图
   

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