寫(xiě)在前面
最近在leetcode上做了一些關(guān)于二叉搜索樹(shù)（BST）的題目倒戏，仔細(xì)看了下關(guān)于BST的資料欺缘，這兒自己做一個(gè)簡(jiǎn)單的總結(jié)棚瘟，可能在后面的題目中也會(huì)遇到關(guān)于BST更難的題（我是按順序簡(jiǎn)單到困難）留荔，也方便查閱蝇棉。
簡(jiǎn)單介紹
樹(shù)是一種重要的數(shù)據(jù)結(jié)構(gòu)讨阻，在面試中也問(wèn)得比較多。
二叉搜索樹(shù)首先是二叉樹(shù)篡殷。二叉樹(shù)是每個(gè)節(jié)點(diǎn)最多只有兩個(gè)分支的樹(shù)結(jié)構(gòu)钝吮，通常稱作“左子樹(shù)”和“右子樹(shù)”，二叉樹(shù)的分支具有左右次序板辽，不能顛倒奇瘦。關(guān)于二叉樹(shù)有一些性質(zhì)以及存在其他的二叉樹(shù)，在這我不做過(guò)多介紹劲弦。
二叉搜索樹(shù)又稱有序二叉樹(shù)耳标、排序二叉樹(shù)。因?yàn)樗墓?jié)點(diǎn)是具有一定順序的瓶您。
我們來(lái)看下它的主要性質(zhì)麻捻，通過(guò)這些主要性質(zhì)你就可以了解到二叉搜索樹(shù)是一種什么樣的二叉樹(shù)。
性質(zhì)：
- 若任意節(jié)點(diǎn)的左子樹(shù)不空呀袱，則左子樹(shù)上所有節(jié)點(diǎn)的值均小于它的根節(jié)點(diǎn)的值贸毕；
- 若任意節(jié)點(diǎn)的右子樹(shù)不空，則右子樹(shù)上所有節(jié)點(diǎn)的值均大于它的根節(jié)點(diǎn)的值夜赵；
- 任意節(jié)點(diǎn)的左明棍、右子樹(shù)也分別為二叉查找樹(shù)；
- 沒(méi)有鍵值相等的節(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)開(kāi)始
b.若root值等于查找值摊腋，返回真
c.若root值小于查找值，找右節(jié)點(diǎn)
d.若root值大于查找值嘁傀，找左節(jié)點(diǎn)
e.最后都沒(méi)找到兴蒸，返回假
代碼：
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)開(kāi)始
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） 沒(méi)有子節(jié)點(diǎn)
直接刪除該節(jié)點(diǎn)，然后父節(jié)點(diǎn)指為空
2）只有一個(gè)子節(jié)點(diǎn)
直接刪除該節(jié)點(diǎn)，然后父節(jié)點(diǎn)指向子節(jié)點(diǎn)
3）有兩個(gè)子節(jié)點(diǎn)
對(duì)于有兩個(gè)節(jié)點(diǎn)的有兩種方式岛啸，用被刪除節(jié)點(diǎn)的左子樹(shù)的最右節(jié)點(diǎn)或者右子樹(shù)的最左節(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)
更多文章請(qǐng)?jiān)L問(wèn)我的博客
