Java實現(xiàn)二分查找樹及其相關(guān)操作

更新時間：2021年07月26日 14:34:25 作者：胡不慌

二分查找樹是一種有組織的二叉樹。我們可以通過鏈接節(jié)點(diǎn)表示這樣一棵樹，二分查找樹（Binary Search Tree）的基本操作有搜索、求最大值、求最小值、求前驅(qū)、求后繼、插入及刪除，對java二分查找樹相關(guān)知識感興趣的朋友一起看看吧

二分查找樹（Binary Search Tree）的基本操作有搜索、求最大值、求最小值、求前驅(qū)、求后繼、插入及刪除。

對二分查找樹的進(jìn)行基本操作所花費(fèi)的時間與樹的高度成比例。例如有n個節(jié)點(diǎn)的完全二叉樹，對它進(jìn)行的基本操作的時間復(fù)雜度為O(logn)。然而，如果樹是一個有n個節(jié)點(diǎn)的線性的鏈，則在這種情況下的時間復(fù)雜度為O(n)。

1、什么是二分查找樹

二分查找樹是一種有組織的二叉樹。我們可以通過鏈接節(jié)點(diǎn)表示這樣一棵樹。每個節(jié)點(diǎn)包含鍵（key），數(shù)據(jù)（data），左子節(jié)點(diǎn)（left），右子節(jié)點(diǎn)（right），父節(jié)點(diǎn)（parent）這五種屬性。

如果一個節(jié)點(diǎn)沒有父節(jié)點(diǎn)或某個子結(jié)點(diǎn)，則其對應(yīng)的屬性的值為null。

創(chuàng)建一個Node.java文件，用如下代碼表示節(jié)點(diǎn)：

public class Node {
    public int key;
    public int data;
    public Node left;
    public Node right;
    public Node parent;
    
    public Node(){}
    
    public Node(int key) {
        this.key = key;
    }
}

創(chuàng)建一個BinarySearchTree.java文件，用如下代碼表示二分查找樹：

public class BinarySearchTree {
    public Node root;
}

接下來，會逐步補(bǔ)充代碼。

對于存儲在二分查找樹中的鍵，必須滿足下面這個條件（二分查找樹特點(diǎn)）：

對于二叉樹中的任一節(jié)點(diǎn)n，如果left是n左子樹中的任何一個節(jié)點(diǎn)，有l(wèi)eft.key <= n.key；如果right是n右子樹中的任一節(jié)點(diǎn)，則有n.key<=right.key。

如果我們中序遍歷二分查找樹，能升序打印出所有的鍵（key）。

可在BinarySearchTree.java文件中加上如下代碼實現(xiàn)中序遍歷：

private void innerWalk(Node node) {
        if(node != null) {
            innerWalk(node.left);
            System.out.print(node.key + " ");
            innerWalk(node.right);
        }
    }

    public void innerWalk() {
        this.innerWalk(this.root);
        System.out.println();
    }

2、查詢二分查找樹

2.1、搜索

在二分查找樹中搜索鍵為key的結(jié)點(diǎn)，如果找到，則返回該結(jié)點(diǎn)，否則，返回null。可利用二分查找樹的特性來查找。

可在BinarySearchTree.java文件中加上如下代碼實現(xiàn)搜索：

public Node search(int key) {
        Node pointer = this.root;
        while (pointer != null && pointer.key != key) {
            pointer = key < pointer.key ? pointer.left : pointer.right;
        }
        return pointer;
    }

2.2、最小值與最大值

求鍵最小的節(jié)點(diǎn)，可根據(jù)二叉樹的特點(diǎn)，從根結(jié)點(diǎn)開始，遍歷跟蹤其左子節(jié)點(diǎn)，直到最后一個。

可在Node.java文件中加上如下代碼實現(xiàn)：

 public Node minimum() {
        Node pointer = this;
        while(pointer.left != null){
            pointer = pointer.left;
        }
        return pointer;
    }

在BinarySearchTree.java文件中加上如下代碼：

