溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
前言
樹是數據結構中非常重要的一種，主要的用途是用來提高查找效率，對于要重復查找的情況效果更佳，如二叉排序樹、FP-樹。另外可以用來提高編碼效率，如哈弗曼樹。
用 Python 實現樹的構造和幾種遍歷算法。實現功能如下：
# -*- coding=utf-8 -*-
class Node(object):
"""節點類"""
def __init__(self, element=-1, l_child=None, r_child=None):
self.element = element
self.l_child = l_child
self.r_child = r_child
class Tree(object):
"""樹類"""
def __init__(self):
self.root = Node()
self.queue = []
def add_node(self, element):
"""為樹添加節點"""
node = Node(element)
# 如果樹是空的，則對根節點賦值
if self.root.element == -1:
self.root = node
self.queue.append(self.root)
else:
tree_node = self.queue[0]
# 此結點沒有左子樹，則創建左子樹節點
if tree_node.l_child is None:
tree_node.l_child = node
self.queue.append(tree_node.l_child)
else:
tree_node.r_child = node
self.queue.append(tree_node.r_child)
# 如果該結點存在右子樹，將此節點丟棄
self.queue.pop(0)
def front_recursion(self, root):
"""利用遞歸實現樹的前序遍歷"""
if root is None:
return
print root.element,
self.front_recursion(root.l_child)
self.front_recursion(root.r_child)
def middle_recursion(self, root):
"""利用遞歸實現樹的中序遍歷"""
if root is None:
return
self.middle_recursion(root.l_child)
print root.element,
self.middle_recursion(root.r_child)
def back_recursion(self, root):
"""利用遞歸實現樹的后序遍歷"""
if root is None:
return
self.back_recursion(root.l_child)
self.back_recursion(root.r_child)
print root.element,
@staticmethod
def front_stack(root):
"""利用堆棧實現樹的前序遍歷"""
if root is None:
return
stack = []
node = root
while node or stack:
# 從根節點開始，一直找它的左子樹
while node:
print node.element,
stack.append(node)
node = node.l_child
# while結束表示當前節點node為空，即前一個節點沒有左子樹了
node = stack.pop()
# 開始查看它的右子樹
node = node.r_child
@staticmethod
def middle_stack(root):
"""利用堆棧實現樹的中序遍歷"""
if root is None:
return
stack = []
node = root
while node or stack:
# 從根節點開始，一直找它的左子樹
while node:
stack.append(node)
node = node.l_child
# while結束表示當前節點node為空，即前一個節點沒有左子樹了
node = stack.pop()
print node.element,
# 開始查看它的右子樹
node = node.r_child
@staticmethod
def back_stack(root):
"""利用堆棧實現樹的后序遍歷"""
if root is None:
return
stack1 = []
stack2 = []
node = root
stack1.append(node)
# 這個while循環的功能是找出后序遍歷的逆序，存在stack2里面
while stack1:
node = stack1.pop()
if node.l_child:
stack1.append(node.l_child)
if node.r_child:
stack1.append(node.r_child)
stack2.append(node)
# 將stack2中的元素出棧，即為后序遍歷次序
while stack2:
print stack2.pop().element,
@staticmethod
def level_queue(root):
"""利用隊列實現樹的層次遍歷"""
if root is None:
return
queue = []
node = root
queue.append(node)
while queue:
node = queue.pop(0)
print node.element,
if node.l_child is not None:
queue.append(node.l_child)
if node.r_child is not None:
queue.append(node.r_child)
if __name__ == '__main__':
"""主函數"""
# 生成十個數據作為樹節點
elements = range(10)
tree = Tree()
for elem in elements:
tree.add_node(elem)
print '隊列實現層次遍歷:'
tree.level_queue(tree.root)
print '\n\n遞歸實現前序遍歷:'
tree.front_recursion(tree.root)
print '\n遞歸實現中序遍歷:'
tree.middle_recursion(tree.root)
print '\n遞歸實現后序遍歷:'
tree.back_recursion(tree.root)
print '\n\n堆棧實現前序遍歷:'
tree.front_stack(tree.root)
print '\n堆棧實現中序遍歷:'
tree.middle_stack(tree.root)
print '\n堆棧實現后序遍歷:'
tree.back_stack(tree.root)
需要源碼的小伙伴可自行下載：代碼傳送門
總結
以上就是這篇文章的全部內容了，希望本文的內容對大家的學習或者工作具有一定的參考學習價值，謝謝大家對億速云的支持。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
