建站
咨詢
售后
建站咨詢
新聞中心
這里有您想知道的互聯(lián)網(wǎng)營銷解決方案
創(chuàng)新互聯(lián)Python教程：Python中樹的相關(guān)操作！
樹的存儲、表示與遍歷
成都地區(qū)優(yōu)秀IDC服務(wù)器托管提供商(成都創(chuàng)新互聯(lián)公司).為客戶提供專業(yè)的雅安移動機房,四川各地服務(wù)器托管,雅安移動機房、多線服務(wù)器托管.托管咨詢專線：18982081108
樹的存儲與表示
順序存儲:將數(shù)據(jù)結(jié)構(gòu)存儲在固定的數(shù)組中,然在遍歷速度上有一定的優(yōu)勢,但因所占空間比較大,是非主流二叉樹。二叉樹通常以鏈式存儲。
某個節(jié)點為空是用0表示。
節(jié)點的結(jié)構(gòu)：
二叉樹的建立
class Node(object): """二叉樹節(jié)點的封裝""" def __init__(self, element=None, lchild=None, rchild=None): self.element = element self.lchild = lchild self.rchild = rchild class Tree(object): """二叉樹的封裝""" def __init__(self, root=None): self.root = root def __add__(self, element): # 插入節(jié)點的封裝 node = Node(element) # 1.判斷是否為空，則對根結(jié)點進行賦值 if not self.root: self.root = node # 2. 如果存在跟結(jié)點，將根結(jié)點放入隊列 else: queue = [] # 將根結(jié)點放入隊列中 queue.append(self.root) # 對隊列中的所有節(jié)點進行遍歷 # 這里的循環(huán)每次都是從根結(jié)點往下循環(huán)的 while queue: # 3.彈出隊列中的第一個元素(第一次彈出的為根節(jié)點，然后是根的左節(jié)點，根的右節(jié)點，依次類推) cur = queue.pop(0) if not cur.lchild: cur.lchild = node return elif not cur.rchild: cur.rchild = node return else: # 左右子樹都存在就將左右子樹添加到隊列中去 queue.append(cur.lchild) queue.append(cur.rchild)
二叉樹的遍歷
遍歷是指對樹中所有結(jié)點的信息的訪問,即依次對樹中每個結(jié)點訪問一次且僅訪問一次,我們把這種對所有節(jié)點的訪問稱為遍歷(traversal)
廣度優(yōu)先遍歷（層次遍歷）
遍歷結(jié)果為1，2，3，4，5，6，7
def breadth_travel(self): """利用隊列實現(xiàn)樹的層次遍歷""" if self.root == None: return # 將二叉樹的節(jié)點依次放入隊列中，通過訪問隊列的形式實現(xiàn)樹的遍歷 queue = [] queue.append(self.root) while queue: node = queue.pop(0) print(node.element, end=',') if node.lchild != None: queue.append(node.lchild) if node.rchild != None: queue.append(node.rchild) print()
深度優(yōu)先遍歷
深度優(yōu)先遍歷有三種方式：
先序遍歷（根->左->右）：先訪問根結(jié)點，再先序遍歷左子樹，最后再先序遍歷右子樹，
中序遍歷（左->根->右）：先中序遍歷左子樹，然后再訪問根結(jié)點，最后再中序遍歷右子樹，
后序遍歷（左->右->根）：先后序遍歷左子樹，然后再后序遍歷右子樹，最后再訪問根結(jié)點。
先序遍歷： 1 2 4 5 3 6 7
中序遍歷： 4 2 5 1 6 3 7
后序遍歷： 4 5 2 6 7 3 1
遞歸實現(xiàn)先序遍歷
# 深度優(yōu)先遍歷：先序遍歷---根 左 右 def preorder(self, root): """遞歸實現(xiàn)先序遍歷""" if not root: return print(root.element, end=',') self.preorder(root.lchild) self.preorder(root.rchild)
遞歸實現(xiàn)中序遍歷
# 深度優(yōu)先遍歷：中序遍歷---左 根 右 def inorder(self, root): """遞歸實現(xiàn)中序遍歷""" if not root: return self.inorder(root.lchild) print(root.element, end=',') self.inorder(root.rchild)
遞歸實現(xiàn)后序遍歷
# 深度優(yōu)先遍歷：后序遍歷---左 右 根 def postorder(self, root): """遞歸實現(xiàn)后序遍歷""" if not root: return self.postorder(root.lchild) self.postorder(root.rchild) print(root.element, end=',')
測試代碼：
if __name__ == '__main__':
binaryTree = Tree()
for i in range(7):
binaryTree.__add__(i+1)
# 廣度優(yōu)先遍歷
print("廣度優(yōu)先：")
binaryTree.breadth_travel()
# 深度優(yōu)先，先序遍歷
root = binaryTree.root
binaryTree.preorder(root)
print('深度優(yōu)先--先序遍歷')
binaryTree.inorder(root)
print('深度優(yōu)先--中序遍歷')
binaryTree.postorder(root)
print('深度優(yōu)先--后序遍歷')廣度優(yōu)先： 1,2,3,4,5,6,7, 1,2,4,5,3,6,7,深度優(yōu)先--先序遍歷 4,2,5,1,6,3,7,深度優(yōu)先--中序遍歷 4,5,2,6,7,3,1,深度優(yōu)先--后序遍歷
和我們預(yù)期的結(jié)果完全相同。
想了解更多python知識，請移步Python視頻教程繼續(xù)學(xué)習(xí)??！
本文標題：創(chuàng)新互聯(lián)Python教程：Python中樹的相關(guān)操作！
網(wǎng)站鏈接：http://www.5511xx.com/article/dhgccgh.html
