BST & AVL 二分搜索树 & 平衡二叉树的实现原理

原创

大学里的混子

修改于 2018-11-02 10:56:28

6590

修改于 2018-11-02 10:56:28

文章被收录于专栏：LeetCodeLeetCode

一.BST 二分搜索树实现原理

本文完整的实现了基本的BST，由于注重的是逻辑和原理的实现，所以没有采用泛型。注意方法的访问修饰符。

import java.util.LinkedList;
import java.util.Queue;

public class BST {
   //采用的是一个内部类 定义节点类型
    private class TreeNode{
    TreeNode left;
    TreeNode right;
    int val;
    public TreeNode(int val) {
        this.val = val;
       }
    }

    private TreeNode root;  // 根节点
    private int count;      // 树种的节点个数

    public boolean find(int target){
       return find(root,target);
    }

    public void insert(int value){
        root = insert(root,value);
    }

    public int size(){
        return count;
    }

    public boolean isEmpty(){
        return count == 0;
    }

    public void inOrder(){
        inOrder(root);
    }

    public void preOrder(){
        preOrder(root);
    }

    public void postOrder(){
        postOrder(root);
    }

    public void levelOrder(){
        levelOrder(root);
    }

    public int maxValue(){
        return maxValue(root);
    }
    
    public int minValue(){
        return minValue(root);
    }

    public void removeMax(){
        if (root == null) return;
        root = removeMax(root);
    }

    public void removeMin(){
        if (root == null) return;
        root = removeMin(root);
    }

    public boolean remove(int value){
        if (!find(value)) return false;
        root = remove(root,value);
        return true;
    }
    
    private boolean find(TreeNode root,int target){
        if (root == null) return false;
        if (root.val == target) return true;
        else if (root.val>target) return find(root.left,target);
        else return find(root.right,target);
    }
    
   //在以root为根节点的二叉树中插入value，并返回新的根节点
   private TreeNode insert(TreeNode root, int value){
        if (root == null) {
            count++;
            return new TreeNode(value);
        }
        if (root.val == value) root.val =value;
        else if (root.val > value) root.left = insert(root.left,value);
        else root.right = insert(root.right,value);
        return root;
    }

    //在以root为根节点的二叉树中删除节点为value的，并返回新的根节点
    private TreeNode remove(TreeNode root,int value){
        if (root == null) return null;
        if (root.val < value){
            root.right = remove(root.right,value);
            return root;
        }else if (root.val>value){
            root.left = remove(root.left,value);
            return root;
        }else {
        //此时就已经找到目标节点了，下面分为三种情况
        //1. 目标节点左子树为空
            if (root.left == null){
                TreeNode rightNode = root.right;
                count--;
                //下面这句可以不要
                root.right = null;
                return rightNode;
            }

        //2. 目标节点右子树为空
            if (root.right == null){
                TreeNode leftNode = root.left;
                count--;
                //下面这句可以不要
                root.left = null;
                return leftNode;
            }
        //3. 目标节点左右子树都不为空
            TreeNode successor = new TreeNode(minValue(root.right));
            count++;
            successor.right = removeMin(root.right);
            successor.left = root.left;
            root.left = root.right = null;
            count--;
            return successor;
        }
    }

    //在以root为根节点的二叉树中删除最大的节点，并返回新的根节点
    private TreeNode removeMax(TreeNode root){
        if (root.right == null ) {
            TreeNode leftNode = root.left;
            root.left = null;
            count--;
            return leftNode;
        }
        root.right = removeMax(root.right);
        return root;
    }
    
    //在以root为根节点的二叉树中删除最小的节点，并返回新的根节点
    private TreeNode removeMin(TreeNode root){
        if (root.left == null ) {
            TreeNode rightNode = root.right;
            root.right = null;
            count--;
            return rightNode;
        }
        root.left = removeMin(root.left);
        return root;
    }

    //在以root为根节点的二叉树中找到最大的节点值，并返回
    private int maxValue(TreeNode root){
        assert count!=0;
        if (root.right == null) return root.val;
        return maxValue(root.right);
    }

