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