寫在前面

最近在leetcode上做了一些關(guān)于二叉搜索樹（BST）的題目，仔細(xì)看了下關(guān)于BST的資料，這兒自己做一個簡單的總結(jié)，可能在后面的題目中也會遇到關(guān)于BST更難的題（我是按順序簡單到困難），也方便查閱。

簡單介紹

樹是一種重要的數(shù)據(jù)結(jié)構(gòu)，在面試中也問得比較多。

二叉搜索樹首先是二叉樹。二叉樹是每個節(jié)點(diǎn)最多只有兩個分支的樹結(jié)構(gòu)，通常稱作“左子樹”和“右子樹”，二叉樹的分支具有左右次序，不能顛倒。關(guān)于二叉樹有一些性質(zhì)以及存在其他的二叉樹，在這我不做過多介紹。

二叉搜索樹又稱有序二叉樹、排序二叉樹。因為它的節(jié)點(diǎn)是具有一定順序的。
我們來看下它的主要性質(zhì)，通過這些主要性質(zhì)你就可以了解到二叉搜索樹是一種什么樣的二叉樹。
性質(zhì)：

1. 若任意節(jié)點(diǎn)的左子樹不空，則左子樹上所有節(jié)點(diǎn)的值均小于它的根節(jié)點(diǎn)的值；
2. 若任意節(jié)點(diǎn)的右子樹不空，則右子樹上所有節(jié)點(diǎn)的值均大于它的根節(jié)點(diǎn)的值；
3. 任意節(jié)點(diǎn)的左、右子樹也分別為二叉查找樹；
4. 沒有鍵值相等的節(jié)點(diǎn)。

基本操作

1. 定義

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

2. 查找

流程：
a.從root節(jié)點(diǎn)開始
b.若root值等于查找值，返回真
c.若root值小于查找值，找右節(jié)點(diǎn)
d.若root值大于查找值，找左節(jié)點(diǎn)
e.最后都沒找到，返回假
代碼：

def find(self, root, value):
    """
    :param root: TreeNode
    :param value: int
    :return: boolean
    """
    while root:
        if root.val == value:
            return True
        elif root.val > value:
            root = root.left
        else:
            root = root.right
    return False

3. 插入（構(gòu)造BST）

流程：
a. 從root節(jié)點(diǎn)開始
b. 若root為空，則root為插入值
c. 循環(huán)：
d. 若當(dāng)前節(jié)點(diǎn)值大于插入值，找左節(jié)點(diǎn)
e. 若當(dāng)前節(jié)點(diǎn)值小于插入值，找右節(jié)點(diǎn)
代碼：

def inset(self, root, num):
    """
    :param num: int
    :param root: TreeNode
    :return: TreeNode
    """
    newNode = TreeNode(num)
    ans = root
    if not root:
        return newNode
    while True:
        parent = root
        if num < root.val:
            root = root.left
            if not root:
                parent.left = newNode
                return ans
        else:
            root = root.right
            if not root:
                parent.right = newNode
                return ans

4. 刪除

根據(jù)待刪除節(jié)點(diǎn)分三種情況：
1） 沒有子節(jié)點(diǎn)
直接刪除該節(jié)點(diǎn)，然后父節(jié)點(diǎn)指為空
2）只有一個子節(jié)點(diǎn)
直接刪除該節(jié)點(diǎn)，然后父節(jié)點(diǎn)指向子節(jié)點(diǎn)
3）有兩個子節(jié)點(diǎn)
對于有兩個節(jié)點(diǎn)的有兩種方式，用被刪除節(jié)點(diǎn)的左子樹的最右節(jié)點(diǎn)或者右子樹的最左節(jié)點(diǎn)替代刪除節(jié)點(diǎn)，并修改相應(yīng)的最左最右的父節(jié)點(diǎn)的指針。

def deleteNode(self, root, key):
    if not root:
        print 'not find key:', key
    elif key < root.key:
        root.left = self.deleteNode(root.left, key)
    elif key > root.key:
        root.right = self.deleteNode(root.right, key)
    elif root.left and root.right:
        right_min = self.find_min(self.root.right)
        root.key = right_min.key
        root.right = self.deleteNode(root.right, right_min.key)
    elif root.left:
        root = root.left
    elif root.right:
        root = root.right
    else；
        root = None
    return root

def find_min(self, root):
    if not root.left:
        return root
    return self.find_min(root.left)

更多文章請訪問我的博客