天天看點
傳回

Java實作二分搜尋樹二分搜尋樹的定義

Java實作二分搜尋樹

  • 二分搜尋樹的定義
    • 二分搜尋樹的代碼結構
    • 向二分搜尋樹添加元素（遞歸實作）
    • 對添加元素代碼的簡化（如果遞歸功底深厚）
    • 檢視二分搜尋樹中是否還有元素e（遞歸）
    • 二分搜尋樹的前序周遊（遞歸）
    • 基于前序周遊重寫toString
    • 二分搜尋樹的中序周遊
    • 二分搜尋樹的後序周遊
    • 二分搜尋樹的前序周遊（非遞歸）
    • 二分搜尋樹的層序周遊（非遞歸）（廣度優先周遊）
    • 查找二分搜尋樹中的最大最小值
    • 删除二分搜尋樹的最小值與最大值
    • 删除二分搜尋樹的任意元素
    • 删除任意一個元素
    • 通篇代碼整合（終結版）

二分搜尋樹的定義

#二分搜尋樹是二叉樹

#二分搜尋樹的每個節點的值：

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沒有孩子節點，并且此時棧為空，前序周遊結束。

Java實作二分搜尋樹二分搜尋樹的定義

代碼實作：

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，記錄。沒有孩子節點，什麼都不做。出隊隊首元素，由于此時隊列為空，周遊結束。

Java實作二分搜尋樹二分搜尋樹的定義

代碼實作：

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：

Java實作二分搜尋樹二分搜尋樹的定義

情況2：

Java實作二分搜尋樹二分搜尋樹的定義

#查找最小值（遞歸）

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：最小值為葉子節點（如下圖）

操作：直接删除就好了

Java實作二分搜尋樹二分搜尋樹的定義

情況2：最小值為非葉子節點（如下圖）

操作：将删除節點的右子樹變成删除節點的父親節點的左子樹

Java實作二分搜尋樹二分搜尋樹的定義

情況2删除後：（如下圖）

Java實作二分搜尋樹二分搜尋樹的定義

#删除最小值（遞歸）

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：最大值為葉子節點（如下圖）

操作：直接删除就好了

Java實作二分搜尋樹二分搜尋樹的定義

情況二：最大值為非葉子節點（如下圖）

操作：将删除節點的左子樹變成删除節點的父親節點的右子樹

Java實作二分搜尋樹二分搜尋樹的定義

情況2删除後（如下圖）：

Java實作二分搜尋樹二分搜尋樹的定義

#删除最大值（遞歸）

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;
}

删除二分搜尋樹的任意元素

Java實作二分搜尋樹二分搜尋樹的定義
Java實作二分搜尋樹二分搜尋樹的定義
Java實作二分搜尋樹二分搜尋樹的定義
Java實作二分搜尋樹二分搜尋樹的定義

删除任意一個元素 

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 二分搜尋樹 二叉樹
上一篇: 資料結構學習——二分搜尋樹(1)
下一篇: 二分搜尋樹c++資料結構插入查找，和插入類似周遊

繼續閱讀