二叉查找樹是一種特殊的二叉樹，任意一個節(jié)點(diǎn)，右子樹中的所有的值都比節(jié)點(diǎn)本身大，左子樹中所有的值都比節(jié)點(diǎn)本身的值要小。

二叉查找樹

使用二叉查找樹來進(jìn)行數(shù)據(jù)的插入、查找、刪除的效率是很高的。整體上來體會，由于是二叉樹的結(jié)構(gòu)，所以最直觀的給人的體會就是查找數(shù)據(jù)，速度會很快。

一棵二叉查找樹.png

二叉查找樹的插入

向一棵 普通 的二叉查找樹中插入一個數(shù)據(jù)，這個數(shù)據(jù)肯定是插入之后作為了 葉子節(jié)點(diǎn) 的。從根節(jié)點(diǎn)開始，每次都比較當(dāng)前的節(jié)點(diǎn)與要插入節(jié)點(diǎn)的值的大小關(guān)系，如果當(dāng)前節(jié)點(diǎn)的值大于要插入的節(jié)點(diǎn)的值，就遍歷當(dāng)前節(jié)點(diǎn)的左子樹繼續(xù)找位置，反之遍歷右子樹。找到最終的位置插入值。比如，我們向已知的一棵二叉查找樹插入一個值：

插入節(jié)點(diǎn)21到已有的二叉查找樹中.png

二叉查找樹的查詢

查詢操作跟插入操作基本一樣，都是通過對二叉樹的層層比較來找到需要查找的值。

查找節(jié)點(diǎn)值為21的節(jié)點(diǎn).png

二叉查找樹的刪除

刪除節(jié)點(diǎn)的操作是最復(fù)雜的操作，隨著刪除的節(jié)點(diǎn)的位置不同，可以分為幾種不同的情況來進(jìn)行刪除。

• 1. 刪除的是葉子節(jié)點(diǎn)

被刪除的是葉子節(jié)點(diǎn).png

被刪除的如果是葉子節(jié)點(diǎn)的話，那么只需要把該葉子節(jié)點(diǎn)的父節(jié)點(diǎn)中指向該被刪除節(jié)點(diǎn)的指針（左或者右）置空就可以了。

• 2. 刪除的節(jié)點(diǎn)只有左子樹或者只有右子樹

被刪除的節(jié)點(diǎn)只含有一棵子樹.png

這種情況，我們只需要將該節(jié)點(diǎn)刪除，并且用它的子樹來代替它的位置“取而代之”即可。

• 3. 刪除的節(jié)點(diǎn)含有左子樹和右子樹

被刪除的節(jié)點(diǎn)含有左右子樹.png

這種情況下，我們需要遍歷該節(jié)點(diǎn)的右子樹，找到右子樹中值最小的節(jié)點(diǎn)。該節(jié)點(diǎn)一定是右子樹中最“靠左”的節(jié)點(diǎn)。這個最靠左的節(jié)點(diǎn)一定沒有左子樹了，如果有左子樹的話它也就不是最小值的節(jié)點(diǎn)了。

只有找到這個點(diǎn)，并且用這個點(diǎn)取代該要被刪除節(jié)點(diǎn)，才能使這個節(jié)點(diǎn)唄替換掉了之后，該節(jié)點(diǎn)的左子樹中的值全都小于它，右子樹中的所有值全都大于它。

我們以15這個節(jié)點(diǎn)為例，刪掉15這個節(jié)點(diǎn)之后，我們找到最靠左的節(jié)點(diǎn)，就是16這個節(jié)點(diǎn)，我們用16這個15的右子樹中最小的節(jié)點(diǎn)的值替代15這個節(jié)點(diǎn)的值，然后將16的父節(jié)點(diǎn)18的左子節(jié)點(diǎn)置空，這樣就完成了15節(jié)點(diǎn)的刪除工作。

刪除15節(jié)點(diǎn).png

刪除后，先序遍歷二叉樹的話，結(jié)果將會是：25 => 16 => 10 => 18 => 21 => 28 => 30（后面程序中會有驗證）

算法實現(xiàn)

# -*- coding: utf-8 -*-
# @Time    : 2019-03-28 16:06
# @Author  : Jaedong
# @Version : 3.6
# @File    : BinarySearchTree.py
# @Software: PyCharm

