基本介紹

二叉排序樹：BST(Binary Sort(Search) Tree)，對於二叉排序樹的任何一個非葉子節點，要求左節點的值，比當前節點的值小，右節點的值比當前節點的值大。

**特別說明：**如果有相同的值，可以將該節點放在左子節點或者右子節點

比如針對資料{7,3,10,12,5,1,9}，對應的二叉排序樹為：

刪除葉子節點(比如：2，5，9，12)需要先找到要刪除的節點 targetNode找到 targetNode 的父節點 parentNode(考慮是否存在父節點)確定 targetNode 是 parentNode 的左子節點還是右子節點根據前面的來對應刪除，左子節點=>parent.left = null，右子節點=>parent.right = null;刪除只有一顆子樹的節點（比如：1）需要先找到要刪除的節點 targetNode找到 targetNode 的父節點 parentNode(考慮是否存在父節點)確定 targetNode 的子節點是左子節點還是右子節點確定 targetNode 是 parentNode 的左子節點還是右子節點如果 targetNode 是parentNode 的左子節點 :targetNode 的子節點是左子節點 ,那麼 parentNode.left = targetNode.lefttargetNode 的子節點是右子節點，那麼， parentNode.left = targetNode.right;如果 targetNode 是 parentNode 的右子節點：targetNode 的子節點是左子節點 ,那麼 parentNode.right = targetNode.lefttargetNode 的子節點是右子節點，那麼， parentNode.right = targetNode.right刪除有兩顆子樹的節點（比如：7，3，10）需要先找到要刪除的節點 targetNode找到 targetNode 的父節點 parentNode(考慮是否存在父節點)從 targetNode 的右子樹找到最小的節點，用一個臨時變數，將右子樹最小節點的值儲存到temp ,刪除該右子樹最小節點，然後，targetNode.value = temp;如果從左子樹找的話，只要替換左子樹最大的值就行。程式碼案例

package com.xie.bst;public class BinarySortTreeDemo {    public static void main(String[] args) {        int[] arr = {7, 3, 10, 12, 5, 1, 9, 2};        BinarySortTree binarySortTree = new BinarySortTree();        for (int i : arr) {            binarySortTree.add(new Node(i));        }        System.out.println("中序遍歷二叉排序樹~");        binarySortTree.infixOrder();        System.out.println("測試刪除葉子節點");        binarySortTree.delNode(10);        System.out.println("刪除節點後");        binarySortTree.infixOrder();    }}class BinarySortTree {    private Node root;    //查詢要刪除的節點的父節點    public Node searchParent(Node node) {        if (root != null) {            return root.searchParent(node);        } else {            return null;        }    }    //查詢要刪除的節點    public Node search(int value) {        if (root == null) {            return null;        } else {            return root.search(value);        }    }    /**     * 找到以node 根的二叉排序樹的最小值，並刪除以node 為根節點的二叉排序樹的最小節點     *     * @param node 傳入節點（當做二叉排序樹的根節點)     * @return 返回以node為根節點的二叉排序樹的最小節點值     */    public int delRightTreeMin(Node node) {        Node target = node;        //迴圈查詢左節點        while (target.left != null) {            target = target.left;        }        //刪除最小節點        delNode(target.value);        return target.value;    }    /**     * 找到以node 根的二叉排序樹的最大值，並刪除以node 為根節點的二叉排序樹的最大節點     *     * @param node 傳入節點（當做二叉排序樹的根節點)     * @return 返回以node為根節點的二叉排序樹的最大節點值     */    public int delLeftTreeMax(Node node) {        Node target = node;        while (target.right != null) {            target = target.right;        }        //刪除最大節點        delNode(target.value);        return target.value;    }    //刪除節點    public void delNode(int value) {        if (root == null) {            return;        } else {            Node targetNode = search(value);            if (targetNode == null) {                return;            }            if (targetNode == root) {                root = null;                return;            }            Node parentNode = searchParent(targetNode);            if (targetNode.left == null && targetNode.right == null) {                //如果要刪除的節點是葉子節點                if (parentNode.left != null && parentNode.left.value == targetNode.value) {                    parentNode.left = null;                }                if (parentNode.right != null && parentNode.right.value == targetNode.value) {                    parentNode.right = null;                }            } else if (targetNode.left != null && targetNode.right != null) {                //如果要刪除的節點是有兩個子樹的節點                int minValue = delRightTreeMin(targetNode.right);                targetNode.value = minValue;                //上下程式碼刪除效果一樣                //int maxValue = delLeftTreeMax(targetNode.left);                //targetNode.value = maxValue;            } else {                //要刪除的節點是隻有左子節點                if (targetNode.left != null) {                    if (parentNode != null) {                        if (parentNode.left == targetNode) {                            parentNode.left = targetNode.left;                        } else {                            parentNode.right = targetNode.left;                        }                    } else {                        //如果父節點是空，讓root換位                        root = targetNode.left;                    }                } else {//要刪除的節點是隻有右子節點                    if (parentNode != null) {                        if (parentNode.left == targetNode) {                            parentNode.left = targetNode.right;                        } else {                            parentNode.right = targetNode.right;                        }                    } else {                        //如果父節點是空，讓root換位                        root = targetNode.right;                    }                }            }        }    }    //新增節點    public void add(Node node) {        if (root == null) {            root = node;        } else {            root.add(node);        }    }    //中序遍歷    public void infixOrder() {        if (root != null) {            root.infixOrder();        } else {            System.out.println("二叉排序為空，不能遍歷");        }    }}class Node {    int value;    Node left;    Node right;    public Node(int value) {        this.value = value;    }    /**     * 查詢要刪除節點的父節點     *     * @param node 要刪除的節點     * @return 要刪除節點的父節點     */    public Node searchParent(Node node) {        //如果當前節點就是要刪除節點的父節點就返回        if ((this.left != null && this.left.value == node.value) ||                (this.right != null && this.right.value == node.value)) {            return this;        } else {            if (this.left != null && node.value < this.value) {                //如果查詢的節點的值小於當前節點的值，向左子樹遞迴查詢                return this.left.searchParent(node);            } else if (this.right != null && value >= this.value) {                //如果查詢的節點的值小於當前節點的值，向左子樹遞迴查詢                return this.right.searchParent(node);            } else {                return null;            }        }    }    /**     * 查詢要刪除的節點     *     * @param value 要刪除的節點的值     * @return 刪除的節點     */    public Node search(int value) {        if (value == this.value) {            return this;        } else if (value < this.value) {            if (this.left != null) {                return this.left.search(value);            } else {                return null;            }        } else {            if (this.right != null) {                return this.right.search(value);            } else {                return null;            }        }    }    //遞迴的形式新增節點，滿足二叉排序樹的要求    public void add(Node node) {        if (node == null) {            return;        }        if (node.value < this.value) {            if (this.left == null) {                this.left = node;            } else {                //遞歸向左子樹新增                this.left.add(node);            }        } else {            if (this.right == null) {                this.right = node;            } else {                //遞歸向右子節點新增                this.right.add(node);            }        }    }    //中序遍歷    public void infixOrder() {        if (this.left != null) {            this.left.infixOrder();        }        System.out.println(this);        if (this.right != null) {            this.right.infixOrder();        }    }    @Override    public String toString() {        return "Node{" +                "value=" + value +                '}';    }}

歡迎關注、點贊、收藏，後續將推送更多優質文章！