創(chuàng)新互聯(lián)www.cdcxhl.cn八線動(dòng)態(tài)BGP香港云服務(wù)器提供商，新人活動(dòng)買多久送多久，劃算不套路！
目前創(chuàng)新互聯(lián)已為成百上千家的企業(yè)提供了網(wǎng)站建設(shè)、域名、雅安服務(wù)器托管、網(wǎng)站托管、服務(wù)器租用、企業(yè)網(wǎng)站設(shè)計(jì)、巫山網(wǎng)站維護(hù)等服務(wù)，公司將堅(jiān)持客戶導(dǎo)向、應(yīng)用為本的策略，正道將秉承"和諧、參與、激情"的文化，與客戶和合作伙伴齊心協(xié)力一起成長，共同發(fā)展。本篇文章給大家分享的是有關(guān)Python中有關(guān)樹的使用方法，小編覺得挺實(shí)用的，因此分享給大家學(xué)習(xí)，希望大家閱讀完這篇文章后可以有所收獲，話不多說，跟著小編一起來看看吧。
樹的存儲、表示與遍歷
樹的存儲與表示
順序存儲:將數(shù)據(jù)結(jié)構(gòu)存儲在固定的數(shù)組中,然在遍歷速度上有一定的優(yōu)勢,但因所占空間比較大,是非主流二叉樹。二叉樹通常以鏈?zhǔn)酱鎯Α?/p>
某個(gè)節(jié)點(diǎn)為空是用0表示。
節(jié)點(diǎn)的結(jié)構(gòu)：
二叉樹的建立
class Node(object): """二叉樹節(jié)點(diǎn)的封裝""" 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é)點(diǎn)的封裝 node = Node(element) # 1.判斷是否為空，則對根結(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ì)列中的所有節(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: # 左右子樹都存在就將左右子樹添加到隊(duì)列中去 queue.append(cur.lchild) queue.append(cur.rchild)
二叉樹的遍歷
遍歷是指對樹中所有結(jié)點(diǎn)的信息的訪問,即依次對樹中每個(gè)結(jié)點(diǎn)訪問一次且僅訪問一次,我們把這種對所有節(jié)點(diǎn)的訪問稱為遍歷(traversal)
廣度優(yōu)先遍歷（層次遍歷）
遍歷結(jié)果為1，2，3，4，5，6，7
def breadth_travel(self): """利用隊(duì)列實(shí)現(xiàn)樹的層次遍歷""" if self.root == None: return # 將二叉樹的節(jié)點(diǎn)依次放入隊(duì)列中，通過訪問隊(duì)列的形式實(shí)現(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é)點(diǎn)，再先序遍歷左子樹，最后再先序遍歷右子樹，
中序遍歷（左->根->右）：先中序遍歷左子樹，然后再訪問根結(jié)點(diǎ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=',')
測試代碼：
重慶分公司
重慶分公司
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中有關(guān)樹的使用方法，小編相信有部分知識點(diǎn)可能是我們?nèi)粘９ぷ鲿姷交蛴玫降?。希望你能通過這篇文章學(xué)到更多知識。更多詳情敬請關(guān)注創(chuàng)新互聯(lián)-成都網(wǎng)站建設(shè)公司行業(yè)資訊頻道。
