10.1二叉樹
10.1.1為什么需要樹這種數(shù)據(jù)結構
1)數(shù)組存儲方式的分析：
優(yōu)點：通過下標方式訪問元素，速度快。對于有序數(shù)組，還可使用二分查找提高檢索速度。
缺點：如果要檢索具體某個值，或者插入值(按一定順序)會整體移動，效率較低
示意圖：
2)鏈式存儲方式的分析
優(yōu)點：在一定程度上對數(shù)組存儲方式有優(yōu)化(比如：插入一個數(shù)值節(jié)點，只需要將插入節(jié)點，鏈接到鏈表中即可，刪除效率也很好)。
缺點：在進行檢索時，效率仍然較低，比如(檢索某個值，需要從頭節(jié)點開始遍歷)
示意圖：
3)樹存儲方式的分析
樹存儲能提高數(shù)據(jù)存儲，讀取的效率,比如利用二叉排序樹(BinarySortTree)，既可以保證數(shù)據(jù)的檢索速度，同時也可以保證數(shù)據(jù)的插入，刪除，修改的速度。
示意圖：
樹的常用術語(結合示意圖理解):
1)節(jié)點
2)根節(jié)點
3)父節(jié)點
4)子節(jié)點
5)葉子節(jié)點(沒有子節(jié)點的節(jié)點)
6)節(jié)點的權(節(jié)點值)
7)路徑(從root節(jié)點找到該節(jié)點的路線)
8)層
9)子樹
10)樹的高度(最大層數(shù))
11)森林:多顆子樹構成森林
10.1.2二叉樹的概念
1)樹有很多種，每個節(jié)點最多只能有兩個子節(jié)點的一種形式稱為二叉樹。
2)二叉樹的子節(jié)點分為左節(jié)點和右節(jié)點
3)示意圖：
4)如果該二叉樹的所有葉子節(jié)點都在最后一層，并且結點總數(shù)=2^n-1,n為層數(shù)，則我們稱為滿二叉樹。
5)如果該二叉樹的所有葉子節(jié)點都在最后一層或者倒數(shù)第二層，而且最后一層的葉子節(jié)點在左邊連續(xù)，倒數(shù)第二層的葉子節(jié)點在右邊連續(xù)，我們稱為完全二叉樹
10.1.3二叉樹遍歷的說明
1)前序遍歷:先輸出父節(jié)點，再遍歷左子樹和右子樹
2)中序遍歷:先遍歷左子樹，再輸出父節(jié)點，再遍歷右子樹
3)后序遍歷:先遍歷左子樹，再遍歷右子樹，最后輸出父節(jié)點
10.1.4二叉樹遍歷應用實例(前序,中序,后序)
應用實例的說明和思路：
10.1.5二叉樹-查找指定節(jié)點
要求:
1)請編寫前序查找，中序查找和后序查找的方法。
2)并分別使用三種查找方式，查找heroNO=5的節(jié)點
3)并分析各種查找方式，分別比較了多少次
4)示意圖：
10.1.6二叉樹-刪除節(jié)點
要求（規(guī)定）：
1)如果刪除的節(jié)點是葉子節(jié)點，則刪除該節(jié)點
2)如果刪除的節(jié)點是非葉子節(jié)點，則刪除該子樹.
3)示意圖：
10.1.5二叉樹的遍歷、查找、刪除節(jié)點的所有代碼：
class HeroNode():
def __init__(self,id,name):
self.id = id
self.name = name
self.left = None
self.right = None
def preOrder(self):
#先輸出父結點
print(self.id,self.name)
#遞歸向左子樹前序遍歷
if self.left != None:
self.left.preOrder()
#遞歸向右子樹前序遍歷
if self.right != None:
self.right.preOrder()
def infixOrder(self):
if self.left != None:
self.left.infixOrder()
print(self.id,self.name)
if self.right != None:
self.right.infixOrder()
def postOrder(self):
if self.left != None:
self.left.postOrder()
if self.right != None:
self.right.postOrder()
print(self.id,self.name)
def preOrderSearched(self,id):
# 1.先判斷當前結點的no是否等于要查找的
# 2.如果是相等，則返回當前結點
if self.id == id:
return self
print("compare",self.id)
# 3.如果不等，則判斷當前結點的左子節(jié)點是否為空，如果不為空，則遞歸前序查找，
# 這里創(chuàng)建一個對象用來接收查找的返回值
self.heronode = HeroNode(None,None)
if self.left != None:
print("left")
self.heronode = self.left.preOrderSearched(id)
# 4.如果左遞歸前序查找，找到結點，則返回這個對象，注意這里不能直接返回self，因為self是只當前節(jié)點，而不是self.heronode這個對象
if self.heronode.id != None:
return self.heronode
# 5.否->繼續(xù)判斷，當前的結點的右子節(jié)點是否為空，如果不空，則繼續(xù)向右遞歸前序查找.
if self.right != None:
print("right")
self.heronode = self.right.preOrderSearched(id)
# 6.不管向右遞歸前序查找有沒有找到直接返回self.heronode對象即可。
return self.heronode
def infixOrderSearched(self,id):
self.heronode = HeroNode(None,None)
if self.left != None:
print("left")
self.heronode = self.left.infixOrderSearched(id)
if self.heronode.id != None:
return self.heronode
if self.id == id:
return self
print("compare",self.id)
if self.right != None:
print("right")
self.heronode = self.right.infixOrderSearched(id)
return self.heronode
def postOrderSearched(self,id):
self.heronode = HeroNode(None,None)
if self.left != None:
print("left")
self.heronode = self.left.postOrderSearched(id)
if self.heronode.id != None:
return self.heronode
if self.right != None:
print("right")
self.heronode = self.right.postOrderSearched(id)
if self.heronode.id != None:
return self.heronode
if self.id == id:
return self
print("compare",self.id)
return self.heronode
def perdelete(self,id):
#說明：
#1.本刪除方法，是按照前序查找的形式進行查找刪除的
#2.規(guī)定
# //1.如果刪除的節(jié)點是葉子節(jié)點，則刪除該節(jié)點
# //2.如果刪除的節(jié)點是非葉子節(jié)點，則刪除該子樹
#實現(xiàn)過程：
#1.因為我們的二叉樹是單向的，所以我們是判斷當前結點的子結點是否需要刪除結點，而不能去判斷當前這個結點是不是需要刪除結點.因此用self.left self.right
#2.如果當前結點的左子結點不為空，并且左子結點就是要刪除結點，就將this.left=null;并且就返回(結束遞歸刪除)
if self.left != None and self.left.id == id:
self.left = None
return
#3.如果當前結點的右子結點不為空，并且右子結點就是要刪除結點，就將this.right=null;并且就返回(結束遞歸刪除)
if self.right != None and self.right.id == id:
self.right = None
return
#4.如果第2和第3步沒有刪除結點，那么我們就需要向左子樹進行遞歸刪除
if self.left != None:
self.left.perdelete(id)
#5.如果第4步也沒有刪除結點，則應當向右子樹進行遞歸刪除.
if self.right != None:
self.right.perdelete(id)
return
class BinaryTree():
def __init__(self,id,name):
self.id = id
self.name = name
self.headnode = HeroNode(self.id,self.name)
def infixOrder(self):
if self.headnode != None:
self.headnode.infixOrder()
else:
print("None")
def postOrder(self):
if self.headnode != None:
self.headnode.postOrder()
else:
print("None")
def preOrder(self):
if self.headnode != None:
self.headnode.preOrder()
else:
print("None")
def preOrderSearched(self,id):
self.id = id
if self.headnode != None:
return self.headnode.preOrderSearched(id)
else:
return None
def infixOrderSearched(self,id):
self.id = id
if self.headnode != None:
return self.headnode.infixOrderSearched(id)
else:
return None
def postOrderSearched(self,id):
self.id = id
if self.headnode != None:
return self.headnode.postOrderSearched(id)
else:
return None
def perdelete(self,id):
#在這里先對root結點進行判斷，若是則置空，不是再調用root結點的perdelete方法
self.id = id
if self.headnode != None and self.headnode.id == id:
self.headnode = None
return
self.headnode.perdelete(self.id)
#這里手動創(chuàng)建二叉樹并做出相應連接、后續(xù)會寫代碼按照一定規(guī)則的形式來創(chuàng)建二叉樹
binary = BinaryTree(0,'q')
node1 = HeroNode(1,'w')
node2 = HeroNode(2,'e')
node3 = HeroNode(3,'r')
node4 = HeroNode(4,'t')
node5 = HeroNode(5,'y')
node6 = HeroNode(6,'u')
node7 = HeroNode(7,'I')
binary.headnode.left = node1
binary.headnode.right = node2
node2.left = node3
node2.right = node4
node3.left = node5
node3.right = node6
node4.right = node7
#前序中序后序遍歷
binary.preOrder()
binary.infixOrder()
binary.postOrder()
#前序中序后序查找
# persearch = binary.preOrderSearched(6)
# if persearch != None:
# print(persearch.id, persearch.name)
# print("--------------------------------")
# persearch = binary.infixOrderSearched(6)
# if persearch != None:
# print(persearch.id, persearch.name)
# print("--------------------------------")
# persearch = binary.postOrderSearched(6)
# if persearch != None:
# print(persearch.id, persearch.name)
#刪除
binary.preOrder()
print("--------------------------------")
binary.perdelete(7)
binary.preOrder()
10.2順序存儲二叉樹
10.2.1順序存儲二叉樹的概念
從數(shù)據(jù)存儲來看，數(shù)組存儲方式和樹的存儲方式可以相互轉換，即數(shù)組可以轉換成樹，樹也可以轉換成數(shù)組，示意圖：
要求:
1)如二叉樹的7個節(jié)點，要求以數(shù)組的方式來存放arr:[1,2,3,4,5,6,6]
2)在遍歷數(shù)組arr時，仍然可以以前序遍歷，中序遍歷和后序遍歷的方式完成結點的遍歷
順序存儲二叉樹的特點:
1)順序二叉樹通常只考慮完全二叉樹
溫習概念：
2)第n個元素的左子節(jié)點為2n+1
3)第n個元素的右子節(jié)點為2n+2
4)第n個元素的父節(jié)點為(n-1)/2
5)n:表示二叉樹中的第幾個元素(從0開始編號如圖所示)
10.2.2順序存儲二叉樹遍歷
需求:
給你一個數(shù)組{1,2,3,4,5,6,7}，要求以二叉樹前序遍歷的方式進行遍歷。前序遍歷的結果應當為1,2,4,5,3,6,7
代碼實現(xiàn):
class ArrayBinaryTree():
def __init__(self,array):
self.array = array
self.length = len(self.array)
def perOrder(self,index):
if self.length == 0:
return
print(self.array[index])
if 2*index+1<self.length:
self.perOrder(2*index+1)
if 2*index+2<self.length:
self.perOrder(2*index+2)
a = [1,2,3,4,5,6,7]
A = ArrayBinaryTree(a)
A.perOrder(0)
10.3線索化二叉樹
10.3.1 問題提出：
將數(shù)列{1,3,6,8,10,14}構建成一顆二叉樹，如圖所示：
問題分析:
1)當我們對上面的二叉樹進行中序遍歷時，數(shù)列為{8,3,10,1,6,14}
2)但是6,8,10,14這幾個節(jié)點的左右指針，并沒有完全的利用上.
3)如果我們希望充分的利用各個節(jié)點的左右指針，讓各個節(jié)點可以指向自己的前后節(jié)點,怎么辦?
4)解決方案-線索二叉樹
10.3.2線索二叉樹基本介紹
1)n個結點的二叉鏈表中含有n+1【公式2n-(n-1)=n+1】個空指針域。利用二叉鏈表中的空指針域，存放指向該結點在某種遍歷次序下的前驅和后繼結點的指針（這種附加的指針稱為"線索"）
2)這種加上了線索的二叉鏈表稱為線索鏈表，相應的二叉樹稱為線索二叉樹(ThreadedBinaryTree)。根據(jù)線索性質的不同，線索二叉樹可分為前序線索二叉樹、中序線索二叉樹和后序線索二叉樹三種
3)一個結點的前一個結點，稱為前驅結點
4)一個結點的后一個結點，稱為后繼結點
10.3.3線索二叉樹應用案例
說明：將下面的二叉樹，進行中序線索二叉樹。中序遍歷的數(shù)列為{8,3,10,1,14,6}
思路分析:中序遍歷的結果：{8,3,10,1,14,6}
說明:
一、中序線索化二叉樹如上圖所示：
首先第一個葉子結點無前驅結點，最后一個葉子結點無后繼結點，
其次如值為10的結點，則其前驅結點值為3，后繼結點值為1，如圖紅線所示
二、當線索化二叉樹后，Node節(jié)點的屬性left和right，有如下情況:
1)left指向的是左子樹，也可能是指向的前驅節(jié)點.
比如①節(jié)點left指向的左子樹,而⑩節(jié)點的left指向的就是前驅節(jié)點.
2)right指向的是右子樹，也可能是指向后繼節(jié)點.
比如①節(jié)點right指向的是右子樹，而⑩節(jié)點的right指向的是后繼節(jié)點.
10.3.4遍歷線索化二叉樹
1)說明：對前面的中序線索化的二叉樹，進行遍歷
2)分析：因為線索化后，各個結點指向有變化，因此原來的遍歷方式不能使用，這時需要使用新的方式遍歷線索化二叉樹，各個節(jié)點可以通過線型方式遍歷，因此無需使用遞歸方式，這樣也提高了遍歷的效率。遍歷的次序應當和中序遍歷保持一致。
代碼實現(xiàn)
class HeroNode():
def __init__(self,id,name):
self.id = id
self.name = name
self.left = None
self.right = None
self.lefttype = 0
self.righttype = 0
class BinaryTree():
def __init__(self):
self.pre = HeroNode(None,None)
self.pre.right = None
def threaded(self,node):
#這一個程序還算好寫的，但是有兩個地方困擾了我一天，我已經差點要放棄了，已經在簡書里用別人的代碼，寫著我遇到了xxx的問題，想找人幫忙解決
#可是我寫著寫著的時候，突然想到，嗯？為什么會有這個錯誤？為什么（我在線索化最左邊葉子結點的left結點的時候由于為空所以應該返回到最左邊的葉子結點， 可以是我return后，葉子結點丟了，當前結點變?yōu)榭樟耍? #然后我就在想return空的原因，那不就是因為我self.node = node 我在self.threaded(node.left) 這里調用的時候，此時的node.left為None，當然你再
#self.node = node，它也就為空了，那么解決辦法就是不要這句代碼。
# self.node = node
#node: 就是當前需要線索化的結點
if node == None:
return
# 先線索化左子樹
self.threaded(node.left)
# 線索化當前結點
# 處理當前結點的前驅結點
if node.left == None:
node.left = self.pre
node.lefttype = 1
# 處理當前結點的后繼結點
if self.pre.id != None and self.pre.right == None:
self.pre.right = node
self.pre.righttype = 1
#第二個錯誤是下面這句代碼。所以導致了我整個程序一直有bug，這個問題修復是看別人的代碼，才修復好的，慚愧
#node.pre = node
self.pre = node
# 線索化右子樹
self.threaded(node.right)
# 中序遍歷線索化二叉樹
def threaded_in_order(self, node):
#用一個循環(huán)去判斷，其實這里能獲得的node== None: 的話只有兩種情況。一種是node3.left 一種是node6.right, 這里很巧妙
#第二個None用于找到結束位置也就是node6
while node != None:
#這里用lefttype ==0: 找到第一個 lefttype ==1 的結點也就是3作為開始結點,并且這個可以找到每個小分支最左邊結點這個很重要！要不然有的結點就漏了
while node.lefttype ==0:
node = node.left
#其實從這里開始就是不斷的輸出當前結點，并 node = node.right 但是不能直接這么兩句話寫了，不然會造成死循環(huán)，因為當運行到最后一句代前
#正常此時 的 node.righttype以及node.lefttype 都為0 因此加上最后一句代碼，起了順水推舟的作用，這樣就跳開了上面的while循環(huán)
print(node.id)
while(node.righttype == 1):
node = node.right
print(node.id)
node = node.right
#這里手動創(chuàng)建二叉樹并做出相應連接、后續(xù)會寫代碼按照一定規(guī)則的形式來創(chuàng)建二叉樹
node0 = HeroNode(0,'q')
node1 = HeroNode(1,'w')
node2 = HeroNode(2,'e')
node3 = HeroNode(3,'r')
node4 = HeroNode(4,'t')
node5 = HeroNode(5,'y')
node6 = HeroNode(6,'u')
node7 = HeroNode(7,'I')
binary = BinaryTree()
node0.left = node1
node0.right = node2
node1.left = node3
node1.right = node4
node2.left = node5
node2.right = node6
binary.threaded(node0)
binary.threaded_in_order(node0)
10.4樹結構的實際應用
11.1 堆排序
詳見：
http://www.itdecent.cn/p/ff61c524f5cf
11.2 赫夫曼樹
11.2.1基本介紹
1)給定n個權值作為n個葉子結點，構造一棵二叉樹，若該樹的帶權路徑長度(wpl)達到最小，稱這樣的二叉樹為最優(yōu)二叉樹，也稱為哈夫曼樹(HuffmanTree),還有的書翻譯為霍夫曼樹。
2)赫夫曼樹是帶權路徑長度最短的樹，權值較大的結點離根較近
11.2.2赫夫曼樹幾個重要概念和舉例說明
1)路徑和路徑長度：在一棵樹中，從一個結點往下可以達到的孩子或孫子結點之間的通路，稱為路徑。通路中分支的數(shù)目稱為路徑長度。若規(guī)定根結點的層數(shù)為1，則從根結點到第L層結點的路徑長度為L-1
2)結點的權及帶權路徑長度：若將樹中結點賦給一個有著某種含義的數(shù)值，則這個數(shù)值稱為該結點的權。結點的帶權路徑長度為：從根結點到該結點之間的路徑長度與該結點的權的乘積
3)樹的帶權路徑長度：樹的帶權路徑長度規(guī)定為所有葉子結點的帶權路徑長度之和，記為WPL(weightedpathlength),權值越大的結點離根結點越近的二叉樹才是最優(yōu)二叉樹。
4)WPL最小的就是霍夫曼樹
11.2.3霍夫曼樹創(chuàng)建思路
首先，我們給定任一字符串如“Hello world，i love python”
然后會生成這樣一些數(shù)據(jù)：
sourceData = [('H', 1), ('e', 2), ('l', 4), ('o', 4), (' ', 3), ('w', 1), ('r', 1), ('d', 1), ('，', 1), ('i', 1), ('v', 1), ('p', 1), ('y', 1), ('t', 1), ('h', 1), ('n', 1)]
每一個數(shù)據(jù)項是一個元組，元組的第一項是數(shù)據(jù)內容，第二項是該數(shù)據(jù)的權重。也就是說，用于構建霍夫曼樹的數(shù)據(jù)是帶權重的。假設這些數(shù)據(jù)里面的字母a-f的權重是根據(jù)這些字母在一個文本出出現(xiàn)的概率計算得出的，字母出現(xiàn)的概率越高，則該字母的權重越大。例如字母 a 的權重為 8 .
拿到數(shù)據(jù)我們就可以來構建霍夫曼樹了。
1)找出所有元素中權重最小的兩個元素，即g(2)和c(3)，
2)以g和c為子節(jié)點構建二叉樹，則構建的二叉樹的父節(jié)點的權重為 2+3 = 5.
3)從除g和c以外剩下的元素和新構建的權重為5的節(jié)點中選出權重最小的兩個節(jié)點，
4)進行第 2 步操作。
以此類推，直至最后合成一個二叉樹就是霍夫曼樹。
11.2.4代碼實現(xiàn)
代碼參考：https://www.cnblogs.com/dongyangblog/p/11228930.html
class Node ():
def __init__(self,data,value):
self.value = value
self.data = data
self.left = None
self.right = None
# 定義獲取列表中權重最大的兩個節(jié)點的方法：
#1.定義 result 列表 帶有兩個value為正無窮的 Node 對象
#2.將權重最小的兩個結點放入 result 中
#3.將其他結點扔到list2中，包括從result淘汰的結點
def getmin2(list):
result = [Node (None,float('inf')), Node (None,float('inf'))]
list2 = []
for i in range(len(list)):
if list[i].value < result[0].value:
if result[1].value != float('inf'):
list2.append(result[1])
result[0] , result[1] = list[i] , result[0]
elif list[i].value < result[1].value:
if result[1].value != float('inf'):
list2.append(result[1])
result[1] = list[i]
else:
list2.append(list[i])
# for i in range(len(result)):
# print("result",result[i].value)
# for i in range(len(list2)):
# print("list2",list2[i].value)
return result , list2
#定義生成哈夫曼樹的方法：
#1.調用getmin2方法 獲得 min2，分別為left、right結點，data 為剩下的結點
#2.創(chuàng)建一個father結點，并將left、right分別賦給 father.left father.right
#3.如果data里空了 說明沒有剩余結點了 就可以返回 father了就是哈夫曼樹
#4.如果data不是空的，那么就還得繼續(xù)構造father結點， 并且記得把father結點扔到 data里面
#5.遞歸調用makeHuffman函數(shù)，也就繼續(xù)調用getmin2函數(shù)，繼續(xù)獲得最小權重的兩個結點
def makeHuffman(list):
min2, data = getmin2(list)
left = min2[0]
right = min2[1]
value = left.value + right.value
father = Node(None, value)
father.left = left
father.right = right
if data == []:
return father
data.append(father)
return makeHuffman(data)
# 遞歸方式實現(xiàn)廣度優(yōu)先遍歷
#1.先將Node對象的list轉為列表,只是把類型改了，list 的屬性都還在
#2.將值一個一個扔到result里面，先扔根結點，
# 3.然后判斷當前跟結點有沒有左右子結點，有的話將根結點的左子結點，右子結點分別扔到nextlist里去
#4.沒有的話判斷當前根結點是是其父結點的右子結點嗎，若是則判斷nextlist是否為空，
# 4.1 若為空說明以當前結點為根結點的樹遍歷完了（沒有葉子結點），可以返回了
# 4.2 若不為空，說明還沒有遍歷完，調整下參數(shù)以便繼續(xù)遍歷
#5.若不是右子結點，則將index + 1 使當前指向右子結點繼續(xù)遍歷
#6 全遍歷完，返回result
def traverse(list,index= 0 ,nextlist = [] ,result = []):
if type(list) == Node:
list = [list]
result.append((list[index].data,list[index].value))
if list[index].left != None:
nextlist.append((list[index].left))
if list[index].right != None:
nextlist.append((list[index].right))
if index == len(list)-1:
if nextlist == []:
return
else:
list = nextlist
nextlist = []
index = 0
else:
index +=1
traverse(list,index,nextlist,result)
return result
# 直接用前序遍歷將其輸出
# def traverse(list):
# # if type(list) == Node:
# # list = [list]
# print(list.data,list.value)
# if list.left != None:
# traverse(list.left)
# if list.right != None:
# traverse(list.right)
#文章中部分字母根據(jù)出現(xiàn)的概率規(guī)定權重，并讓其生成Node對象
#將字符串轉為攜帶自身字符及次數(shù)（權重）組成的元組的列表，再實例化Node對象
str = "Hello world，i love python"
#統(tǒng)計字符串出現(xiàn)字符的次數(shù)，并與字符組成字典
sourceData = {x:str.count(x) for x in str }
print("1",sourceData)
#sourceData.items() ： 以列表形式返回可遍歷的(鍵, 值) 元組數(shù)組。
#sourceData = sourceData.items() 也可以
sourceData = [(key,val) for key,val in sourceData.items()]
print("2",sourceData)
#將每個元組中的第0個元素與第一個元素作為參數(shù)實例化Node對象
sourceData = [Node(x[0], x[1]) for x in sourceData]
print("3",sourceData)
huffman = makeHuffman(sourceData)
# print(huffman.value)
# print(huffman.left.value)
# print(huffman.right.value)
# # print(huffman.left.left.value)
# # print(huffman.left.right.value)
# print(huffman.right.right.value)
# print(huffman.right.left.value)
huff = traverse(huffman)
print(huff)
