二叉查找樹(shù)是一種特殊的二叉樹(shù)勋陪，任意一個(gè)節(jié)點(diǎn)，右子樹(shù)中的所有的值都比節(jié)點(diǎn)本身大拱撵，左子樹(shù)中所有的值都比節(jié)點(diǎn)本身的值要小辉川。

二叉查找樹(shù)

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

一棵二叉查找樹(shù).png

二叉查找樹(shù)的插入

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

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

二叉查找樹(shù)的查詢

查詢操作跟插入操作基本一樣，都是通過(guò)對(duì)二叉樹(shù)的層層比較來(lái)找到需要查找的值咽安。

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

二叉查找樹(shù)的刪除

刪除節(jié)點(diǎn)的操作是最復(fù)雜的操作伴网，隨著刪除的節(jié)點(diǎn)的位置不同，可以分為幾種不同的情況來(lái)進(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)只有左子樹(shù)或者只有右子樹(shù)

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

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

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

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

這種情況下红选，我們需要遍歷該節(jié)點(diǎn)的右子樹(shù)澜公，找到右子樹(shù)中值最小的節(jié)點(diǎn)。該節(jié)點(diǎn)一定是右子樹(shù)中最“靠左”的節(jié)點(diǎn)喇肋。這個(gè)最靠左的節(jié)點(diǎn)一定沒(méi)有左子樹(shù)了坟乾，如果有左子樹(shù)的話它也就不是最小值的節(jié)點(diǎn)了。

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

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

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

刪除后鹊漠，先序遍歷二叉樹(shù)的話主到，結(jié)果將會(huì)是：25 => 16 => 10 => 18 => 21 => 28 => 30（后面程序中會(huì)有驗(yàn)證）

算法實(shí)現(xiàn)

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

# 引入的上一篇文章中的二叉樹(shù)查找相關(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)，以及這個(gè)節(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

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

    # 要?jiǎng)h除的節(jié)點(diǎn)是中間的節(jié)點(diǎn)
    if p.leftNode != None and p.rightNode != None:
        # 應(yīng)找到右子樹(shù)中最左邊的節(jié)點(diǎn)登钥，就是右子樹(shù)中值最小的節(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ǎng)h除的那個(gè)最小節(jié)點(diǎn)牧牢，這樣的話看锉，在后面統(tǒng)一刪除葉子節(jié)點(diǎn)的時(shí)候會(huì)將其刪掉
        p = minNode
        pp = pMinNode

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

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



# 定義一個(gè)全局的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('先序遍歷二叉樹(shù)的結(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之后的先序遍歷二叉樹(shù)：")
TraversingBinaryTree.preorder_traversal(tree)

結(jié)果是：

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

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