手寫完美的二叉排序樹

二叉排序樹，也叫搜索樹、查找樹，是一種有順序的二叉樹，或者是一顆空樹，或者是一顆。

它有以下特點：

1、若左子樹不為空，那么左子樹上面的所有節(jié)點的關(guān)鍵字值都比根節(jié)點的關(guān)鍵字值小
2、若右子樹不為空，那么右子樹上面的所有節(jié)點的關(guān)鍵字值都比根節(jié)點的關(guān)鍵字值大
3、左右子樹都為二叉樹
4、沒有重復(fù)值（這一點在實際中可以忽略）

應(yīng)用場景

在大數(shù)據(jù)中，越來越廣泛的頻繁使用二叉樹，解決各種大數(shù)據(jù)查詢的問題。在jdk1.8+版本中的大量的數(shù)據(jù)結(jié)構(gòu)，都換成樹來處理，而且樹在大數(shù)據(jù)里，性能是做好的。它的作用就是快速查找。時間復(fù)雜度介于O(log?n)到O(n)之間，數(shù)據(jù)量越大，越接近于O(log?n)，性能越優(yōu)。

代碼實踐

1、使用孩子雙親法表示法來定義樹

public class Node<T extends Comparable> {
    T data;
    Node<T> leftChild;
    Node<T> rightChild;
    Node<T> parent;

    public Node(T data) {
        this.data = data;
        leftChild = null;
        rightChild = null;
        parent = null;
    }
}

2、首先實現(xiàn)新增的方法，在樹的葉子節(jié)點添加一個節(jié)點

/**
 * 新增一個節(jié)點
 *
 * @param data
 * @return
 */
public Node put(T data) {
    Node<T> newNode = new Node(data);
    if (root == null) {
        root = newNode;
        return newNode;
    }
    Node<T> parent = null;
    Node<T> node = root;
    while (node != null) {
        parent = node;
        if (node.data.compareTo(data) > 0) {//小于跟節(jié)點就往左查詢
            node = node.leftChild;
        } else if (node.data.compareTo(data) < 0) {//大于跟節(jié)點就往右查詢
            node = node.rightChild;
        } else {//是重復(fù)值 就不理會了
            return node;
        }
    }
    if (parent.data.compareTo(data) > 0) {
        parent.leftChild = newNode;
    } else {
        parent.rightChild = newNode;
    }
    newNode.parent = parent;
    size++;
    return newNode;
}

3、查找節(jié)點

public Node get(T data) {
    if (root == null) {
        return null;
    }
    Node<T> node = root;
    while (node != null) {
        if (node.data.compareTo(data) > 0) {
            node = node.leftChild;
        } else if (node.data.compareTo(data) < 0) {
            node = node.rightChild;
        } else {
            return node;
        }
    }
    return null;
}

4、遍歷樹，采用中序遍歷。

/**
 * 中序遍歷
 *
 * @param node
 */
public void middleOrderTraseval(Node<T> node) {
    if (node == null) {
        return;
    }
    middleOrderTraseval(node.leftChild);
    System.out.print(node.data + "    ");
    middleOrderTraseval(node.rightChild);
}

5、刪除節(jié)點（難點）分四種情況

1. 要刪除node是葉子節(jié)點

if (left == null && right == null) {
        if (parent == null) {
            root = null;
        } else {
            if (parent.leftChild == node) {
                parent.leftChild = null;
            } else {
                parent.rightChild = null;
            }
            node.parent = null;
        }
    }

2. 要刪除node節(jié)點只有左節(jié)點

else if (left != null && right == null) {
    if (parent == null) {
        root = left;
    } else {
        if (parent.leftChild == node) {
            parent.leftChild = left;
        } else {
            parent.rightChild = left;
        }
    }
    left.parent = parent;
    node.leftChild = null;
    node.parent = null;
}

3. 要刪除node節(jié)點只有右節(jié)點

else if (left == null && right != null) {
    if (parent == null) {
            root = right;
    } else {
        if (parent.leftChild == node) {
                parent.leftChild = right;
        } else {
                parent.rightChild = right;
            }
        }
        right.parent = parent;
        node.rightChild = null;
        node.parent = null;
}

