一、樹的概念
詳情見 https://blog.csdn.net/little_limin/article/details/129845592
Python數(shù)據(jù)結構與算法-堆排序（NB組）—— 一、樹的基礎知識
二、樹的實例：模擬文件系統(tǒng)
1、樹的存儲
樹結構也是鏈式存儲的，與鏈表的結構相似，只是樹存在多個子節(jié)點，不是線性的，存在一堆多的情況。與雙鏈表相似，只不過鏈表節(jié)點對應的下一個節(jié)點只有一個，樹節(jié)點對應的孩子節(jié)點很多，需要用列表[]存儲。
（1）樹節(jié)點代碼實現(xiàn)
# 樹節(jié)點的類
class Node(): # 創(chuàng)建文件節(jié)點的類，及其屬性（父節(jié)點，孩子節(jié)點）
def __init__(self, name, type = "dir"): # 節(jié)點初始屬性,文件名，文件類型
self.name = name # 文件名
self.type = type # 文件類型
# 文件相互間關系
self.children = [] # 孩子節(jié)點，孩子節(jié)點可以有很多，所以是列表
self.parent = None # 父節(jié)點，父節(jié)點只有一個的，不一定需要有這個指向
# print測試
n = Node("hello") #父節(jié)點
n2 = Node("world") #孩子節(jié)點1
n3 = Node("yoyo") # 孩子節(jié)點2
# 孩子節(jié)點與父節(jié)點關聯(lián)
n.children.append(n2)
n.children.append(n3)
n2.parent = n
n3.parent = n
# 打印孩子節(jié)點的屬性
for nm in n.children:
print(nm.name)（2）輸出結果
world
yoyo2、模擬文件系統(tǒng)
（1）代碼實現(xiàn)
# 樹的實例：模擬文件系統(tǒng)
# 樹是鏈式存儲
class Node(): # 創(chuàng)建文件節(jié)點的類，及其屬性（父節(jié)點，孩子節(jié)點）
def __init__(self, name, type = "dir"): # 節(jié)點初始屬性,文件名，文件類型
self.name = name # 文件名
self.type = type # 文件類型
# 文件相互間關系
self.children = [] # 孩子節(jié)點，孩子節(jié)點可以有很多，所以是列表
self.parent = None # 父節(jié)點，父節(jié)點只有一個的，不一定需要有這個指向
def __repr__(self): # 內(nèi)置函數(shù)，返回值
return self.name # 返回名字
class FileSystemTree(): # 創(chuàng)建文件根目錄——數(shù)據(jù)結構（樹）
def __init__(self) -> None: # 樹的屬性
self.root = Node("/") # 樹的根節(jié)點，類似于鏈表的head結點
self.now = self.root # now指針，當前目錄
def mkdir(self,name): # 當前目錄創(chuàng)建文件
# 保證name以/結尾
if name[-1] != "/": # name這個字符串的最后一位不是斜杠
name += "/" # 在name的最后加上斜杠
new_dir = Node(name) # 創(chuàng)建文件節(jié)點
# 創(chuàng)建與當前文件夾的連接
self.now.children.append(new_dir)
new_dir.parent = self.now
def ls(self): # 展現(xiàn)當前目錄下的所有子目錄
return self.now.children # 返回子目錄列表
def cd(self,name): # 切換目錄(到子目錄)，支持向上返回
# 判斷是否為文件夾
if name[-1] != "/":
name += "/"
if name == "../": #當前目錄
self.now = self.now.parent # 返回目錄到上級
return
# 找到和name相同的文件
for child in self.now.children:
if child.name == name:
self.now = child # 切換目錄到child
return # 輸出
# 子目錄中無該文件夾，報錯
raise ValueError("invaild dir")
tree = FileSystemTree() # 創(chuàng)建樹
# 新建文件夾
tree.mkdir("Var/")
tree.mkdir("bin/")
tree.mkdir("usr/")
print(tree.ls()) # 展示當前子目錄
# 切換到子目錄
tree.cd("bin/")
tree.mkdir("python/") # 子目錄中創(chuàng)建文件夾
print(tree.ls()) # 展示當前子目錄
# 切換回上級目錄
tree.cd("../")
print(tree.ls()) # 展示當前子目錄（2）代碼結果
[Var/, bin/, usr/]
[python/]
[Var/, bin/, usr/]3、模擬文件代碼相關知識點
（1）__repr__ 和__str__ 內(nèi)置函數(shù)的用法和示例
1）__repr__的作用
輸出實例對象時，其內(nèi)容由__repr__的返回值決定。
class Test:
def __repr__(self) -> str:
return "hello"
t = Test()
print(t)輸出結果
hello可以看到，當打印實例對象的時候，打印的結果就是__repr__的返回值。如果不加定義__repr__則會默認使用object的__repr__函數(shù)，返回如下：
<__main__.Test object at 0x0000023573CF0700>2）__str__作用
與__repe__作用相同，只不過__str__要更猛一點，當你的類中同時重寫了__str__和__repr__后，那么當你打印實例對象的時候，python底層會優(yōu)先執(zhí)行實例對象.__str__()。
class Test:
def __repr__(self) -> str:
return "repr"
def __str__(self) -> str:
return "str"
t = Test()
print(t)輸出結果
str通過上面這個例子可以看到，輸出的是__str__的返回值（__repr__沒搶過__str__）。
（2）__str__和__repr__區(qū)別
在代碼編輯器中執(zhí)行print()函數(shù)，python優(yōu)先調(diào)用print(實例對象.__str__())；而當在運行終端直接敲實例對象的時候，python底層執(zhí)行的其實是實例對象.__repr__()。
示例1：在終端直接打印
>>> from text import Test
>>> t = Test()
>>> t
repr
>>> print(t)
str示例2：在編輯器print()
class Test:
def __repr__(self) -> str:
return "repr"
def __str__(self) -> str:
return "str"
t = Test()
print(t)輸出結果：
str（3）文件的相對路徑和絕對路徑
相對路徑從當前目錄到文件所在位置；
絕對路徑從根目錄開始到文件所在地。
（4）python的"./"、"../"和"/"路徑
./代表目前文件所在的目錄。
. ./代表目前文件的上一層目錄。
/代表根目錄。
三、二叉樹
1、概念
詳情見 https://blog.csdn.net/little_limin/article/details/129845592
Python數(shù)據(jù)結構與算法-堆排序（NB組）—— 二、二叉樹的基礎知識
2、二叉樹的存儲
（1）二叉樹的鏈式存儲
將二叉樹的節(jié)點定義為一個對象，節(jié)點之間通過類似鏈表的鏈接方式來連接。
（2）節(jié)點存儲代碼
class BiTreeNode: # 二叉樹
? ? def __init__(self,data): # data：節(jié)點數(shù)據(jù)
? ? ? ? self.data = data
? ? ? ? self.lchild = None # 左孩子
? ? ? ? self.rchild = None # 右孩子3、二叉樹代碼實現(xiàn)
# 二叉樹的簡單實現(xiàn)
class BiTreeNode(): # 二叉樹節(jié)點
def __init__(self,data) -> None:
self.data = data
self.lchild = None
self.rchild = None
# 定位節(jié)點
a = BiTreeNode("A")
b = BiTreeNode("B")
c = BiTreeNode("C")
d = BiTreeNode("D")
e = BiTreeNode("E")
f = BiTreeNode("F")
g = BiTreeNode("G")
# 節(jié)點關系鏈接
e.lchild = a
e.rchild = g
a.rchild = c
c.lchild = b
c.rchild = d
g.rchild = f
# 根節(jié)點
root = e
print(root.lchild.rchild.data)結果輸出
C4、二叉樹的遍歷
以上圖舉例，樹的遍歷如何實現(xiàn)。
（1）二叉樹遍歷方式
前序遍歷：EACBDGF 從根節(jié)點開始，先左孩子再右孩子。
中序遍歷：ABCDEFG
后序遍歷：BDCAFGE
層次遍歷：EAGCFBD
（2）前序遍歷代碼實現(xiàn)
在二叉樹代碼實現(xiàn)的基礎代碼上，增加以下代碼，以下代碼為前序遍歷主代碼。
# 根節(jié)點
root = e
# 前序遍歷
def pre_order(root):
if root: # root不為空
print(root.data, end = ',')
pre_order(root.lchild) # 訪問左孩子
pre_order(root.rchild) # 訪問右孩子
pre_order(e) # 從e開始前序遍歷輸出結果
E,A,C,B,D,G,F,（3）中序遍歷代碼實現(xiàn)
中序遍歷可以理解為將樹結構“拍扁”，與前序遍歷的區(qū)別僅在print打印的位置不同。
# 中序遍歷
def in_order(root):
if root: # root不為空，遞歸結束條件
in_order(root.lchild) # 訪問左孩子
print(root.data, end = ',') # 打印本身
in_order(root.rchild) # 訪問右孩子
in_order(root) # 從e開始前序遍歷輸出結果
A,B,C,D,E,G,F,遞歸原理
s1.首先，運行E的左孩子所在的子樹，打印E，再運行E的右孩子所在的子樹。
s2.進入E的左孩子的子樹，A沒有左孩子，打印A，運行A的右孩子。
s3.進入A的右孩子的子樹，先運行C的左孩子，打印C，運行C的右孩子。
s4.進入C的左孩子的子樹，打印了B；進入C的右孩子的子樹，打印了D。
s5，進入E的右孩子的子樹，依舊同以上步驟，得到G和F。
（4）后序遍歷
# 后序遍歷
def post_order(root):
if root: # root不為空，遞歸結束條件
post_order(root.lchild) # 訪問左孩子
post_order(root.rchild) # 訪問右孩子
print(root.data, end = ',') # 打印本身
post_order(root) # 從e開始前序遍歷輸出結果
B,D,C,A,F,G,E,遞歸原理
運行的順序從左往右，與中序遍歷的原理類似。先運行左孩子所在子樹，再運行右孩子所在子樹，最后才打印本身。
（5）層次遍歷
# 層次遍歷——廣度優(yōu)先搜索
from collections import deque # 隊列模塊
def level_order(root):
queue = deque() # 新建隊列
queue.append(root) # 根節(jié)點入隊
while len(queue) > 0: # 隊列不空
node = queue.popleft() # 節(jié)點出隊
print(node.data, end = ',') # 得到節(jié)點的值
if node.lchild: # 節(jié)點的左孩子存在
queue.append(node.lchild) # 左孩子進入隊列
if node.rchild: # 節(jié)點的右孩子存在
queue.append(node.rchild) # 右孩子入隊
level_order(root)輸出結果
E,A,G,C,F,B,D,代碼實現(xiàn)原理
使用單向隊列的性質(zhì)，節(jié)點出隊時，其對應的孩子節(jié)點入隊。例如（以本節(jié)遍歷二叉樹為例）：
[E]:根節(jié)點入隊
E,[A,G]:E出隊，對應的左孩子A和右孩子入隊
E,A,[G,C]:A出隊，A的右孩子C入隊
E,A,G,[C,F]:G出隊，G的右孩子F入隊
E,A,G,C,[F,B,D]:C出隊，C的左孩子B，右孩子D出隊
E,A,G,C,F,[B,D]:F出隊，F(xiàn)沒有孩子節(jié)點
E,A,G,C,F,B,[D]:B出隊，B沒有孩子節(jié)點
E,A,G,C,F,B,D,[]:D出隊，D沒有孩子節(jié)點,隊列為空，結束循環(huán)。
三、二叉搜索樹
1、概念
二叉搜索樹是一棵二叉樹且滿足性質(zhì)：設x是二叉樹的一個節(jié)點。如果y是x左子樹的一個節(jié)點，那么y.key 
x.key;如果y是x右子樹的一個節(jié)點，那么y.key 
x.key。
如下圖為一棵二叉搜索樹：
二叉搜索樹的操作：查詢、插入、刪除
查詢和插入的時間復雜度都為O(logn),刪除操作較為復雜后面會具體分析。
2、二叉搜索樹：插入
（1）遞歸實現(xiàn)插入
當插入值小于當前節(jié)點的值，當前節(jié)點的左孩子（左孩子子樹）是插入值的節(jié)點；當插入值大于當前節(jié)點的值，當前節(jié)點的右孩子（右孩子子樹）是插入值的節(jié)點；若該值插入的位置不存在節(jié)點或該值與當前節(jié)點值相同，則創(chuàng)建新的節(jié)點或覆蓋該節(jié)點。
# 二叉搜索樹的用遞歸寫插入函數(shù)
class BiTreeNode(): # 二叉樹節(jié)點
def __init__(self, data) -> None: # 屬性
self.data = data # 樹的值
self.lchild = None # 左孩子
self.rchild = None # 右孩子
self.parent = None # 父節(jié)點
# 二叉搜索樹 binary search tree
class BST():
def __init__(self): # 創(chuàng)建空樹
self.root = None # 根節(jié)點為空
# 遞歸插入
def insert(self, node, val): # node是指二叉樹中當前指向的節(jié)點，初始一般為根節(jié)點，val是指插入的值
if not node or node.data == val: # 空樹或節(jié)點的值與插入的值相同
node = BiTreeNode(val) # 創(chuàng)建一個節(jié)點插入到樹中（最后一步）或者是插入的值的節(jié)點直接與原節(jié)點相重合
elif val < node.data: # 插入的值小于當前節(jié)點的值
# 往當前節(jié)點的左邊插,當前節(jié)點的也就往左孩子找
node.lchild = self.insert(node.lchild,val) # 左孩子為根節(jié)點的子樹上，node.lchild(當前點的左孩子) = node(插入的節(jié)點)
node.lchild.parent = node # 與父節(jié)點的連接
else: # val > node.data
node.rchild = self.insert(node.rchild,val) # 當前節(jié)點的右孩子是插入的節(jié)點
node.rchild.parent = node
return node # 返回
# 前序遍歷
def pre_order(self, root):
if root: # root不為空
print(root.data, end = ',')
self.pre_order(root.lchild) # 訪問左孩子
self.pre_order(root.rchild) # 訪問右孩子
tree = BST()
node = BiTreeNode(10) # 樹的根節(jié)點
# 插入數(shù)值
tree.insert(node,5)
tree.insert(node,19)
tree.insert(node,8)
tree.insert(node,3)
tree.pre_order(node)輸出結果
10,5,3,8,19,（2）普通方式實現(xiàn)插入
# 二叉搜索樹普通辦法寫插入函數(shù)
class BiTreeNode(): # 二叉樹節(jié)點
def __init__(self, data) -> None: # 屬性
self.data = data # 樹的值
self.lchild = None # 左孩子
self.rchild = None # 右孩子
self.parent = None # 父節(jié)點
# 二叉搜索樹 binary search tree
class BST():
def __init__(self, li=None): # 創(chuàng)建樹
self.root = None # 根節(jié)點為空
# 創(chuàng)建二叉搜索樹
if li:
for val in li:
self.insert_no_dec(val) # 循環(huán)插入值
def insert_no_dec(self,val): # 非遞歸
p = self.root # 創(chuàng)建指針p，p起始指向根節(jié)點
if not p: # p指向節(jié)點為空，空樹，
self.root = BiTreeNode(val) # 創(chuàng)建根節(jié)點
return
while True: # 循環(huán)
if val < p.data: # 插入值小于p指向節(jié)點的值
if p.lchild: # 左孩子節(jié)點存在
p = p.lchild # 指針移動至新的節(jié)點
else: # 左孩子不存在
p.lchild = BiTreeNode(val) # 插入值
p.lchild.parent = p # 連接父節(jié)點
return # 結束循環(huán)，返回
elif val > p.data: # 插入值大于p指向節(jié)點的值
if p.rchild: # 右孩子存在
p = p.rchild # 指針移動至新節(jié)點
else: # 右孩子不存在
p.rchild = BiTreeNode(val) # 插入值
p.rchild.parent = p # 連接父節(jié)點
return # 結束循環(huán)，返回
else: # val == p.data
return # 不用插入
# 前序遍歷
def pre_order(self,root):
if root: # root不為空
print(root.data, end = ',')
self.pre_order(root.lchild) # 訪問左孩子
self.pre_order(root.rchild) # 訪問右孩子
# 中序遍歷
def in_order(self, root):
if root: # root不為空，遞歸結束條件
self.in_order(root.lchild) # 訪問左孩子
print(root.data, end = ',') # 打印本身
self.in_order(root.rchild) # 訪問右孩子
# 后序遍歷
def post_order(self, root):
if root: # root不為空，遞歸結束條件
self.post_order(root.lchild) # 訪問左孩子
self.post_order(root.rchild) # 訪問右孩子
print(root.data, end = ',') # 打印本身
tree = BST([4,6,7,9,2,1,3,5,8]) # 對象實例化
# 遍歷二叉樹
tree.pre_order(tree.root)
print("")
tree.in_order(tree.root)
print("")
tree.post_order(tree.root)輸出結果：
4,2,1,3,6,5,7,9,8,
1,2,3,4,5,6,7,8,9,
1,3,2,5,8,9,7,6,4,說明：中序遍歷的二叉搜索樹一定是升序輸出的
3、二叉搜索樹：查詢
查詢函數(shù)的原理與插入函數(shù)的原理基本一致。
import random
class BiTreeNode(): # 二叉樹節(jié)點
def __init__(self, data) -> None: # 屬性
self.data = data # 樹的值
self.lchild = None # 左孩子
self.rchild = None # 右孩子
self.parent = None # 父節(jié)點
# 二叉搜索樹 binary search tree
class BST():
def __init__(self, li=None): # 創(chuàng)建樹
self.root = None # 根節(jié)點為空
# 創(chuàng)建二叉搜索樹
if li:
for val in li:
self.insert_no_dec(val) # 循環(huán)插入值
def insert_no_dec(self,val): # 非遞歸插入
p = self.root # 創(chuàng)建指針p，p起始指向根節(jié)點
if not p: # p指向節(jié)點為空，空樹，
self.root = BiTreeNode(val) # 創(chuàng)建根節(jié)點
return
while True: # 循環(huán)
if val < p.data: # 插入值小于p指向節(jié)點的值
if p.lchild: # 左孩子節(jié)點存在
p = p.lchild # 指針移動至新的節(jié)點
else: # 左孩子不存在
p.lchild = BiTreeNode(val) # 插入值
p.lchild.parent = p # 連接父節(jié)點
return # 結束循環(huán)，返回
elif val > p.data: # 插入值大于p指向節(jié)點的值
if p.rchild: # 右孩子存在
p = p.rchild # 指針移動至新節(jié)點
else: # 右孩子不存在
p.rchild = BiTreeNode(val) # 插入值
p.rchild.parent = p # 連接父節(jié)點
return # 結束循環(huán)，返回
else: # val == p.data
return # 不用插入
def query(self, node, val): # 遞歸寫查詢
if not node: # 節(jié)點不存在
return None # 返回none
elif val > node.data: # 值大于當前節(jié)點的值，往右子樹找
node = self.query(node.rchild, val) # 變量node是返回的node的賦值
elif val < node.data: # 值小于當前節(jié)點的值，往左子樹找
node = self.query(node.lchild, val)
else: # val == node.data
node = node # 值相等時返回節(jié)點
return node
def query_no_rec(self, val): # 非遞歸查詢
p = self.root # p指針初始指向根節(jié)點
while p: # 不是空樹
if val < p.data: # 值小于當前節(jié)點，往左找
p = p.lchild # p指針下移
elif val > p.data: # 值大于當前節(jié)點,往右找
p = p.rchild # p指針往右下移
else: # val == p.data
return p # 退出循環(huán)
return None
li = list(range(0,10,2)) # 0-9的偶數(shù)
random.shuffle(li)
tree = BST(li) # 創(chuàng)建樹
node = tree.root
# print(node.data)
print(tree.query(node, 5)) # 遞歸
print(tree.query_no_rec(4)) # 非遞歸輸出結果
None
<__main__.BiTreeNode object at 0x00000170A1C1C6A0>4、二叉搜索樹：刪除
（1）刪除操作原理
二叉搜索樹的刪除與雙向鏈表的刪除極為相似。
1）要刪除的節(jié)點是葉子節(jié)點：直接刪除。node.parent.lchild 或者 node.parent,rchild = None
2）要刪除的節(jié)點只有一個孩子：將此節(jié)點的父親與孩子連接，然后刪除該節(jié)點。如果刪除的節(jié)點是根節(jié)點，則需要調(diào)整子樹節(jié)點的位置。
3）要刪除的節(jié)點有兩個孩子：將其右子樹的值最小的節(jié)點（該節(jié)點最多有一個右孩子，也可能就是葉子節(jié)點），該點一定為右子樹的各節(jié)點的最后一個左孩子，找到該節(jié)點并替換當前節(jié)點的值，再刪除該接節(jié)點文章來源：http://www.zghlxwxcb.cn/news/detail-414411.html
（2）刪除操作代碼實現(xiàn)
# 二叉搜索樹——刪除
class BiTreeNode(): # 二叉樹節(jié)點
def __init__(self, data) -> None: # 屬性
self.data = data # 樹的值
self.lchild = None # 左孩子
self.rchild = None # 右孩子
self.parent = None # 父節(jié)點
# 二叉搜索樹 binary search tree
class BST():
def __init__(self, li=None): # 創(chuàng)建樹
self.root = None # 根節(jié)點為空
# 創(chuàng)建二叉搜索樹
if li:
for val in li:
self.insert_no_dec(val) # 循環(huán)插入值
def insert_no_dec(self,val): # 非遞歸插入
p = self.root # 創(chuàng)建指針p，p起始指向根節(jié)點
if not p: # p指向節(jié)點為空，空樹，
self.root = BiTreeNode(val) # 創(chuàng)建根節(jié)點
return
while True: # 循環(huán)
if val < p.data: # 插入值小于p指向節(jié)點的值
if p.lchild: # 左孩子節(jié)點存在
p = p.lchild # 指針移動至新的節(jié)點
else: # 左孩子不存在
p.lchild = BiTreeNode(val) # 插入值
p.lchild.parent = p # 連接父節(jié)點
return # 結束循環(huán)，返回
elif val > p.data: # 插入值大于p指向節(jié)點的值
if p.rchild: # 右孩子存在
p = p.rchild # 指針移動至新節(jié)點
else: # 右孩子不存在
p.rchild = BiTreeNode(val) # 插入值
p.rchild.parent = p # 連接父節(jié)點
return # 結束循環(huán)，返回
else: # val == p.data
return # 不用插入
def query(self, node, val): # 遞歸寫查詢
if not node: # 節(jié)點不存在
return None # 返回none
elif val > node.data: # 值大于當前節(jié)點的值，往右子樹找
node = self.query(node.rchild, val) # 變量node是返回的node的賦值
elif val < node.data: # 值小于當前節(jié)點的值，往左子樹找
node = self.query(node.lchild, val)
else: # val == node.data
node = node # 值相等時返回節(jié)點
return node
def query_no_rec(self, val): # 非遞歸查詢
p = self.root # p指針初始指向根節(jié)點
while p: # 不是空樹
if val < p.data: # 值小于當前節(jié)點，往左找
p = p.lchild # p指針下移
elif val > p.data: # 值大于當前節(jié)點,往右找
p = p.rchild # p指針往右下移
else: # val == p.data
return p # 退出循環(huán)
return None
# 中序遍歷
def in_order(self,root):
if root: # root不為空，遞歸結束條件
self.in_order(root.lchild) # 訪問左孩子
print(root.data, end = ',') # 打印本身
self.in_order(root.rchild) # 訪問右孩子
def __remove_node_1(self, node): # 情況1：葉子節(jié)點
# 判斷是否為根節(jié)點
if not node.parent:
self.root = None # 根節(jié)點為None，即刪除根節(jié)點
if node == node.parent.lchild: # node為左孩子
node.parent.lchild = None
else: # node為右孩子
node.parent.rchild = None
def __remove_node_21(self,node): # 情況2.1：只有一個左孩子
if not node.parent: # 根節(jié)點
self.root = node.lchild # 根節(jié)點為node的左孩子
node.lchild.parent = None # 左孩子的父親為空
elif node == node.parent.lchild: # node是父親的左孩子
node.parent.lchild = node.lchild # node父親的左孩子變?yōu)閚ode的左孩子
node.lchild.parent = node.parent # node左孩子的父親變?yōu)閚ode的父親
else: # node是父親的右孩子
node.parent.rchild = node.lchild # node父親的右孩子變?yōu)閚ode的左孩子
node.lchild.parent = node.parent # node左孩子的父親變?yōu)閚ode的父親
def __remove_node_22(self,node): # 情況2.2：只有一個右孩子
if not node.parent: # 根節(jié)點
self.root = node.rchild # 根節(jié)點為node的右孩子
node.rchild.parent = None # 根節(jié)點沒有父節(jié)點
elif node == node.parent.lchild: # node是父親的左孩子
node.parent.lchild = node.rchild # node父親的左孩子變?yōu)閚ode的右孩子
node.rchild.parent = node.parent # node右孩子的父親變?yōu)閚ode的父親
else: # node為父親的右孩子
node.parent.rchild = node.rchild # node父親的右孩子變?yōu)閚ode的右孩子
node.rchild.parent = node.parent # node右孩子的父親變?yōu)閚ode的父親
def delete(self,val): # 刪除操作（合并）
if self.root: # 不是空樹
node = self.query_no_rec(val) # 找到該節(jié)點 這步錯了
if not node: # node不存在
return False
if not node.lchild and not node.rchild: # 葉子節(jié)點
self.__remove_node_1(node) # 情況1
elif not node.rchild: # node只有左孩子
self.__remove_node_21(node) # 情況2.1
elif not node.lchild: # node只有右孩子
self.__remove_node_22(node) # 情況2.2
else: # 情況3 即有左孩子又有右孩子
# 找min_node，右子樹的最小節(jié)點
min_node = node.rchild # min_node在右子樹上
while min_node.lchild: # 直到?jīng)]有左孩子
min_node = min_node.lchild # min_node一直往左孩子移動，尋找
node.data = min_node.data # 互換兩者的值
# 刪除min_node
if min_node.rchild: # 只有右孩子
self.__remove_node_22(min_node)
else: # min_node為葉子節(jié)點
self.__remove_node_1(min_node)
tree = BST([1,4,2,5,3,8,6,9,7])
tree.in_order(tree.root)
print("")
# 刪除值
tree.delete(4)
tree.delete(8)
tree.in_order(tree.root)結果輸出文章來源地址http://www.zghlxwxcb.cn/news/detail-414411.html
1,2,3,4,5,6,7,8,9,
1,2,3,5,6,7,9,到了這里，關于Python數(shù)據(jù)結構與算法-樹的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
