前言
樹是數據結構中非常重要的一種，主要的用途是用來提高查找效率，對于要重復查找的情況效果更佳，如二叉排序樹、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)
需要源碼的小伙伴可自行下載：代碼傳送門
總結
以上就是這篇文章的全部內容了，希望本文的內容對大家的學習或者工作具有一定的參考學習價值，謝謝大家對腳本之家的支持。
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