public Node minimum() {
        return this.root.minimum();
    }

求鍵最大的節(jié)點(diǎn)，可根據(jù)二叉樹的特點(diǎn)，從根結(jié)點(diǎn)開始，遍歷跟蹤其右子節(jié)點(diǎn)，直到最后一個。

可在Node.java文件中加上如下代碼實現(xiàn)：

 public Node maximum() {
        Node pointer = this;
        while(pointer.right != null) {
            pointer = pointer.right;
        }
        return pointer;
    }

在BinarySearchTree.java文件中加上如下代碼：

public Node minimum() {
        return this.root.maximum();
    }

2.3、前驅(qū)與后繼

給定一個二分查找樹中的節(jié)點(diǎn)，有時我們需要發(fā)現(xiàn)它在樹中所有結(jié)點(diǎn)按鍵升序排序的情況下的直接后繼（后面第一個）。

如果樹中所有的鍵是不同的，結(jié)點(diǎn)n的直接后繼是大于n.key的最小結(jié)點(diǎn)。

如果該結(jié)點(diǎn)有右節(jié)點(diǎn)，則其直接后繼是其右子樹鍵最小的那個結(jié)點(diǎn)。如果該結(jié)點(diǎn)則判斷該結(jié)點(diǎn)是其父節(jié)點(diǎn)的左子節(jié)點(diǎn)還是其右子節(jié)點(diǎn)。

如果是左子節(jié)點(diǎn)，則返回其父節(jié)點(diǎn)。如果是右子節(jié)點(diǎn)，判斷其父節(jié)點(diǎn)的其父節(jié)點(diǎn)的父節(jié)點(diǎn)的左子節(jié)點(diǎn)還是右子節(jié)點(diǎn)，以此類推。

如果找不到，則返回null。

可在Node.java文件中加上如下實現(xiàn)代碼：

public Node successor() {
        Node pointer = this;
        if (pointer.right != null)
            return pointer.right.minimum();
        Node parentPointer = pointer.parent;
        while (parentPointer != null && parentPointer.right == pointer) {
            pointer = parentPointer;
            parentPointer = parentPointer.parent;
        }
        return pointer;
    }

一個節(jié)點(diǎn)的直接前繼是指樹中所有結(jié)點(diǎn)按鍵升序排序的情況下，該節(jié)點(diǎn)的前面第一個。求直接前繼的與求直接后繼是對稱的。

可在Node.java文件中加上如下實現(xiàn)代碼：

 public Node predecessor() {
        Node pointer = this;
        if (pointer.left != null)
            return pointer.left.maximum();
        Node parentPointer = pointer.parent;
        while (parentPointer != null && parentPointer.left == pointer) {
            pointer = parentPointer;
            parentPointer = parentPointer.parent;
        }
        return pointer;
    }

3、插入與刪除

插入與刪除會導(dǎo)致二分查找樹發(fā)生改變，但必須保持其特點(diǎn)。

3.1、插入

在樹中找到一個鍵（key）最接近要插入結(jié)點(diǎn)鍵（key）的結(jié)點(diǎn)，且有可以插入的位置，然后插入合適的位置。

可在BinarySearchTree.java文件中加上如下實現(xiàn)代碼：

 public void insert(Node node) {
        Node pointer = this.root;
        Node parentPointer = null;
        while (pointer != null) {
            parentPointer = pointer;
            pointer = node.key < pointer.key ? pointer.left : pointer.right;
        }
        node.parent = parentPointer;
        if (parentPointer == null)
            this.root = node;
        else if (node.key < parentPointer.key) {
            parentPointer.left = node;
        } else {
            parentPointer.right = node;
        }
    }

3.2、刪除

刪除節(jié)點(diǎn)后，我門要保持二分查找樹的特點(diǎn)。

如果要刪除節(jié)點(diǎn)沒有任何子節(jié)點(diǎn)，直接可以刪除它，不用做任何處理。