4. 要刪除node節(jié)點左右節(jié)點都有

else if (left != null && right != null) {
    Node<T> leftMinNode = getLeftMinNode(right);
    // 1. 把右節(jié)點最小的節(jié)點接上node的左節(jié)點
    leftMinNode.leftChild = left;
    left.parent = leftMinNode;
    // 2. 如果右節(jié)點最小的節(jié)點，如果有右節(jié)點，則把右節(jié)點接上父節(jié)點
    Node<T> leftMinNodeParent = leftMinNode.parent;
    if (leftMinNode.rightChild != null) {
        if (leftMinNodeParent != node) {
            leftMinNodeParent.leftChild = leftMinNode.rightChild;
            leftMinNode.rightChild.parent = leftMinNodeParent;
        }
    } else {
        //沒有右節(jié)點，則要把最小節(jié)點的父節(jié)點的左節(jié)點賦空
        leftMinNodeParent.leftChild = null;
    }
    // 3. 把右節(jié)點最小節(jié)點接上node的右節(jié)點上
    if (leftMinNode != right) {
        leftMinNode.rightChild = right;
    }
    right.parent = leftMinNode;
    // 4. 接上node的父節(jié)點
    if (parent == null) {
        root = leftMinNode;
    } else {
        if (parent.leftChild == node) {
            parent.leftChild = leftMinNode;
        } else {
            parent.rightChild = leftMinNode;
        }
    }
    leftMinNode.parent = parent;
    node.leftChild = null;
    node.rightChild = null;
    node.parent = null;
}

6、完整代碼

