[[390181]]

基本介紹

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

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

比如針對數(shù)據(jù){7,3,10,12,5,1,9}，對應的二叉排序樹為：

二叉排序樹刪除節(jié)點

二叉排序樹的刪除情況比較復雜，如下圖，有下面三種情況需要考慮，

1.刪除葉子節(jié)點(比如：2，5，9，12)

1. 需要先找到要刪除的節(jié)點 targetNode
2. 找到 targetNode 的父節(jié)點 parentNode(考慮是否存在父節(jié)點)
3. 確定 targetNode 是 parentNode 的左子節(jié)點還是右子節(jié)點
4. 根據(jù)前面的來對應刪除，左子節(jié)點=>parent.left = null，右子節(jié)點=>parent.right = null;

2.刪除只有一顆子樹的節(jié)點(比如：1)

1. 需要先找到要刪除的節(jié)點 targetNode
2. 找到 targetNode 的父節(jié)點 parentNode(考慮是否存在父節(jié)點)
3. 確定 targetNode 的子節(jié)點是左子節(jié)點還是右子節(jié)點
4. 確定 targetNode 是 parentNode 的左子節(jié)點還是右子節(jié)點
5. 如果 targetNode 是parentNode 的左子節(jié)點 :

• targetNode 的子節(jié)點是左子節(jié)點 ,那么 parentNode.left = targetNode.lefttargetNode 的子節(jié)點是右子節(jié)點，那么， parentNode.left = targetNode.right;
• 如果 targetNode 是 parentNode 的右子節(jié)點：targetNode 的子節(jié)點是左子節(jié)點 ,那么 parentNode.right = targetNode.lefttargetNode 的子節(jié)點是右子節(jié)點，那么， parentNode.right = targetNode.right

3.刪除有兩顆子樹的節(jié)點(比如：7，3，10)

1. 需要先找到要刪除的節(jié)點 targetNode
2. 找到 targetNode 的父節(jié)點 parentNode(考慮是否存在父節(jié)點)
3. 從 targetNode 的右子樹找到最小的節(jié)點，用一個臨時變量，將右子樹最小節(jié)點的值保存到temp ,刪除該右子樹最小節(jié)點，然后，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("測試刪除葉子節(jié)點"); 
        binarySortTree.delNode(10); 
        System.out.println("刪除節(jié)點后"); 
        binarySortTree.infixOrder(); 
    } 
} 
 
class BinarySortTree { 
    private Node root; 
 
    //查找要刪除的節(jié)點的父節(jié)點 
    public Node searchParent(Node node) { 
        if (root != null) { 
            return root.searchParent(node); 
        } else { 
            return null; 
        } 
    } 
 
    //查找要刪除的節(jié)點 
    public Node search(int value) { 
        if (root == null) { 
            return null; 
        } else { 
            return root.search(value); 
        } 
    } 
 
    /** 
     * 找到以node 根的二叉排序樹的最小值，并刪除以node 為根節(jié)點的二叉排序樹的最小節(jié)點 
     * 
     * @param node 傳入節(jié)點（當做二叉排序樹的根節(jié)點) 
     * @return 返回以node為根節(jié)點的二叉排序樹的最小節(jié)點值 
     */ 
    public int delRightTreeMin(Node node) { 
        Node target = node; 
        //循環(huán)查找左節(jié)點 
        while (target.left != null) { 
            target = target.left; 
        } 
        //刪除最小節(jié)點 
        delNode(target.value); 
        return target.value; 
    } 
 
    /** 
     * 找到以node 根的二叉排序樹的最大值，并刪除以node 為根節(jié)點的二叉排序樹的最大節(jié)點 
     * 
     * @param node 傳入節(jié)點（當做二叉排序樹的根節(jié)點) 
     * @return 返回以node為根節(jié)點的二叉排序樹的最大節(jié)點值 
     */ 
    public int delLeftTreeMax(Node node) { 
        Node target = node; 
        while (target.right != null) { 
            target = target.right; 
        } 
 
        //刪除最大節(jié)點 
        delNode(target.value); 
        return target.value; 
    } 
 
    //刪除節(jié)點 
    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) { 
                //如果要刪除的節(jié)點是葉子節(jié)點 
                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) { 
                //如果要刪除的節(jié)點是有兩個子樹的節(jié)點 
                int minValue = delRightTreeMin(targetNode.right); 
                targetNode.value = minValue; 
                //上下代碼刪除效果一樣 
                //int maxValue = delLeftTreeMax(targetNode.left); 
                //targetNode.value = maxValue; 
            } else { 
                //要刪除的節(jié)點是只有左子節(jié)點 
                if (targetNode.left != null) { 
                    if (parentNode != null) { 
                        if (parentNode.left == targetNode) { 
                            parentNode.left = targetNode.left; 
                        } else { 
                            parentNode.right = targetNode.left; 
                        } 
                    } else { 
                        //如果父節(jié)點是空，讓root換位 
                        root = targetNode.left; 
                    } 
                } else {//要刪除的節(jié)點是只有右子節(jié)點 
                    if (parentNode != null) { 
                        if (parentNode.left == targetNode) { 
                            parentNode.left = targetNode.right; 
                        } else { 
                            parentNode.right = targetNode.right; 
                        } 
                    } else { 
                        //如果父節(jié)點是空，讓root換位 
                        root = targetNode.right; 
                    } 
 
                } 
            } 
        } 
    } 
 
    //添加節(jié)點 
    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; 
    } 
 
    /** 
     * 查找要刪除節(jié)點的父節(jié)點 
     * 
     * @param node 要刪除的節(jié)點 
     * @return 要刪除節(jié)點的父節(jié)點 
     */ 
    public Node searchParent(Node node) { 
        //如果當前節(jié)點就是要刪除節(jié)點的父節(jié)點就返回 
        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) { 
                //如果查找的節(jié)點的值小于當前節(jié)點的值，向左子樹遞歸查找 
                return this.left.searchParent(node); 
            } else if (this.right != null && value >= this.value) { 
                //如果查找的節(jié)點的值小于當前節(jié)點的值，向左子樹遞歸查找 
                return this.right.searchParent(node); 
            } else { 
                return null; 
            } 
        } 
    } 
 
    /** 
     * 查找要刪除的節(jié)點 
     * 
     * @param value 要刪除的節(jié)點的值 
     * @return 刪除的節(jié)點 
     */ 
    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; 
            } 
        } 
    } 
 
    //遞歸的形式添加節(jié)點，滿足二叉排序樹的要求 
    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 { 
                //遞歸向右子節(jié)點添加 
                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 + 
                '}'; 
    } 
} 

 【編輯推薦】