精华内容
下载资源
问答
  • 二叉树由节点(Node)组成,每个节点包含一个“左”指针(left)、“右”指针(right)和一个数据元素(e)。“根”(root)指针指向中最顶端的节点。左右指针递归地指向较小的两边的...上图是一棵二分搜索(BST):二分搜索...

    二叉树由节点(Node)组成,每个节点包含一个“左”指针(left)、“右”指针(right)和一个数据元素(e)。

    “根”(root)指针指向树中最顶端的节点。左右指针递归地指向较小的

    两边的“子树”。空指针表示没有元素的二叉树——空树。正式的递归定义是:二叉树要么为空(由空指针表示),要么由单个节点构成,

    其中左指针和右指针(前面是递归定义)都指向一个二叉树。

    87556058279fbae446c7e2ba7bea97c4.png

    上图是一棵二分搜索树(BST):

    二分搜索树是二叉树

    二分搜索树的每个节点的值都大于其左子树的所有节点的值,小于其右子树的所有节点的值(1,3,4)<5

    其中(1,4,6)是树的叶子节点,因为其节点的left和right指针是空子树。

    由于二分搜索树具有元素之间比较的特点,所以二分搜索树存储的元素类型应该要具有可比较性。可以为二分搜索树添加泛型E,并且E extends Comparable

    这里我的二分搜索树存储的元素类型就指定为int,且其他方法都用递归实现

    public class BST {

    private class Node {

    int e;

    Node left;

    Node right;

    public Node(int e) {

    this.e = e;

    left = null;

    right = null;

    }

    }

    private Node root;

    private int size;

    public BST() {

    this.root = null;

    this.size = 0;

    }

    }

    查找方法:

    public boolean lookup(Node node,int target){

    //最基本的情况:空树,找不到目标,所以返回false

    if (node == null)

    return false;

    //如果不为空,则根据值来判断

    else {

    if (target == node.e)

    return true;

    else {

    if (target < node.e)

    return lookup(node.left,target);

    else return lookup(node.right,target);

    }

    }

    }

    插入元素方法:

    public void insert(int data){

    root = insert(root,data);

    }

    private Node insert(Node node,int data){

    //如果节点是空的,则返回一个新的节点,值为data

    if (node == null){

    size++;

    return new Node(data);

    }

    //如果节点不为空,则根据data和e对比

    else {

    if (data < node.e) node.left = insert(node.left,data);

    else node.right = insert(node.right,data);

    return node;

    }

    }

    getSize方法:

    public int getSize(){

    return size;

    }

    获取树的最大深度方法:

    public int maxDepth(){

    return maxDepth(root);

    }

    private int maxDepth(Node node){

    if (node == null)

    return 0;

    else {

    int lDepth = maxDepth(node.left);

    int rDepth = maxDepth(node.right);

    return Math.max(lDepth,rDepth)+1;

    }

    }

    先序遍历、中序遍历、后序遍历:

    public void preOrder(){

    preOrder(root);

    }

    private void preOrder(Node node){

    if (node == null)

    return;

    System.out.println(node.e);

    preOrder(node.left);

    preOrder(node.right);

    }

    public void inOrder(){

    inOrder(root);

    }

    private void inOrder(Node node){

    if (node==null)

    return;

    inOrder(node.left);

    System.out.println(node.e);

    inOrder(node.right);

    }

    public void postOrder(){

    postOrder(root);

    }

    private void postOrder(Node node){

    if (node==null)

    return;

    postOrder(node.left);

    postOrder(node.right);

    System.out.println(node.e);

    }

    展开全文
  • “根”(root)指针指向中最顶端的节点。左右指针递归地指向较小的两边的“子树”。空指针表示没有元素的二叉树——空。正式的递归定义是:二叉树要么为空(由空指针表示),要么由单个节点构成,其中左指针和右指针...

    二叉树由节点(Node)组成,每个节点包含一个“左”指针(left)、“右”指针(right)和一个数据元素(e)。

    “根”(root)指针指向树中最顶端的节点。左右指针递归地指向较小的

    两边的“子树”。空指针表示没有元素的二叉树——空树。正式的递归定义是:二叉树要么为空(由空指针表示),要么由单个节点构成,

    其中左指针和右指针(前面是递归定义)都指向一个二叉树。

    87556058279fbae446c7e2ba7bea97c4.png

    上图是一棵二分搜索树(BST):

    二分搜索树是二叉树

    二分搜索树的每个节点的值都大于其左子树的所有节点的值,小于其右子树的所有节点的值(1,3,4)<5

    其中(1,4,6)是树的叶子节点,因为其节点的left和right指针是空子树。

    由于二分搜索树具有元素之间比较的特点,所以二分搜索树存储的元素类型应该要具有可比较性。可以为二分搜索树添加泛型E,并且E extends Comparable

    这里我的二分搜索树存储的元素类型就指定为int,且其他方法都用递归实现

    public class BST {

    private class Node {

    int e;

    Node left;

    Node right;

    public Node(int e) {

    this.e = e;

    left = null;

    right = null;

    }

    }

    private Node root;

    private int size;

    public BST() {

    this.root = null;

    this.size = 0;

    }

    }

    查找方法:

    public boolean lookup(Node node,int target){

    //最基本的情况:空树,找不到目标,所以返回false

    if (node == null)

    return false;

    //如果不为空,则根据值来判断

    else {

    if (target == node.e)

    return true;

    else {

    if (target < node.e)

    return lookup(node.left,target);

    else return lookup(node.right,target);

    }

    }

    }

    插入元素方法:

    public void insert(int data){

    root = insert(root,data);

    }

    private Node insert(Node node,int data){

    //如果节点是空的,则返回一个新的节点,值为data

    if (node == null){

    size++;

    return new Node(data);

    }

    //如果节点不为空,则根据data和e对比

    else {

    if (data < node.e) node.left = insert(node.left,data);

    else node.right = insert(node.right,data);

    return node;

    }

    }

    getSize方法:

    public int getSize(){

    return size;

    }

    获取树的最大深度方法:

    public int maxDepth(){

    return maxDepth(root);

    }

    private int maxDepth(Node node){

    if (node == null)

    return 0;

    else {

    int lDepth = maxDepth(node.left);

    int rDepth = maxDepth(node.right);

    return Math.max(lDepth,rDepth)+1;

    }

    }

    先序遍历、中序遍历、后序遍历:

    public void preOrder(){

    preOrder(root);

    }

    private void preOrder(Node node){

    if (node == null)

    return;

    System.out.println(node.e);

    preOrder(node.left);

    preOrder(node.right);

    }

    public void inOrder(){

    inOrder(root);

    }

    private void inOrder(Node node){

    if (node==null)

    return;

    inOrder(node.left);

    System.out.println(node.e);

    inOrder(node.right);

    }

    public void postOrder(){

    postOrder(root);

    }

    private void postOrder(Node node){

    if (node==null)

    return;

    postOrder(node.left);

    postOrder(node.right);

    System.out.println(node.e);

    }

    展开全文
  • Java实现二分搜索

    2019-07-27 22:06:58
    Java实现二分搜索二分搜索的定义二分搜索的代码结构向二分搜索添加元素(递归实现)对添加元素代码的简化(如果递归功底深厚)查看二分搜索中是否还有元素e(递归)二分搜索的前序遍历(递归)基于前序...

    二分搜索树的定义

    #二分搜索树是二叉树
    #二分搜索树的每个节点的值:
    1.大于左子树的所有节点的值
    2.小于右子树的所有节点的值

    #存储的元素要具有可比较性。例如:如果存储学生对象,可以比较学号。

    二分搜索树的代码结构

      public class BST<E extends Comparable<E>> { private Node root;
        private int size;
    
        private class Node {
            public E e;
            public Node left, right;
    
            public Node(E e) {
                this.e = e;
                this.left = null;
                this.right = null;
            }
        }
    
        public BST() {
            this.root = null;
            this.size = 0;
        }
    
        public int getSize() {
            return size;
        }
    
        public boolean isEmpty() {
            return size == 0;
        }
    
    }
    
    

    向二分搜索树添加元素(递归实现)

    public void add(E e) {
        if (root == null) {
            root = new Node(e);
            size++;
        } else
            add(root, e);
    }
    
    private void add(Node node, E e) {
    //递归终止条件
        if (e.equals(node.e))
            return;
    
        else if (e.compareTo(node.e) < 0 && node.left == null) {
            node.left = new Node(e);
            size++;
            return;
        } else if (e.compareTo(node.e) > 0 && node.right == null) {
            node.left = new Node(e);
            size++;
            return;
        }
    //递归调用
        if (e.compareTo(node.e) < 0)
            add(node.left, e);
        else//e.compareTo(node.e) > 0
    
            add(node.right, e);
    }
    

    对添加元素代码的简化(如果递归功底深厚)

    public void add(E e) {
        root = add(root, e);
    }
    
    private Node add(Node node, E e) {
    
        if (node == null) {
            size++;
            return new Node(e);
        }
    
        if (e.compareTo(node.e) < 0)
            node.left = add(node.left, e);
        else if (e.compareTo(node.e) > 0)
            node.right = add(node.right, e);
    
        return node;
    }
    

    查看二分搜索树中是否还有元素e(递归)

    public boolean contains(E e) {
        return contains(root, e);
    }
    
    private boolean contains(Node node, E e) {
        if (node == null)
            return false;
    
        if (e.compareTo(node.e) == 0)
            return true;
    
        
        else if (e.compareTo(node.e) < 0)
            return contains(node.left, e);
        else //e.compareTo(node.e) > 0
            return contains(node.right, e);
    }
    

    二分搜索树的前序遍历(递归)

    public void preorderTraversal() {
        preorderTraversal(root);
    }
    
    private void preorderTraversal(Node node) {
    
        if (node == null)
            return;
    
        System.out.println(node.e);
        preorderTraversal(node.left);
        preorderTraversal(node.right);
    }
    

    基于前序遍历重写toString

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        generateBSTString(root, 0, res);
        return res.toString();
    }
    
    private void generateBSTString(Node node, int depth, StringBuilder res) {
        if (node == null) {
            res.append(generateDepthString(depth) + "Null\n");
            return;
        }
        res.append(generateDepthString(depth)+node.e + "\n");
    
        generateBSTString(node.left,depth+1,res);
        generateBSTString(node.right,depth+1,res);
    }
    
    private String generateDepthString(int depth) {
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < depth; i++)
            res.append("-");
        return res.toString();
    }
    

    二分搜索树的中序遍历

    public void intermediateTraversal(){
        intermediateTraversal(root);
    }
    
    private void intermediateTraversal(Node node) {
        if (node==null)
            return;
    
        intermediateTraversal(node.left);
        System.out.println(node.e);
        intermediateTraversal(node.right);
    }
    

    二分搜索树的后序遍历

    public void postorderTraversal(){
        postorderTraversal(root);
    }
    
    private void postorderTraversal(Node node) {
    
        if (node==null)
            return;
    
        postorderTraversal(node.left);
        postorderTraversal(node.right);
        System.out.println(node.e);
    }
    

    二分搜索树的前序遍历(非递归)

    说明:
    1.先将根节点压入栈,出栈,记录,并将左右孩子节点压入(先压入右孩子节点,后压入左孩子节点)
    2.出栈(即左孩子节点(栈顶元素)先出栈),记录,并查看左孩子节点是否有孩子节点,仍然是右孩子节点先压入栈,然后压入左孩子节点。如果没有孩子,则出栈现在栈顶元素(右孩子节点),记录。
    3.循环以上过程
    如下图:
    28入栈,出栈,记录。30,16入栈,16为栈顶,出栈,记录,并将16的左右孩子节点13和22入栈。13为栈顶,出栈,此时13没有左右孩子节点,22出栈,记录。22没有左右孩子,30出栈,记录。
    压入30的左右孩子节点。此时,栈顶元素为30的左孩子节点,即29,29出栈,记录。由于29没有孩子节点,42出栈,记录。42没有孩子节点,并且此时栈为空,前序遍历结束。
    在这里插入图片描述
    代码实现:

    public void preorderTraversalNR() {
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            Node cur = stack.pop();
            System.out.println(cur.e);
    
            if (cur.right != null)
                stack.push(cur.right);
            if (cur.left != null)
                stack.push(cur.left);
        }
    }
    

    由于使用了java中的栈,需要在代码前加:
    import java.util.Stack;

    二分搜索树的层序遍历(非递归)(广度优先遍历)

    说明:(使用辅助数据结构:队列)
    1.先将根节点入队,出队,记录。并将根节点的左右孩子节点入队(左孩子节点先入队,右孩子节点后入队)
    2.入队完成后,队首元素出队,记录,并将其左右孩子入队(仍然按照左先右后的顺序)
    3.由于队列先进先出的性质,每次都是左孩子节点先出队,右孩子后出队。并且左孩子节点和右孩子节点都入队,左孩子节点出队后,压入左孩子节点的左右孩子节点之前,上一层右孩子节点为队首,所以下层的左右孩子节点在上层的右孩子节点之后,所以可以做到层序遍历。

    如下图:
    根节点28入队,出队并记录,并将左右孩子节点16,30入队。
    左孩子节点16出队,记录。并将16的左右孩子节点13,22入队。
    此时30位队首元素,出队,记录,并入队30的左右孩子节点。
    此时队首元素为13,出队,记录,入队13的左右孩子节点,由于没有孩子节点,所以此时什么都不做。然后去队首,出队队首元素22,没有孩子节点,出队,记录,没有孩子节点,什么都不做。出队队首元素29,记录,没有孩子节点,什么都不做。出队队首元素42,记录。没有孩子节点,什么都不做。出队队首元素,由于此时队列为空,遍历结束。

    在这里插入图片描述
    代码实现:

    public void levelTraversal(){
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()){
            Node cur = queue.remove();
            System.out.println(cur.e);
    
            if (cur.left!=null)
                queue.add(cur.left);
            if (cur.right!=null)
                queue.add(cur.right);
        }
    }
    

    查找二分搜索树中的最大最小值

    最小值:一直向左一直到null之前
    最大值:一直向右一直到null之前

    情况1:
    在这里插入图片描述
    情况2:
    在这里插入图片描述
    #查找最小值(递归)

    public E minimumValue(){
    if (size == 0)
        throw new IllegalArgumentException("BST is Empty!");
    
        return minimumValue(root);
    }
    
    private E minimumValue(Node node) {
        if (node.left==null)
            return node.e;
        return minimumValue(node.left);
    }
    

    #查找最小值(非递归)

    public E minimumValueNR() {
        if (size == 0)
            throw new IllegalArgumentException("BST is Empty!");
    
        Node cur = root;
        while (cur.left!=null)
            cur = cur.left;
        return cur.e;
    }
    

    #查找最大值(递归)

    public E maximumValue(){
    if (size == 0)
        throw new IllegalArgumentException("BST is Empty!");
    
        return maximumValue(root);
    }
    
    private E maximumValue(Node node) {
        if (node.right==null)
            return node.e;
        return maximumValue(node.right);
    }
    

    #查找最大值(非递归)

    public E maximumValueNR() {
        if (size == 0)
            throw new IllegalArgumentException("BST is Empty!");
    
        Node cur = root;
        while (cur.right != null)
            cur = cur.right;
        return cur.e;
    }
    

    删除二分搜索树的最小值与最大值

    #删除最小值
    情况1:最小值为叶子节点(如下图)
    操作:直接删除就好了
    在这里插入图片描述
    情况2:最小值为非叶子节点(如下图)
    操作:将删除节点的右子树变成删除节点的父亲节点的左子树
    在这里插入图片描述
    情况2删除后:(如下图)
    在这里插入图片描述
    #删除最小值(递归)

    public E removeMin() {
        E ret = minimumValueNR();
        root = removeMin(root);
        return ret;
    }
    
    //删除以node为根的最小值
    //返回删除节点后新的二分搜索树的跟
    private Node removeMin(Node node) {
    
        if (node.left==null){
            Node rightNode = node.right;
            node.right=null;
            size--;
            return rightNode;
        }
        node.left = removeMin(node.left);
        return node;
    }
    

    #删除最小值(非递归)

    public E removeMinNR() {
        E ret = minimumValueNR();
        Node cur = root;
        if (cur.left == null) {
            Node rightNode = cur.right;
            cur.right = null;
            root = rightNode;
            size--;
            return ret;
        }
        while (cur.left.left != null) {
            cur = cur.left;
    }
        if (cur.left.right != null) {
            Node rightNode = cur.left.right;
            cur.left = rightNode;
        } else
            cur.left = null;
    
        size--;
        return ret;
    }
    

    #删除最大值
    情况1:最大值为叶子节点(如下图)
    操作:直接删除就好了
    在这里插入图片描述
    情况二:最大值为非叶子节点(如下图)
    操作:将删除节点的左子树变成删除节点的父亲节点的右子树
    在这里插入图片描述
    情况2删除后(如下图):
    在这里插入图片描述
    #删除最大值(递归)

    public E removeMax() {
        E ret = maximumValueNR();
        root = removeMax(root);
        return ret;
    }
    //删除以node为根的最大值
    //返回删除节点后新的二分搜索树的跟
    private Node removeMax(Node node) {
        if (node.right == null) {
            Node leftNode = node.left;
            node.left = null;
            size--;
            return leftNode;
        }
        node.right = removeMax(node.right);
        return node;
    }
    

    #删除最大值(非递归)

    public E removeMaxNR() {
    
        E ret = maximumValueNR();
        Node cur = root;
        if (cur.right == null) {
            Node leftNode = cur.left;
            cur.left = null;
            root = leftNode;
            size--;
            return ret;
        }
        while (cur.right.right != null)
            cur = cur.right;
    
        if (cur.right.left != null) {
            Node leftNode = cur.right.left;
            cur.right = leftNode;
        } else
            cur.right = null;
        size--;
        return ret;
    }
    

    删除二分搜索树的任意元素

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    删除任意一个元素

    public void remove(E e) {
        root = remove(root, e);
    }
    
    private Node remove(Node node, E e) {
    
        if (node == null)
            return null;
    
        if (e.compareTo(node.e) < 0) {
            node.left = remove(node.left, e);
            return node;
        } else if (e.compareTo(node.e) > 0) {
            node.right = remove(node.right, e);
            return node;
        } else {//e.compareTo(node.e) == 0
            if (node.left == null) {
                Node rightNode = node.right;
                node.right = null;
                size--;
                return rightNode;
            }
            if (node.right == null) {
                Node leftNode = node.left;
                node.left = null;
                size--;
                return leftNode;
            }
    
            Node successor = minimumValue(node.right);
            successor.right = removeMin(node.right);
            successor.left = node.left;
    
            node.left = node.right = null;
            return successor;
        }
    
    }
    

    通篇代码整合(终结版)

    package com.cc;
    
    import java.util.LinkedList;
    import java.util.Queue;
    import java.util.Stack;
    
    /**
     * @Author: 李立建
     * @Date: 2019/7/26 22:03
     * @Version 1.0
     */
    public class BST<E extends Comparable<E>> {
    
        private Node root;
        private int size;
    
        private class Node {
            public E e;
            public Node left, right;
    
            public Node(E e) {
                this.e = e;
                this.left = null;
                this.right = null;
            }
    
            @Override
            public String toString() {
                return e.toString();
            }
        }
    
        public BST() {
            this.root = null;
            this.size = 0;
        }
    
        public int getSize() {
            return size;
        }
    
        public boolean isEmpty() {
            return size == 0;
        }
    
        public void add(E e) {
            root = add(root, e);
        }
    
        private Node add(Node node, E e) {
    
            if (node == null) {
                size++;
                return new Node(e);
            }
    
            if (e.compareTo(node.e) < 0)
                node.left = add(node.left, e);
            else if (e.compareTo(node.e) > 0)
                node.right = add(node.right, e);
    
            return node;
        }
    
        public boolean contains(E e) {
            return contains(root, e);
        }
    
        private boolean contains(Node node, E e) {
            if (node == null)
                return false;
    
            if (e.compareTo(node.e) == 0)
                return true;
    
    
            else if (e.compareTo(node.e) < 0)
                return contains(node.left, e);
            else //e.compareTo(node.e) > 0
                return contains(node.right, e);
        }
    
        public void preorderTraversal() {
            preorderTraversal(root);
        }
    
        private void preorderTraversal(Node node) {
    
            if (node == null)
                return;
    
            System.out.println(node.e);
            preorderTraversal(node.left);
            preorderTraversal(node.right);
        }
    
    
        public void preorderTraversalNR() {
            Stack<Node> stack = new Stack<>();
            stack.push(root);
            while (!stack.isEmpty()) {
                Node cur = stack.pop();
                System.out.println(cur.e);
    
                if (cur.right != null)
                    stack.push(cur.right);
                if (cur.left != null)
                    stack.push(cur.left);
            }
        }
    
    
        public void intermediateTraversal() {
            intermediateTraversal(root);
        }
    
        private void intermediateTraversal(Node node) {
            if (node == null)
                return;
    
            intermediateTraversal(node.left);
            System.out.println(node.e);
            intermediateTraversal(node.right);
        }
    
        public void postorderTraversal() {
            postorderTraversal(root);
        }
    
        private void postorderTraversal(Node node) {
    
            if (node == null)
                return;
    
            postorderTraversal(node.left);
            postorderTraversal(node.right);
            System.out.println(node.e);
        }
    
    
        public void levelTraversal() {
            Queue<Node> queue = new LinkedList<>();
            queue.add(root);
            while (!queue.isEmpty()) {
                Node cur = queue.remove();
                System.out.println(cur.e);
    
                if (cur.left != null)
                    queue.add(cur.left);
                if (cur.right != null)
                    queue.add(cur.right);
            }
        }
    
        public E minimumValue() {
            if (size == 0)
                throw new IllegalArgumentException("BST is Empty!");
            return minimumValue(root).e;
        }
    
        private Node minimumValue(Node node) {
            if (node.left == null)
                return node;
            return minimumValue(node.left);
        }
    
        public E minimumValueNR() {
            if (size == 0)
                throw new IllegalArgumentException("BST is Empty!");
    
            Node cur = root;
            while (cur.left != null)
                cur = cur.left;
            return cur.e;
        }
    
    
        public E maximumValue() {
            if (size == 0)
                throw new IllegalArgumentException("BST is Empty!");
            return maximumValue(root);
        }
    
        private E maximumValue(Node node) {
            if (node.right == null)
                return node.e;
            return maximumValue(node.right);
        }
    
        public E maximumValueNR() {
            if (size == 0)
                throw new IllegalArgumentException("BST is Empty!");
    
            Node cur = root;
            while (cur.right != null)
                cur = cur.right;
            return cur.e;
        }
    
    
        public E removeMin() {
            E ret = minimumValueNR();
            root = removeMin(root);
            return ret;
        }
    
        public Node removeMin(Node node) {
    
            if (node.left == null) {
                Node rightNode = node.right;
                node.right = null;
                size--;
                return rightNode;
            }
            node.left = removeMin(node.left);
            return node;
        }
    
        public E removeMinNR() {
            E ret = minimumValueNR();
            Node cur = root;
    
            if (cur.left == null) {
                Node rightNode = cur.right;
                cur.right = null;
                root = rightNode;
                size--;
                return ret;
            }
    
    
            while (cur.left.left != null) {
                cur = cur.left;
            }
    
            if (cur.left.right != null) {
                Node rightNode = cur.left.right;
                cur.left = rightNode;
            } else
                cur.left = null;
    
            size--;
            return ret;
        }
    
        public E removeMax() {
            E ret = maximumValueNR();
            root = removeMax(root);
            return ret;
        }
    
        private Node removeMax(Node node) {
            if (node.right == null) {
                Node leftNode = node.left;
                node.left = null;
                size--;
                return leftNode;
            }
            node.right = removeMax(node.right);
            return node;
        }
    
    
        public E removeMaxNR() {
    
            E ret = maximumValueNR();
    
            Node cur = root;
    
            if (cur.right == null) {
                Node leftNode = cur.left;
                cur.left = null;
                root = leftNode;
                size--;
                return ret;
            }
    
            while (cur.right.right != null)
                cur = cur.right;
    
            if (cur.right.left != null) {
                Node leftNode = cur.right.left;
                cur.right = leftNode;
            } else
                cur.right = null;
            size--;
            return ret;
        }
    
        public void remove(E e) {
            root = remove(root, e);
        }
    
        private Node remove(Node node, E e) {
    
            if (node == null)
                return null;
    
            if (e.compareTo(node.e) < 0) {
                node.left = remove(node.left, e);
                return node;
            } else if (e.compareTo(node.e) > 0) {
                node.right = remove(node.right, e);
                return node;
            } else {//e.compareTo(node.e) == 0
                if (node.left == null) {
                    Node rightNode = node.right;
                    node.right = null;
                    size--;
                    return rightNode;
                }
                if (node.right == null) {
                    Node leftNode = node.left;
                    node.left = null;
                    size--;
                    return leftNode;
                }
    
                Node successor = minimumValue(node.right);
                successor.right = removeMin(node.right);
                successor.left = node.left;
    
                node.left = node.right = null;
                return successor;
            }
    
        }
    
    
        @Override
        public String toString() {
            StringBuilder res = new StringBuilder();
            generateBSTString(root, 0, res);
            return res.toString();
        }
    
        private void generateBSTString(Node node, int depth, StringBuilder res) {
            if (node == null) {
                res.append(generateDepthString(depth) + "Null\n");
                return;
            }
            res.append(generateDepthString(depth) + node.e + "\n");
    
            generateBSTString(node.left, depth + 1, res);
            generateBSTString(node.right, depth + 1, res);
        }
    
        private String generateDepthString(int depth) {
            StringBuilder res = new StringBuilder();
            for (int i = 0; i < depth; i++)
                res.append("-");
            return res.toString();
        }
    
    
    }
    
    
    展开全文
  • java实现二分搜索

    2021-01-16 17:43:50
    二分搜索方面的实现,我更关注递归实现 在现代计算机下,使用递归可能看不出来,但是在极端情况下还是可以看出来的 向二分搜索中添加新的元素e /** * 向二分搜索中添加新的元素e */ pu

    二分搜索树

    • 我们的二分搜索树不包含重复的元素

    ​ 如果想包含重复元素的话,只需要定义:

    ​ 左子树小于等于节点;或者右子树大于等于节点

    我自己之前学习的数组和链表是可以拥有重复元素的

    • 二分搜索树添加元素的非递归写法,和链表很像
    • 二分搜索树方面的实现,我更关注递归实现

    在现代计算机下,使用递归可能看不出来,但是在极端情况下还是可以看出来的


    向二分搜索树中添加新的元素e

      /**
         * 向二分搜索树中添加新的元素e
         */
        public void add(E e){
            if(root==null){
                root=new Node(e);
                size++;
            }else{
                add(root ,e);
    
            }
        }
    
        /**
         * 向以node为根的二分搜索树种插入元素e,递归算法
         */
         private void add(Node node,E e){
             if(e.equals(node.e))
                 return;
             else if(e.compareTo(node.e)<0&&node.left==null){
                 node.left=new Node(e);
                 size++;
                 return;
             }else if (e.compareTo(node.e)>0&&node.right==null){
                 node.right=new Node(e);
                 size++;
                 return;
             }
             //以上代码是递归终结条件
             
             if(e.compareTo(e)<0)
                 add(node.left,e);
             else //e.compareTo(e)>0
           
                add(node.right,e);
         }
    
    
    

    现在这个添加代码还是相对比较复杂的。

    改进后的代码

     public void add(E e){
            root=add(root,e);
        }
    
    
          /**
         * 向以node为根的二分搜索树种插入元素e,递归算法
         * 返回插入信节点后二分搜索树的根
         *
         */
        private Node add(Node node ,E e ){
            //如果所在节点是空,就创建一个新的节点,返回给上一个递归调用
            if(node==null){
                size++;
                return new Node(e);
            }
    
            if(node.e.compareTo(e)<0){
                //比较e和当前节点的大小,判断左右孩子
                //如果是左孩子,将新创建好的节点,连接到左孩子
                //右边同理
                node.left  = add(node.left, e);
            }else if(node.e.compareTo(e)<0){
                node.right=add(node.right,e);
            }
    
            return node;
        }
    
    

    二分搜索树中是否包含元素e

    /**
         * 看二分搜索树中是否包含元素e
         */
        public boolean contains(E e){
            return contains(root,e);
        }
    
        /**
         * 看以node为根的二分搜索树中是否包含元素e,递归算法
         */
        private boolean contains(Node node, E e){
            if(node==null)
                return false;
            if(node.e.compareTo(e)==0)
                return  true;
            else if(node.e.compareTo(e)<0)
                
               return  contains(node.left,e);
            else //root.e.compareTo(e)>0
               return contains(node.right,e);
    
    
        }
    

    前序遍历

     /**
         * 二分搜索数的前序遍历
         */
        public void preOrder(){
            preOrder(root);
            
        }
        /**
         * 前序遍历以node为根的二分搜索树,递归算法
         * @param node
         */
        private void preOrder(Node node){
            if(node==null)
                return;
            System.out.println(node.e);
            preOrder(node.left);
            preOrder(node.left);
        }
        
    
    

    前序遍历将二分搜索树打印

    @Override
        public String toString() {
            StringBuilder res=new StringBuilder();
            generateBSTString(root ,0,res);
            return res.toString();
        }
    
        /**
         * 生成以node为根节点,深度为depth的描述二叉树的字符串
         * @param node
         * @param depth
         * @param res
         */
        private void generateBSTString(Node node, int depth, StringBuilder res) {
            if(node==null){
                res.append(generateDepthString(depth)+"null\n");
                return;
            }
    
            res.append(generateDepthString(depth)+node.e+"\n");
            generateBSTString(node.left,depth+1,res);
            generateBSTString(node.right,depth+1,res);
        }
    
        private String generateDepthString(int depth) {
            StringBuilder res=new StringBuilder();
            for (int i = 0; i < depth; i++) {
                res.append("--");
    
            }
            return res.toString();
    
        }
    

    输出结果:

    5
    --3
    ----2
    ------null
    ------null
    ----4
    ------null
    ------null
    --6
    ----null
    ----8
    ------null
    ------null
    
    ‘--’代表深度为1
    ‘----’代表深度为2
    以‘--’ 为一个深度,以此类推。
    

    前序遍历的非递归方法

    利用栈进行遍历

      /**
         * 前序遍历非递归的方法
         */
        public void preOrderNR() {
            Stack<Node> stack = new Stack<>();
            stack.push(root);
            while (!stack.isEmpty()) {
                Node cur = stack.pop();
                System.out.println(cur.e);
    
                if (cur.right != null)
                    stack.push(cur.right);
                if (cur.left != null)
                    stack.push(cur.left);
            }
        }
    

    中序遍历二分搜索树

    /**
         * 中序遍历以node为根的二分搜索树,递归算法
         */
        public void inOrder(){
            inOrder(root);
        }
        private void inOrder(Node node){
            if(node==null){
                return;
            }
            inOrder(node.left);
            System.out.println(node.e);
            inOrder(node.right);
        }
    

    Tips:以中序遍历打印二分搜索树的时候打印的是 ,排序后的结果

    后序遍历不再赘述

    二分搜索树的层序遍历

    利用队列进行控制

      /**
         * 二分搜索树的层序遍历
         */
        public void levelOrder(){
            Queue<Node> q=new LinkedList<>();
            q.add(root);
            while(!q.isEmpty()){
                Node cur=q.remove();
                System.out.println(cur.e);
    
                if(cur.left!=null)
                    q.add(cur.left);
                if(cur.right!=null)
                    q.add(cur.right);
            }
    
        }
    

    寻找二分搜索树中的最小元素

     /**
         * 寻找二分搜索树的最小元素
         * @return
         */
        public E minimum(){
            if(size==0)
                throw new IllegalArgumentException("BST is empty!");
            return minimum(root).e;
    
        }
        public Node minimum(Node node){
            if(node.left==null)
                return node;
            return minimum(node.left);
        }
    

    寻找二分搜索数中的最大元素

      /**
         * 寻找二分搜索树的最大元素
         * @return
         */
        public E maximum(){
            if(size==0)
                throw new IllegalArgumentException("BST is empty!");
            return maximum(root).e;
        }
        public Node maximum(Node node){
            if(node.right==null)
                return node;
            return maximum(node.right);
        }
    

    删除二分搜索树中的最小值

    /**
     * 从二分搜索树中删除最小值所在节点,返回最小值
     * @return
     */
    public E removeMin(){
        E ret=minimum();
    
        root = removeMin(root);
        return ret;
    }
    
    /**
     * 删除掉以node为根的二分搜索树中的最小节点
     * 返回删除节点后新的二分搜索树的根
     * @param node
     * @return
     */
    private Node removeMin(Node node){
        if(node.left==null){
            Node rightNode=node.right;
            node.right=null;
            size--;
            return rightNode;
        }
        node.left=removeMin(node.left);
        return node;
    }
    

    删除二分搜索树中的最大值

      /**
         * 从二分搜索树中删除最大值所在节点,返回最大值
         * @return
         */
        public E removeMax(){
            E ret=maximum();
            root=removeMax(root);
            return ret;
        }
    
        /**
         * 删除掉以node为根的二分搜索树中的最大节点
         * 返回删除节点后新的二分搜索树的根
         * @param node
         * @return
         */
        private Node removeMax(Node node ){
            if(node.right==null){
                Node leftNode=node.left;
                node.left=null;
                size--;
                return leftNode;
            }
            node.right =removeMax(node.right);
            return node;
        }
    
    

    测试minimum()

    import java.util.ArrayList;
    import java.util.Random;
    
    public class Main {
    
    
    
        public static void main(String[] args) {
            BST<Integer> bst = new BST<>();
            Random random = new Random();
            int n=1000;
            for (int i = 0; i < n; i++) {
                bst.add(random.nextInt(10000));
            }
    
            ArrayList<Integer> nums=new ArrayList<>();
            while (!bst.isEmpty()){
                nums.add(bst.removeMin());
            }
            System.out.println(nums);
            for (int i = 1; i < nums.size(); i++) {
                if(nums.get(i-1)>nums.get(i))
                    throw new IllegalArgumentException("Error");
            }
            System.out.println("removeMin test completed.");
    
        
        }
    }
    
    

    输出结果:都是从小到大有序的

    [3, 13, 21, 50, 52, 53, 54, 57, 74, 107, 112, 132, 137, 191, 193, 201, 225, 230, 240, 243, 257, 271, 288, 294, 298, 302, 305, 320, 339, 350, 358, 359, 385, 389, 391, 408, 410, 412, 420, 422, 459, 475, 482, 484, 495, 497, 515, 541, 542, 544, 564, 575, 579, 581, 585, 587, 614, 619, 645, 658, 674, 675, 679, 686, 688, 690, 721, 728, 744, 757, 767, 773, 778, 791, 797, 806, 821, 826, 831, 885, 905, 923, 926, 930, 932, 950, 979, 985, 997, 1009, 1015, 1026, 1050, 1056, 1068, 1088, 1096, 1112, 1132, 1133, 1137, 1151, 1184, 1198, 1205, 1208, 1212, 1213, 1230, 1248, 1265, 1267, 1276, 1279, 1291, 1310, 1341, 1351, 1368, 1379, 1383, 1388, 1422, 1430, 1440, 1442, 1446, 1459, 1470, 1502, 1521, 1528, 1535, 1551, 1561, 1571, 1575, 1589, 1595, 1602, 1614, 1620, 1624, 1633, 1636, 1641, 1678, 1679, 1687, 1695, 1708, 1710, 1712, 1714, 1716, 1735, 1738, 1739, 1756, 1765, 1770, 1786, 1803, 1823, 1827, 1829, 1832, 1844, 1846, 1847, 1849, 1858, 1870, 1915, 1937, 1944, 1975, 1980, 1991, 1992, 2018, 2027, 2032, 2037, 2046, 2061, 2064, 2089, 2099, 2124, 2126, 2132, 2133, 2157, 2167, 2174, 2185, 2193, 2226, 2238, 2246, 2253, 2254, 2255, 2268, 2277, 2295, 2297, 2304, 2314, 2325, 2328, 2336, 2337, 2342, 2353, 2375, 2381, 2390, 2396, 2408, 2409, 2419, 2424, 2439, 2460, 2471, 2488, 2489, 2492, 2498, 2504, 2509, 2524, 2531, 2532, 2536, 2545, 2548, 2559, 2568, 2571, 2572, 2576, 2582, 2589, 2590, 2606, 2610, 2613, 2633, 2647, 2657, 2663, 2699, 2704, 2705, 2706, 2732, 2733, 2734, 2751, 2754, 2758, 2771, 2774, 2787, 2789, 2792, 2798, 2801, 2802, 2816, 2818, 2824, 2828, 2836, 2846, 2868, 2871, 2887, 2890, 2893, 2895, 2902, 2905, 2939, 2952, 2958, 2977, 2985, 2987, 2993, 3030, 3036, 3056, 3082, 3087, 3097, 3127, 3130, 3139, 3158, 3163, 3176, 3191, 3206, 3223, 3225, 3228, 3230, 3236, 3244, 3267, 3271, 3279, 3284, 3296, 3297, 3298, 3303, 3319, 3321, 3324, 3354, 3375, 3378, 3387, 3397, 3403, 3410, 3428, 3433, 3435, 3437, 3442, 3448, 3453, 3460, 3463, 3482, 3490, 3498, 3512, 3522, 3532, 3535, 3536, 3543, 3551, 3552, 3555, 3557, 3559, 3566, 3575, 3593, 3608, 3638, 3646, 3647, 3659, 3660, 3663, 3672, 3691, 3698, 3703, 3705, 3708, 3709, 3721, 3732, 3738, 3749, 3754, 3769, 3777, 3785, 3792, 3796, 3809, 3812, 3821, 3822, 3838, 3847, 3854, 3872, 3895, 3908, 3911, 3915, 3916, 3921, 3931, 3941, 3969, 3972, 3977, 3980, 3989, 4005, 4008, 4035, 4036, 4054, 4057, 4070, 4072, 4078, 4079, 4083, 4090, 4099, 4123, 4128, 4134, 4140, 4143, 4149, 4159, 4162, 4198, 4199, 4204, 4209, 4215, 4228, 4241, 4246, 4255, 4270, 4286, 4292, 4293, 4294, 4306, 4314, 4321, 4331, 4333, 4334, 4340, 4342, 4347, 4359, 4370, 4385, 4397, 4401, 4402, 4404, 4420, 4422, 4434, 4454, 4467, 4473, 4483, 4486, 4492, 4502, 4504, 4508, 4509, 4511, 4514, 4516, 4525, 4529, 4543, 4554, 4562, 4563, 4581, 4599, 4605, 4620, 4631, 4650, 4665, 4672, 4675, 4688, 4704, 4723, 4732, 4737, 4738, 4740, 4758, 4763, 4779, 4786, 4803, 4824, 4829, 4838, 4847, 4851, 4872, 4887, 4888, 4894, 4905, 4907, 4919, 4924, 4936, 4941, 4958, 4974, 5005, 5010, 5012, 5032, 5044, 5049, 5082, 5091, 5110, 5114, 5135, 5144, 5146, 5147, 5163, 5167, 5174, 5191, 5221, 5230, 5233, 5243, 5255, 5274, 5275, 5276, 5320, 5347, 5353, 5389, 5396, 5400, 5420, 5427, 5445, 5446, 5456, 5464, 5481, 5495, 5550, 5551, 5563, 5598, 5599, 5602, 5604, 5606, 5629, 5680, 5683, 5686, 5719, 5721, 5729, 5731, 5735, 5738, 5740, 5747, 5749, 5754, 5778, 5780, 5794, 5821, 5833, 5843, 5861, 5864, 5892, 5893, 5939, 5944, 5945, 5946, 5964, 5983, 5993, 6005, 6015, 6016, 6018, 6029, 6033, 6041, 6054, 6077, 6078, 6091, 6111, 6130, 6131, 6164, 6177, 6187, 6196, 6198, 6199, 6205, 6207, 6208, 6216, 6219, 6232, 6238, 6248, 6271, 6294, 6301, 6306, 6310, 6329, 6344, 6346, 6349, 6367, 6384, 6387, 6430, 6436, 6441, 6448, 6450, 6451, 6455, 6460, 6461, 6480, 6483, 6496, 6507, 6517, 6529, 6538, 6558, 6567, 6571, 6574, 6578, 6598, 6610, 6614, 6616, 6636, 6693, 6695, 6707, 6734, 6738, 6758, 6779, 6782, 6785, 6828, 6837, 6838, 6841, 6869, 6870, 6873, 6919, 6929, 6931, 6940, 6968, 6976, 6980, 6986, 6999, 7020, 7054, 7055, 7092, 7105, 7107, 7108, 7111, 7125, 7129, 7130, 7132, 7140, 7150, 7151, 7152, 7154, 7157, 7160, 7174, 7177, 7183, 7211, 7212, 7252, 7263, 7303, 7310, 7317, 7320, 7355, 7357, 7365, 7369, 7382, 7383, 7386, 7418, 7433, 7434, 7459, 7482, 7483, 7546, 7553, 7554, 7579, 7609, 7614, 7621, 7623, 7630, 7643, 7684, 7692, 7711, 7720, 7721, 7722, 7734, 7736, 7751, 7764, 7770, 7772, 7777, 7779, 7808, 7819, 7824, 7828, 7836, 7850, 7866, 7908, 7920, 7934, 7937, 7971, 7990, 8037, 8046, 8049, 8082, 8110, 8119, 8129, 8133, 8135, 8163, 8165, 8167, 8170, 8174, 8186, 8199, 8211, 8234, 8237, 8240, 8253, 8255, 8258, 8265, 8274, 8281, 8295, 8300, 8333, 8369, 8370, 8428, 8431, 8442, 8451, 8456, 8472, 8480, 8491, 8521, 8525, 8538, 8540, 8542, 8551, 8557, 8561, 8567, 8568, 8571, 8580, 8596, 8602, 8609, 8610, 8612, 8630, 8642, 8653, 8663, 8668, 8704, 8710, 8747, 8754, 8761, 8773, 8774, 8779, 8792, 8808, 8820, 8825, 8827, 8840, 8843, 8859, 8897, 8937, 8942, 8946, 8956, 8957, 8969, 8971, 8973, 8980, 8993, 8998, 9000, 9020, 9041, 9043, 9052, 9064, 9080, 9110, 9113, 9118, 9172, 9184, 9204, 9207, 9208, 9212, 9217, 9232, 9248, 9252, 9271, 9274, 9282, 9293, 9302, 9308, 9316, 9331, 9341, 9346, 9357, 9362, 9370, 9371, 9372, 9392, 9416, 9429, 9438, 9441, 9447, 9453, 9454, 9465, 9468, 9484, 9485, 9511, 9517, 9531, 9540, 9543, 9550, 9566, 9567, 9576, 9604, 9607, 9608, 9616, 9637, 9639, 9640, 9653, 9668, 9673, 9712, 9713, 9718, 9720, 9726, 9738, 9748, 9751, 9756, 9765, 9767, 9777, 9801, 9802, 9821, 9826, 9870, 9872, 9899, 9904, 9921, 9940, 9945, 9949, 9956, 9963, 9967, 9977, 9978, 9984, 9997]
    removeMin test completed.
    

    二分搜索树中删除任意元素e

    /**
         *
         * 从二分搜索树中删除元素为e的节点
         * @param e
         */
        public void remove(E e ){
           root= remove(root,e );
        }
    
        /**
         * 删除从以node为根的二分搜索树中值为e的节点,递归算法
         * 返回删除节点后新的二分搜索树的根
         * @param node
         * @param e
         * @return
         */
        private Node remove(Node node,E e){
            if(node==null)
                return null;
            if(e.compareTo(node.e)<0){
                node.left=remove(node.left,e);
                return node;
            }else if (e.compareTo(node.e)>0){
                node.right=remove(node.right,e);
                return node;
            }else{//e.compareTo(node.e) == 0
                //待删除节点左子树为空的情况
                if(node.left==null){
                    Node rightNode=node.right;
                    node.right=null;
                    size--;
                    return rightNode;
                }
    
                //待删除节点右子树为空的情况
                if(node.right==null){
                    Node leftNode=node.left;
                    node.left=null;
                    size--;
                    return leftNode;
                }
    
                //待删除节点左右子树均不为空的情况
    
                //找到比待删除节点大的最小节点,即待删除节点右子树的最小节点
                //用这个节点顶替待删除节点的位置
                Node successor=minimum(node.right);
                successor.right=removeMin(node.right);
                successor.left=node.left;
                node.left=node.right=null;
                return successor;
    
            }
    
    展开全文
  • package ...import sun.reflect.generics.tree.Tree;import java.util.HashMap;import java.util.LinkedList;import java.util.Queue;import java.util.Stack;public class BST> {class TreeNode{E...
  • importjava.util.LinkedList;importjava.util.Queue;public class BST, Value>{private classNode {privateKey key;privateValue value;privateNode left, right;publicNode(Key key, Value value)...
  • 标签:minimumsemminioidposturnelsemin()rgs递归理解起来还是有点难,弄清楚搞了不短的时间package ...import java.util.LinkedList;import java.util.Queue;public class BST> {priva...
  • 二分搜索Mappublic class BSTMap,V> implements Map {private class Node{public K key;public V value;public Node left,right;public Node(K key,V value){this.key = key;this.value = value;left = null;...
  • 2.java实现二分搜索 1.二分搜索特点 二分搜索是一个动态数据结构; 二分搜索也是一个二叉树; 二分搜索的每个结点的值都大于其左子树上的所有结点的值,小于其右子上的所有结点的值; 存储的元素必须有...
  • java实现二分检索

    2016-02-19 20:48:29
    二分检索的左子树比根小,右...这里用二分检索树实现了一个符号表,包括常用的api。package symbolForm;import simpleStructure.Queue;public class BST, V> implements SymbolForm, V> { private Node root; privat
  • java实现二分搜索BST

    2019-08-28 17:56:04
    package Tree; import java.awt.image.RescaleOp; import javax.sound.midi.Soundbank; /** * @Title: BST.java ...* @Description: TODO二分搜索,递归的写法一般具有更高的开销 * @author YEXIN * @date...
  • 递归理解起来还是有点难,弄清楚搞了不短的时间package ...import java.util.LinkedList;import java.util.Queue;public class BST> {private class Node{public E e;public Node left,right;public Node(E e...
  • 14.Java实现二分搜索

    2019-03-26 08:34:19
    package com.cl.set; import java.util.LinkedList; import java.util.Queue; /** * 二分搜索 * @param <E> */ public class BST<E extends Comparable<E>>{ private class Node{ ...
  • /*** 二分查找BST(也叫二叉查找、二叉排序)的提出是为了提供查找效率,* 之所以称为二分查找,因为该二叉树对应着二分查找算法,查找平均的时间复杂度为o(logn),所以该数据结构的提出是为了提高查找效率。...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 597
精华内容 238
关键字:

java实现二分树

java 订阅