public class SearchBinaryTree<T extends Comparable> {

//二叉樹跟節(jié)點
private Node<T> root;
//二叉樹大小
private int size;

/**
 * 新增一個節(jié)點
 *
 * @param data
 * @return
 */
public Node put(T data) {
    Node<T> newNode = new Node(data);
    if (root == null) {
        root = newNode;
        return newNode;
    }
    Node<T> parent = null;
    Node<T> node = root;
    while (node != null) {
        parent = node;
        if (node.data.compareTo(data) > 0) {//小于跟節(jié)點就往左查詢
            node = node.leftChild;
        } else if (node.data.compareTo(data) < 0) {//大于跟節(jié)點就往右查詢
            node = node.rightChild;
        } else {//是重復(fù)值 就不理會了
            return node;
        }
    }
    if (parent.data.compareTo(data) > 0) {
        parent.leftChild = newNode;
    } else {
        parent.rightChild = newNode;
    }
    newNode.parent = parent;

    size++;

    return newNode;
}

public int getSize() {
    return size;
}

public Node get(T data) {
    if (root == null) {
        return null;
    }
    Node<T> node = root;
    while (node != null) {
        if (node.data.compareTo(data) > 0) {
            node = node.leftChild;
        } else if (node.data.compareTo(data) < 0) {
            node = node.rightChild;
        } else {
            return node;
        }
    }
    return null;
}

public void middleOrderTraseval() {
    middleOrderTraseval(root);
}

/**
 * 中序遍歷
 *
 * @param node
 */
public void middleOrderTraseval(Node<T> node) {
    if (node == null) {
        return;
    }
    middleOrderTraseval(node.leftChild);
    System.out.print(node.data + "    ");
    middleOrderTraseval(node.rightChild);
}

public void deleteNode(Node<T> node) {
    if (node == null) {
        return;
    }
    Node<T> left = node.leftChild;
    Node<T> right = node.rightChild;
    Node<T> parent = node.parent;
    //第一種情況：node是葉子節(jié)點
    if (left == null && right == null) {
        if (parent == null) {
            root = null;
        } else {
            if (parent.leftChild == node) {
                parent.leftChild = null;
            } else {
                parent.rightChild = null;
            }
            node.parent = null;
        }
    }
    //第二種情況：node只有左節(jié)點，沒有右節(jié)點的情況
    else if (left != null && right == null) {
        if (parent == null) {
            root = left;
        } else {
            if (parent.leftChild == node) {
                parent.leftChild = left;
            } else {
                parent.rightChild = left;
            }
        }
        left.parent = parent;
        node.leftChild = null;
        node.parent = null;
    }
    //第三種情況：node只有右節(jié)點，沒有左節(jié)點的情況
    else if (left == null && right != null) {
        if (parent == null) {
            root = right;
        } else {
            if (parent.leftChild == node) {
                parent.leftChild = right;
            } else {
                parent.rightChild = right;
            }
        }
        right.parent = parent;
        node.rightChild = null;
        node.parent = null;
    }
    //第四種情況：node左右節(jié)點都有的情況
    else if (left != null && right != null) {
        Node<T> leftMinNode = getLeftMinNode(right);
        // 1. 把右節(jié)點最小的節(jié)點接上node的左節(jié)點
        leftMinNode.leftChild = left;
        left.parent = leftMinNode;
        // 2. 如果右節(jié)點最小的節(jié)點，如果有右節(jié)點，則把右節(jié)點接上父節(jié)點
        Node<T> leftMinNodeParent = leftMinNode.parent;
        if (leftMinNode.rightChild != null) {
            if (leftMinNodeParent != node) {
                leftMinNodeParent.leftChild = leftMinNode.rightChild;
                leftMinNode.rightChild.parent = leftMinNodeParent;
            }
        } else {
            //沒有右節(jié)點，則要把最小節(jié)點的父節(jié)點的左節(jié)點賦空
            leftMinNodeParent.leftChild = null;
        }
        // 3. 把右節(jié)點最小節(jié)點接上node的右節(jié)點上
        if (leftMinNode != right) {
            leftMinNode.rightChild = right;
        }
        right.parent = leftMinNode;
        // 4. 接上node的父節(jié)點
        if (parent == null) {
            root = leftMinNode;
        } else {
            if (parent.leftChild == node) {
                parent.leftChild = leftMinNode;
            } else {
                parent.rightChild = leftMinNode;
            }
        }
        leftMinNode.parent = parent;
        node.leftChild = null;
        node.rightChild = null;
        node.parent = null;
    }
    size--;
}

/**
 * 獲取當(dāng)前節(jié)點的左邊最小的值，也就是最左邊的節(jié)點
 *
 * @param node
 * @return
 */
public Node<T> getLeftMinNode(Node<T> node) {
    if (node == null) {
        return null;
    }
    Node currentRoot = node;
    while (currentRoot.leftChild != null) {
        currentRoot = currentRoot.leftChild;
    }
    return currentRoot;
}

/**
 * 使用孩子雙親法表示法來定義樹（實際雙向鏈表）
 * @param <T> 對象
 */
public class Node<T extends Comparable> {
    T data;
    Node<T> leftChild;
    Node<T> rightChild;
    Node<T> parent;

    public Node(T data) {
        this.data = data;
        leftChild = null;
        rightChild = null;
        parent = null;
    }
}

}

7、測試

 @Test
public void testBinarySortTree(){
    BinarySortTree<Integer> tree = new BinarySortTree();
    //5  2  7  3  4  1  6
    int[] array=new int[]{5,2,7,3,4,1,8,6,9};
    for (int i = 0; i < array.length; i++) {
        int i1 = array[i];
        tree.put(i1);
    }
    tree.middleOrderTraseval();

    System.out.println();

     //刪除單個
    tree.deleteNode(tree.get(7));

    tree.middleOrderTraseval();

    System.out.println();

    for (int i : array) {
        tree.middleOrderTraseval();
        System.out.println("------------------------------");
        tree.deleteNode(tree.get(i));
    }

    System.out.println();
    for (int i = 0; i < array.length; i++) {
        tree.put(array[i]);
    }
    tree.middleOrderTraseval();

}

8、測試結(jié)果

1    2    3    4    5    6    7    8    9    
1    2    3    4    5    6    8    9    
1    2    3    4    5    6    8    9    ------------------------------
1    2    3    4    6    8    9    ------------------------------
1    3    4    6    8    9    ------------------------------
1    3    4    6    8    9    ------------------------------
1    4    6    8    9    ------------------------------
1    6    8    9    ------------------------------
6    8    9    ------------------------------
6    9    ------------------------------
9    ------------------------------

1    2    3    4    5    6    7    8    9

9、結(jié)束

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容