飞道的博客

二叉查找树

2020-05-05 16:11 358人阅读  评论(0)

目录

二叉查找树的定义

二叉查找树是一颗二叉树且满足一下条件：根节点的值大于其左子树中任意一个节点的值，小于其右节点中任意一节点的值，这一规则适用于二叉查找树中的每一个节点。

二叉查找树的实现

为了方便，该二叉查找树的数据类型是int。

search()和contains()

search(int x)方法：返回指定项x的节点。

  • x的值比根节点的值小，就和左子树的值对比。
  • x的值比根节点的值大，就和右子树的值对比。
  • x的值和根节点一样，就返回根节点。

contains(int x)方法：是否有项x的节点。

  • x的值比根节点的值小，就和左子树对比。
  • x的值比根节点的值大，就和右子树对比。
  • x的值和根节点一样，就返回true。
private TreeNode search(TreeNode t,int x){
        while (t != null){
            if (x < t.data){
                t = t.leftChild;
            }else if (x > t.data){
                t = t.rightChild;
            }else{
                return t;
            }
        }
        return null;
}

private boolean contains(TreeNode t,int x){
        while (t != null){
            if (x < t.data){
                t = t.leftChild;
            }else if (x > t.data){
                t = t.rightChild;
            }else {
                return true;
            }
        }
        return false;
}

findMin()和findMax()

findMin()方法：查找最小项的节点。

  • 从根开始只要有左节点就向左前进，终止点就是最小的元素。

findMax()方法：查找最大项的节点。

  • 从根开始只要有右节点就向右前进，终止点就是最大的元素。
 private TreeNode findMin(TreeNode t){
        if (t == null) return null;
        else if (t.leftChild == null) return t;
        return findMin(t.leftChild);
}

private TreeNode findMax(TreeNode t){
        if (t!= null){
            while (t.rightChild != null){
                t = t.rightChild;
            }
        }
        return t;
}

插入insert()

insert(int x)方法：插入一个项x的节点。

  • 我们可以像contains方法那样沿着树查找，然后根据节点的值大小插入到遍历的路径上的最后一个点上。


为了插入’6‘，我们遍历该树就像在运行contains。在项5的节点处，我们需要像右前进，但右边不存在子树，因此’6’不在这颗树上，从而这个位置就是所要插入的位置。

private void insert(TreeNode t,int x){
        TreeNode parent = null;
        TreeNode node = new TreeNode(x);
        while (t != null){
            parent = t;
            if (node.data < t.data){
                t = t.leftChild;
            }else{
                t = t.rightChild;
            }
        }

        if (node.data < parent.data){
            parent.leftChild = node;
        }else{
            parent.rightChild = node;
        }
}

删除remove()

remove(int x)方法：删除指定节点。
有3种情况：

  • 节点是一片树叶(没有儿子)：可以直接删除。
  • 节点有一个儿子：该节点可以在其父节点调整自己的指针以绕过该节点后被删除。
  • 节点有两个儿子：用其右子树的最小的数据代替该节点的数据，并删除那个节点。
private TreeNode remove(TreeNode t,int x){
        if (t == null) return t;

        if (t.data > x){
            t.leftChild= remove(t.leftChild,x);
        }else if(t.data < x){
            t.rightChild = remove(t.rightChild,x);
        }else if (t.leftChild != null && t.rightChild != null){     //被删除的节点有双子节点
            t.data = removeMin(t).data;
        }else {		//被删除的节点只有一个子节点或没有子节点
            t = (t.leftChild != null) ? t.leftChild : t.rightChild;
        }
        return t;
}

//删除树的最小节点，并返回被删除的节点。
private TreeNode removeMin(TreeNode t){
        TreeNode parent = null;                     //记录父结点
        if (t != null){
            while (t.leftChild != null){            //循环到最小节点
                parent = t;
                t = t.leftChild;
            }
        }
        if (parent != null){                        //父结点不为空。最小节点一定没有左节点
            parent.leftChild = t.rightChild;        //为空或右子树
        }

        return t;                                   //被删除的节点
}

可运行代码

public class BinarySearchTree {

    public TreeNode root;

    private class TreeNode{
        private int data;
        private TreeNode leftChild;
        private TreeNode rightChild;

        public TreeNode(){}
        public TreeNode(int data){this.data = data;}
    }

    /**
     * 返回指定项x的节点
     * @param x 项
     * @return 项的节点
     */
    public TreeNode search(int x){
        return search(root,x);
    }

    /**
     * 是否有项x的节点
     * @param x 项
     * @return 存在含有项的节点返回true，不存在返回false
     */
    public boolean contains(int x){
        return contains(root,x);
    }

    /**
     * 查找最小项的节点
     * @return 最小项的节点
     */
    public TreeNode findMin(){
        return findMin(root);
    }

    /**
     * 查找最大项的节点
     * @return 最大项的节点
     */
    public TreeNode findMax(){
        return findMax(root);
    }

    /**
     * 插入x到树中
     * @param x 插入的值
     */
    public void insert(int x){
        if (root == null) root = new TreeNode(x);
        else insert(root,x);
    }

    /**
     * 删除项x节点
     * @param x 项
     */
    public void remove(int x){
        remove(root,x);
    }

    /**
     * 先序遍历
     */
    public void preorderTraversal(){
        preorderTraversal(root);
    }

    /**
     * 中序遍历
     */
    public void inorderTraversal(){
        inorderTraversal(root);
    }

    /**
     * 后序遍历
     */
    public void postorderTraversal(){
        postorderTraversal(root);
    }




    /**
     * 返回指定项的节点
     * @param t 树
     * @param x 项
     * @return 项的节点
     */
    private TreeNode search(TreeNode t,int x){
        while (t != null){
            if (x < t.data){
                t = t.leftChild;
            }else if (x > t.data){
                t = t.rightChild;
            }else{
                return t;
            }
        }
        return null;
    }

    /**
     * 树t中是否有项x的节点
     * @param t 树
     * @param x 项
     * @return 存在含有项的节点返回true，不存在返回false
     */
    private boolean contains(TreeNode t,int x){
        while (t != null){
            if (x < t.data){
                t = t.leftChild;
            }else if (x > t.data){
                t = t.rightChild;
            }else {
                return true;
            }
        }
        return false;
    }

    /**
     * 寻找树中最小节点
     * @param t 树
     * @return 最小节点
     */
    private TreeNode findMin(TreeNode t){
        if (t == null) return null;
        else if (t.leftChild == null) return t;
        return findMin(t.leftChild);
    }

    /**
     * 寻找树中最大节点
     * @param t 树
     * @return 最大节点
     */
    private TreeNode findMax(TreeNode t){
        if (t!= null){
            while (t.rightChild != null){
                t = t.rightChild;
            }
        }
        return t;
    }

    /**
     * 插入操作，将x插入到树t中
     * @param t 树
     * @param x 项
     */
    private void insert(TreeNode t,int x){
        TreeNode parent = null;
        TreeNode node = new TreeNode(x);
        while (t != null){
            parent = t;
            if (node.data < t.data){
                t = t.leftChild;
            }else{
                t = t.rightChild;
            }
        }

        if (node.data < parent.data){
            parent.leftChild = node;
        }else{
            parent.rightChild = node;
        }
    }

    /**
     * 删除指定节点，可能会改变树的结构
     * @param t 树
     * @param x 项
     * @return
     */
    private TreeNode remove(TreeNode t,int x){
        if (t == null) return t;

        if (t.data > x){
            t.leftChild= remove(t.leftChild,x);
        }else if(t.data < x){
            t.rightChild = remove(t.rightChild,x);
        }else if (t.leftChild != null && t.rightChild != null){     //被删除的节点有双子节点
            t.data = removeMin(t).data;
        }else {     //被删除的节点只有一个子节点或没有子节点
            t = (t.leftChild != null) ? t.leftChild : t.rightChild;
        }
        return t;
    }

    /**
     * 删除树的最小节点，并返回被删除的节点。
     * @param t 树
     * @return 最小节点
     */
    private TreeNode removeMin(TreeNode t){
        TreeNode parent = null;                     //记录父结点
        if (t != null){
            while (t.leftChild != null){            //循环到最小节点
                parent = t;
                t = t.leftChild;
            }
        }
        if (parent != null){                        //父结点不为空。最小节点一定没有左节点
            parent.leftChild = t.rightChild;        //为空或右子树
        }

        return t;                                   //被删除的节点
    }

    /**
     * 递归的先序遍历
     * @param t 要遍历的树
     */
    private void preorderTraversal(TreeNode t){
        if (t != null){
            System.out.print(t.data+" ");
            preorderTraversal(t.leftChild);
            preorderTraversal(t.rightChild);
        }
    }

    /**
     * 递归的中序遍历
     * @param t 要遍历的树
     */
    private void inorderTraversal(TreeNode t){
        if (t != null){
            inorderTraversal(t.leftChild);
            System.out.print(t.data+" ");
            inorderTraversal(t.rightChild);
        }
    }

    /**
     * 递归的后序遍历
     * @param t 要遍历的树
     */
    private void postorderTraversal(TreeNode t){
        if (t != null){
            postorderTraversal(t.leftChild);
            postorderTraversal(t.rightChild);
            System.out.print(t.data+" ");
        }
    }


    public static void main(String[] args) {
        BinarySearchTree root = new BinarySearchTree();
        int[] arr = new int[]{7,2,1,10,5,3};
        for (int a : arr){
            root.insert(a);
        }
        System.out.print("第一次中序遍历：");
        root.inorderTraversal();

        System.out.print("\n最小项的节点的值："+root.findMin().data);
        System.out.print("\n最大项的节点的值："+root.findMax().data);
        System.out.print("\n是否存在项为'1'的节点："+root.contains(1));
        System.out.print("\n是否存在项为'1000'的节点："+root.contains(100));
        System.out.print("\n节点'7'的左子树的值为："+root.search(7).leftChild.data);

        root.insert(4);
        System.out.print("\n插入'4'之后的中序遍历：");
        root.inorderTraversal();

        root.remove(2);
        System.out.print("\n删除'2'之后的中序遍历：");
        root.inorderTraversal();
    }
}

运行结果：


转载：https://blog.csdn.net/weixin_43362650/article/details/105910193
查看评论
* 以上用户言论只代表其个人观点，不代表本网站的观点或立场