如果要刪除節(jié)點(diǎn)只有一個左子樹，可以用左子樹的根節(jié)點(diǎn)代替要刪除節(jié)點(diǎn)，也可以用左子樹中鍵（key）最大的節(jié)點(diǎn)來代替要刪除節(jié)點(diǎn)。

如果要刪除結(jié)點(diǎn)只有一個右子樹，可以用右子樹的根節(jié)點(diǎn)代替要刪除節(jié)點(diǎn)，也可以用右子樹中鍵（key）最小的結(jié)點(diǎn)來代替要刪除結(jié)點(diǎn)。

如果要刪除結(jié)點(diǎn)既有左子樹，又有右子樹，可以用左子樹中鍵（key）最大的結(jié)點(diǎn)代替要刪除結(jié)點(diǎn)，也可以用右子樹中鍵最小的結(jié)點(diǎn)代替要刪除結(jié)點(diǎn)。

假設(shè)要從二分查找樹tree中刪除節(jié)點(diǎn)node，一種刪除方法的具體步驟如下：

如果node沒有左子節(jié)點(diǎn)，然后我們可以用node的右子節(jié)node.right點(diǎn)代替node，node.right可能是或可能不是null。
如果node只有左子節(jié)點(diǎn)node.left，則我們用node.left代替node。
如果node有左子節(jié)點(diǎn)node.left和右子節(jié)點(diǎn)node.right。我么要發(fā)現(xiàn)node的直接后繼s（node右子樹中鍵最小的結(jié)點(diǎn)，它沒有左子節(jié)點(diǎn)），s在node右子樹中，然后用s代替node。這里要考慮下面兩種情況：

如果s是node的右子節(jié)點(diǎn)，可以用s代替node。
否則，用s的右子節(jié)點(diǎn)代替s，然后再用s代替node。

由于我們需要在二分查找樹中替換子樹的方法，可以先寫一個替換子樹的方法。

可在BinarySearchTree.java文件中加上如下實現(xiàn)代碼：

/**
     * 用子樹node2代替代替子樹node1
     * 
     * @param node1
     * @param node2
     */
    private void transplant(Node node1, Node node2) {
        if (node1.parent == null) {
            this.root = node2;
        } else if (node1.parent.left == node1) {
            node1.parent.left = node2;
        } else {
            node1.parent.right = node2;
        }

        if (node2 != null)
            node2.parent = node1.parent;
        node1.parent = null;
    }

接下來解釋刪除節(jié)點(diǎn)操作的代碼實現(xiàn)。

可在BinarySearchTree.java文件中加上如下實現(xiàn)代碼：

 public void delete(Node node) {
        if (node.left == null) {
            this.transplant(node, node.right);
        } else if (node.right == null) {
            this.transplant(node, node.left);
        } else {
            Node successor = node.successor();
            if (successor.parent != node) {
                this.transplant(successor, successor.right);
                successor.right = node.right;
                successor.right.parent = successor;
            }
            this.transplant(node, successor);
            successor.left = node.left;
            successor.left.parent = successor;
        }
    }

4、完整代碼

Node.java文件

public class Node {
    public int key;
    public int data;
    public Node left;
    public Node right;
    public Node parent;

    public Node() {
    }

    public Node(int key) {
        this.key = key;
    }

    public Node minimum() {
        Node pointer = this;
        while (pointer.left != null)
            pointer = pointer.left;
        return pointer;
    }

    public Node maximum() {
        Node pointer = this;
        while (pointer.right != null)
            pointer = pointer.right;
        return pointer;
    }

    public Node successor() {
        Node pointer = this;
        if (pointer.right != null)
            return pointer.right.minimum();
        Node parentPointer = pointer.parent;
        while (parentPointer != null && parentPointer.right == pointer) {
            pointer = parentPointer;
            parentPointer = parentPointer.parent;
        }
        return pointer;
    }

    public Node predecessor() {
        Node pointer = this;
        if (pointer.left != null)
            return pointer.left.maximum();
        Node parentPointer = pointer.parent;
        while (parentPointer != null && parentPointer.left == pointer) {
            pointer = parentPointer;
            parentPointer = parentPointer.parent;
        }
        return pointer;
    }
}

