【python實現】二叉搜尋樹插入、刪除、查詢
二叉搜尋樹
定義：如果一顆二叉樹的每個節點對應一個關鍵碼值，且關鍵碼值的組織是有順序的，例如左子節點值小於父節點值，父節點值小於右子節點值，則這棵二叉樹是一棵二叉搜尋樹。
類（TreeNode）：定義二叉搜尋樹各個節點
在該類中，分別存放節點本身的值，以及其左子節點，右子節點，父節點的值。
class TreeNode(object): def __init__(self,val): self.value = val#存值 self.left = None#存本節點的左子節點 self.right = None#存本節點的右子節點 self.father = None#存本節點的父節點
類（BST）：定義二叉搜尋樹的各種功能方法
此類用於存放定義二叉樹的插入，刪除，搜尋等方法。
class BST(object): def __init__(self,nodeList): self.root = None for node in nodeList: self.bfs_insert(node)
注：self.bfs_insert(node)中的bfs_insert方法在後面實現。放在建構函式中的目的是將一個列表生成一個二叉搜尋樹列表。
方法（bfs_insert）：實現插入功能
第一步：將根節點（self.root）設定成當前位置節點（cur），即從根節點開始遍歷。根節點的父節點（father）初始設定為None。
def bfs_insert(self,node): cur = self.root#設定當前節點為根節點 father = None#設定根節點的父節點為None
第二步：查詢可以插入的位置
1. 當前位置節點（cur）的值與待插入節點（node）的值相等，返回-1（代表無法進行插入操作）。並將父節點（father）值修改為當前位置節點（cur），代表該節點已經遍歷完成。
if cur.value == node.value: return -1 father = cur
2.當前位置節點（cur）的值大於待插入節點（node）的值時，表示待插入節點（node）需繼續在當前位置節點的左子樹中繼續查詢。故把當前位置節點（cur）的左節點賦值給當前位置節點（cur），作為下一個要訪問的節點物件。
if node.value < cur.value: cur = cur.left
3.當前位置節點（cur）的值小於待插入節點（node）的值時，表示待插入節點（node）需繼續在當前位置節點的右子樹中繼續查詢。故把當前位置節點（cur）的右節點賦值給當前位置節點（cur），作為下一個要訪問的節點物件。
if node.value > cur.value: cur = cur.right
第三步：找到插入位置後，將其設定為待插入值（node）的父節點
node.father = father
第四步：插入操作
1.父節點的值為空（即要插入的是個空二叉樹），將待插入節點（node）賦值給根節點（root）。
if father == None: self.root = node
2.待插入節點（node）的值小於父節點（father）的值，將其放到父節點的左子節點
if node.value <father.value: father.left = node
3.待插入節點（node）的值大於父節點（father）的值，將其放到父節點的右子節點
if node.value >father.value: father.right = node
插入功能程式碼彙總：
def insert(self,node): father = None cur = self.root while cur != None: if cur.value == node.value: return -1 father = cur if node.value < cur.value: cur = cur.left else: cur = cur.right node.father = father if father == None: self.root = node elif node.value < father.value: father.left = node else: father.right = node
方法（bfs）：生成二叉搜尋樹列表
利用佇列先進先出的特性，將一個二叉搜尋樹存放到列表中。
def bfs(self): if self.root == None: return None retList = [] q = queue.Queue() q.put(self.root) while q.empty() is not True: node = q.get() retList.append(node.value) if node.left != None: q.put(node.left) if node.right != None: q.put(node.right) return retList
示例：針對如下二叉搜尋樹，遍歷存放到一個列表過程
ps：藍色：二叉樹列表 retList 橙色：佇列 q
方法（bfs_search）：實現查詢功能
第一步：將根節點（self.root）設定成當前位置節點（cur），即從根節點開始遍歷。
def search(self,value): cur = self.root
如果cur值不為None，執行第二步。否則執行第三步
第二步：對比要查詢的值（value）與當前位置節點（cur）的值的大小
1. 如果當前位置節點（cur）的值等於要查詢的值（value），返回當前位置節點（cur）。
if cur.value == value: return cur
2. 如果當前位置節點（cur）的值小於要查詢的值（value），返回當前位置節點（cur）。
if cur.value < value: cur = cur.right
3. 如果當前位置節點（cur）的值小於要查詢的值（value），返回當前位置節點（cur）。
if cur.value > value: cur = cur.left
第三步：如果cur的值為None，返回空。即查詢的二叉搜尋樹為空樹。
return None
查詢功能程式碼彙總：
def search(self,value): cur = self.root while cur != None: if cur.value == value: return cur elif cur.value < value: cur = cur.right else: cur = cur.left return None
方法（bfs_delete）：實現刪除功能
第一步：將待刪除節點（node）的父節點賦值給father變數。
def delete(self,node): father = node.father
第二步：判斷待刪除節點（node）的左子樹是否為空
1. 待刪除節點（node）的左子樹為空
if node.left == None:
a) 待刪除節點（node）為根節點
將待刪除節點（node）的右子節點置為新的根節點（root），且其如果為非空，將其父節點（node.right.father）賦值為空。
if father == None: self.root = node.right if node.right != None: node.right.father = None
b) 待刪除節點（node）為其父節點的左子節點
待刪除節點（node）的右子節點（node.right）取代其原來的位置，成為其父節點新的左子節點（father.left）。且其右子節點（node.right）不為空，將待刪除節點（node）的父節點賦值給它的父節點（node.right.father）
if father.left == node: father.left = node.right if node.right != None: node.right.father = father
c) 待刪除節點（node）為其父節點的右子節點
待刪除節點（node）的右子節點（node.right）取代其原來的位置，成為其父節點新的右子節點（father.right）。且其右子節點（node.right）不為空，將待刪除節點（node）的父節點賦值給它的父節點（node.right.father）
if father.right == node: father.right = node.right if node.right != None: node.right.father = father
2. 待刪除節點（node）的左子樹不為空
第一步：將待刪除節點（node）的右子樹掛到其左子樹最後一層的右子節點下
a) 將待刪除節點的左子節點（node.left）存到臨時變數tmpNode中
tmpNode = node.left
b) 遞迴找到node.left的最後一層右子節點
while tmpNode.right != None: tmpNode = tmpNode.right
c) 將待刪節點的右子樹（node.right）掛到node.left的最後一層右子節點下
tmpNode.right = node.right
d) 將node.right的父節點設定為待刪節點左子樹中的最後一層的右子節點
if node.right != None: node.right.father = tmpNode
第二步：開始刪除node
1.待刪除節點為根節點
將待刪除節點的左子節點（node.left）設定為根節點（self.root），並將其父節點設定為空。
if father == None: self.root = node.left node.left.father = None
2.待刪除節點為根節點的左子節點
待刪除節點的左子節點（node.left）取代待刪節點的位置，並將其父節點設定為待刪除節點的父節點。
if father.left == node: father.left = node.left node.left.father = father
3. 待刪除節點為根節點的右子節點
待刪除節點的左子節點（node.left）取代待刪節點的位置，並將其父節點設定為待刪除節點的父節點
if father.right == node: father.right = node.left node.left.father = father
刪除功能程式碼彙總：
def delete(self,node): father = node.father if node.left == None: if father == None: self.root = node.right if node.right != None: node.right.father = None elif father.left == node: father.left = node.right if node.right != None: node.right.father = father else: father.right = node.right if node.right != None: node.right.father = father return 'delete successfully' tmpNode = node.left while tmpNode.right != None: tmpNode = tmpNode.right tmpNode.right = node.right if node.right != None: node.right.father = tmpNode if father == None: self.root = node.left node.left.father = None elif father.left == node: father.left = node.left node.left.father = father else: father.right = node.left node.left.father = father node = None return 'delete successfully'
綜上，二叉搜尋樹程式碼
# encoding=utf-8 import queue class TreeNode(object): def __init__(self,val): self.value = val self.left = None self.right = None self.father = None class BST(object): def __init__(self,nodeList): self.root = None for node in nodeList: self.bfs_insert(node) def bfs_insert(self,node): father = None cur = self.root while cur != None: if cur.value == node.value: return -1 father = cur if node.value < cur.value: cur = cur.left else: cur = cur.right node.father = father if father == None: self.root = node elif node.value < father.value: father.left = node else: father.right = node def bfs(self): if self.root == None: return None retList = [] q = queue.Queue() q.put(self.root) while q.empty() is not True: node = q.get() retList.append(node.value) if node.left != None: q.put(node.left) if node.right != None: q.put(node.right) return retList def bfs_search(self,value): cur = self.root while cur != None: if cur.value == value: return cur elif cur.value < value: cur = cur.right else: cur = cur.left return None def bfs_delete(self,node): father = node.father if node.left == None: if father == None: self.root = node.right if node.right != None: node.right.father = None elif father.left == node: father.left = node.right if node.right != None: node.right.father = father else: father.right = node.right if node.right != None: node.right.father = father return 'delete successfully' tmpNode = node.left while tmpNode.right != None: tmpNode = tmpNode.right tmpNode.right = node.right if node.right != None: node.right.father = tmpNode if father == None: self.root = node.left node.left.father = None elif father.left == node: father.left = node.left node.left.father = father else: father.right = node.left node.left.father = father node = None return 'delete successfully' if __name__ == '__main__': varList = [24,34,5,4,8,23,45,35,28,6,29] nodeList = [TreeNode(var) for var in varList] bst = BST(nodeList) print (bst.bfs()) node = bst.bfs_search(34) bst.bfs_delete(node) print (bst.bfs())