    //在以root为根节点的二叉树中找到最大的节点值，并返回
    private int minValue(TreeNode root){
        assert count!=0;
        if (root.left == null) return root.val;
        return minValue(root.left);
    }
    
    //以root为根节点的二叉树的层序遍历
    private void levelOrder(TreeNode root){
        if (root==null) return;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()){
            TreeNode temp = queue.remove();
            System.out.println(temp.val);
            if (temp.left!=null){
                queue.add(temp.left);
            }
            if (temp.right!=null){
                queue.add(temp.right);
            }
        }
    }

    //以root为根节点的二叉树的中序遍历
    private void inOrder(TreeNode root){
        if (root == null) return;
        inOrder(root.left);
        System.out.println(root.val);
        inOrder(root.right);
    }

    //以root为根节点的二叉树的前序遍历
    private void preOrder(TreeNode root){
        if (root == null) return;
        System.out.println(root.val);
        inOrder(root.left);
        inOrder(root.right);
    }

    //以root为根节点的二叉树的后序遍历
    private void postOrder(TreeNode root){
        if (root == null) return;
        inOrder(root.left);
        inOrder(root.right);
        System.out.println(root.val);
    }
  }

一种非常容易犯错的地方

在执行删除操作的时候，我们是否这一这么写呢？


    public boolean delete(int value){
        return delete(root,value);
    }

    private boolean delete(TreeNode root,int value){
        if (root ==null) return false;
        if (root.val == value) {
            return deleteNode(root);
        }
        else if (root.val>value){
            return delete(root.left,value);
        }else {
            return delete(root.right,value);
        }
    }

    private boolean deleteNode(TreeNode node){
        if (node.left == null){
            System.out.println(node.val);
            node = node.left;
        }else if (node.right == null){
            node = node.right;
        }else {
            TreeNode temp = node.right;
            while (temp.left!=null){
                temp = temp.left;
            }
            node.val = temp.val;
            temp = null;
        }
        return true;
    }

private boolean delete(TreeNode root,int value)函数与查找的函数类似，是找到要删除的节点，找到删除的节点后，调用
private boolean deleteNode(TreeNode node)函数，看起来这个思路是非常的清晰，甚至比我上面写的思路更加的优雅。实际
上这样的思路是没有问题的。但是在java中， 删除节点操作并不是那么容易，这与java没有指针有关。问题就是出现在函数
private boolean deleteNode(TreeNode node)之中，我们将待删除的节点当做参数传进来，能够用操作原来的数吗？不能。

为了更加清楚的解释，我们看下面的一个例子：

public class Foo {
    public static void main (String [] args)  {
        StringBuffer a = new StringBuffer ("A");
        StringBuffer b = new StringBuffer ("B");
        operate (a,b);
        system.out.printIn{a +" "+b};

   static void operate (StringBuffer x, StringBuffer y)  {
        x.append(y);
        y = x;
    }
}

大家想一下打印出来的是什么？

AB B

为什么不是AB A呢？

变量a\b\x\y中存储的是StringBuffer变量的引用而不是一个StringBuffer对象。根据非基本类型参数传递为引用传递的规则，operate接收的参数只是StringBuffer对象的引用.因此可以理解为x、a都是指向同一个对象;b、y也是指向同一个StringBuffer对象，所以x.append(y)将导致x和a同指的StringBuffer对象改变（增加"B"）；而y=x只是让变量y改变指向为和x相同的StringBuffer对象，而y原来所指的对象并不会发生任何改变。

y原来所指的对象并不会发生任何改变，相必这样总算清楚了，private boolean deleteNode(TreeNode node)；将node作为参数，执行操作：

node = node.left;
node = node.right;

并不会对原来的二叉树做出什么改变。因此这样的做法是错的，在C中可以采用这种方式，删除节点是没有问题的。

二：AVL 平衡二叉树的实现原理

AVL树将在构建树的时候就将不平衡消灭了，实际上，AVL树与BST树的改进就只是在insert()函数上，下面重点的讲解insert()函数。

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

其他

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

其他

登录后参与评论

0 条评论

热度