[[390181]]

基本介紹

二叉排序樹：BST(Binary Sort(Search) Tree)，對(duì)于二叉排序樹的任何一個(gè)非葉子節(jié)點(diǎn)，要求左節(jié)點(diǎn)的值，比當(dāng)前節(jié)點(diǎn)的值小，右節(jié)點(diǎn)的值比當(dāng)前節(jié)點(diǎn)的值大。

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

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

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

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

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

1. 需要先找到要?jiǎng)h除的節(jié)點(diǎn) targetNode
2. 找到 targetNode 的父節(jié)點(diǎn) parentNode(考慮是否存在父節(jié)點(diǎn))
3. 確定 targetNode 是 parentNode 的左子節(jié)點(diǎn)還是右子節(jié)點(diǎn)
4. 根據(jù)前面的來(lái)對(duì)應(yīng)刪除，左子節(jié)點(diǎn)=>parent.left = null，右子節(jié)點(diǎn)=>parent.right = null;

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

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

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

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

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

 【編輯推薦】