# 引入的上一篇文章中的二叉樹查找相關(guān)，方便打印
import TraversingBinaryTree

# 節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)
class Node:
    value = -1
    leftNode = None
    rightNode = None

    def __init__(self, value, leftNode, rightNode):
        self.value = value
        self.leftNode = leftNode
        self.rightNode = rightNode

# 插入節(jié)點(diǎn)
def insert_node(node):
    global tree
    if tree == None:
        tree = node
        return

    p = tree
    while p != None:
        if p.value > node.value:
            if p.leftNode == None:
                p.leftNode = node
                return
            else:
                p = p.leftNode
        else:
            if p.rightNode == None:
                p.rightNode = node
                return
            else:
                p = p.rightNode

# 查找相應(yīng)值的節(jié)點(diǎn)
def search_node(value):
    global tree
    if tree == None:
        return None

    p = tree
    while p != None:
        if p.value > value:
            p = p.leftNode
        elif p.value < value:
            p = p.rightNode
        else:
            return p

    return None

# 刪除相應(yīng)的節(jié)點(diǎn)
def delete_node(value):
    global tree
    p = tree
    pp = None

    # 找到值為value的節(jié)點(diǎn)，以及這個節(jié)點(diǎn)的父節(jié)點(diǎn)
    while p != None and value != p.value:
        pp = p
        if p.value > value:
            p = p.leftNode
        elif p.value < value:
            p = p.rightNode

    # 沒有找到相應(yīng)的值的節(jié)點(diǎn)
    if p == None:
        return

    # 要刪除的節(jié)點(diǎn)是中間的節(jié)點(diǎn)
    if p.leftNode != None and p.rightNode != None:
        # 應(yīng)找到右子樹中最左邊的節(jié)點(diǎn)，就是右子樹中值最小的節(jié)點(diǎn)，替換掉當(dāng)前的節(jié)點(diǎn)的值，并刪除掉最小節(jié)點(diǎn)
        minNode = p.rightNode
        pMinNode = p
        while minNode.leftNode != None:
            pMinNode = minNode
            minNode = minNode.leftNode

        # 找到了最小節(jié)點(diǎn)之后, 最小的節(jié)點(diǎn)肯定是葉子節(jié)點(diǎn)
        p.value = minNode.value
        # 把p和pp指向要刪除的那個最小節(jié)點(diǎn)，這樣的話，在后面統(tǒng)一刪除葉子節(jié)點(diǎn)的時候會將其刪掉
        p = minNode
        pp = pMinNode

    # 要刪除的節(jié)點(diǎn)是葉子節(jié)點(diǎn)或者只有一個子節(jié)點(diǎn)
    childNode = None
    if p.leftNode == None:
        childNode = p.rightNode
    else:
        childNode = p.leftNode

    if pp == None:          # 要刪除的節(jié)點(diǎn)，正好是根節(jié)點(diǎn)，并且只有一個或者沒有子節(jié)點(diǎn)
        tree = childNode
    elif pp.leftNode == p:  # 要刪除的節(jié)點(diǎn)是父節(jié)點(diǎn)的左子節(jié)點(diǎn)
        pp.leftNode = childNode
    elif pp.rightNode == p: # 要刪除的節(jié)點(diǎn)是父節(jié)點(diǎn)的右子節(jié)點(diǎn)
        pp.rightNode = childNode



# 定義一個全局的tree，以及tree中的相關(guān)數(shù)據(jù)
tree = None
values = [25, 15, 10, 18, 16, 21, 28, 30]
for value in values:
    node = Node(value, None, None)
    insert_node(node)

print('先序遍歷二叉樹的結(jié)果：')
TraversingBinaryTree.preorder_traversal(tree)
print('查找到的節(jié)點(diǎn)的值：')
searched = search_node(18)
print(searched.value)
print("刪除節(jié)點(diǎn)15...")
delete_node(15)
print("刪除節(jié)點(diǎn)15之后的先序遍歷二叉樹：")
TraversingBinaryTree.preorder_traversal(tree)

結(jié)果是：

程序運(yùn)行結(jié)果.png

上一篇：寫給媳婦兒的算法（十五）——二叉樹及其遍歷