BinarySearchTree.java文件

public class BinarySearchTree {
    public Node root;

    private void innerWalk(Node node) {
        if (node != null) {
            innerWalk(node.left);
            System.out.print(node.key + " ");
            innerWalk(node.right);
        }
    }

    public void innerWalk() {
        this.innerWalk(this.root);
        System.out.println();
    }

    public Node search(int key) {
        Node pointer = this.root;
        while (pointer != null && pointer.key != key) {
            pointer = key < pointer.key ? pointer.left : pointer.right;
        }
        return pointer;
    }

    public Node minimum() {
        return this.root.minimum();
    }

    public Node maximum() {
        return this.root.maximum();
    }

    public void insert(Node node) {
        Node pointer = this.root;
        Node parentPointer = null;
        while (pointer != null) {
            parentPointer = pointer;
            pointer = node.key < pointer.key ? pointer.left : pointer.right;
        }
        node.parent = parentPointer;
        if (parentPointer == null)
            this.root = node;
        else if (node.key < parentPointer.key) {
            parentPointer.left = node;
        } else {
            parentPointer.right = node;
        }
    }

    /**
     * 用子樹node2代替代替子樹node1
     * 
     * @param node1
     * @param node2
     */
    private void transplant(Node node1, Node node2) {
        if (node1.parent == null) {
            this.root = node2;
        } else if (node1.parent.left == node1) {
            node1.parent.left = node2;
        } else {
            node1.parent.right = node2;
        }

        if (node2 != null)
            node2.parent = node1.parent;
        node1.parent = null;
    }

    public void delete(Node node) {
        if (node.left == null) {
            this.transplant(node, node.right);
        } else if (node.right == null) {
            this.transplant(node, node.left);
        } else {
            Node successor = node.successor();
            if (successor.parent != node) {
                this.transplant(successor, successor.right);
                successor.right = node.right;
                successor.right.parent = successor;
            }
            this.transplant(node, successor);
            successor.left = node.left;
            successor.left.parent = successor;
        }
    }
}

5、演示

演示代碼：

public class Test01 {
    public static void main(String[] args) {
        Node n1 = new Node(1);
        Node n2 = new Node(2);
        Node n3 = new Node(3);
        Node n4 = new Node(4);
        Node n5 = new Node(5);

        BinarySearchTree bst = new BinarySearchTree();
        bst.insert(n3);
        bst.insert(n4);
        bst.insert(n2);
        bst.insert(n1);
        bst.insert(n5);

        System.out.println("bst.minimum().key: " + bst.minimum().key);
        System.out.println("bst.maximum().key: " + bst.maximum().key);
        System.out.println("n3.successor().key: " + n3.successor().key);
        System.out.println("n3.predecessor().key: " + n3.predecessor().key);
        System.out.println("bst.search(4).key: " + bst.search(4).key);

        System.out.print("tree: ");
        bst.innerWalk();
        System.out.print("delete n3: ");
        bst.delete(n3);
        bst.innerWalk();
        System.out.print("delete n2: ");
        bst.delete(n2);
        bst.innerWalk();
        System.out.print("delete n1: ");
        bst.delete(n1);
        bst.innerWalk();
        System.out.print("delete n4: ");
        bst.delete(n4);
        bst.innerWalk();
        System.out.print("delete n5: ");
        bst.delete(n5);
        bst.innerWalk();
    }
}

結(jié)果：

bst.minimum().key: 1
bst.maximum().key: 5
n3.successor().key: 4
n3.predecessor().key: 2
bst.search(4).key: 4
tree: 1 2 3 4 5
delete n3: 1 2 4 5
delete n2: 1 4 5
delete n1: 4 5
delete n4: 5
delete n5:

到此這篇關(guān)于Java實現(xiàn)二分查找樹及其相關(guān)操作的文章就介紹到這了,更多相關(guān)java二分查找樹內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: