python數(shù)據(jù)結(jié)構(gòu)之二叉樹的遍歷實例
遍歷方案
從二叉樹的遞歸定義可知，一棵非空的二叉樹由根結(jié)點及左、右子樹這三個基本部分組成。因此，在任一給定結(jié)點上，可以按某種次序執(zhí)行三個操作：
1).訪問結(jié)點本身(N)
2).遍歷該結(jié)點的左子樹(L)
3).遍歷該結(jié)點的右子樹(R)
有次序：
NLR、LNR、LRN
遍歷的命名
根據(jù)訪問結(jié)點操作發(fā)生位置命名：
NLR：前序遍歷(PreorderTraversal亦稱(先序遍歷)) ——訪問結(jié)點的操作發(fā)生在遍歷其左右子樹之前。
LNR：中序遍歷(InorderTraversal) ——訪問結(jié)點的操作發(fā)生在遍歷其左右子樹之中(間)。
LRN：后序遍歷(PostorderTraversal) ——訪問結(jié)點的操作發(fā)生在遍歷其左右子樹之后。
注：由于被訪問的結(jié)點必是某子樹的根，所以N(Node)、L(Left subtlee)和R(Right subtree)又可解釋為根、根的左子樹和根的右子樹。NLR、LNR和LRN分別又稱為先根遍歷、中根遍歷和后根遍歷。
遍歷算法
1)．先序遍歷的遞歸算法定義：
若二叉樹非空，則依次執(zhí)行如下操作：
a.訪問根結(jié)點
b.遍歷左子樹
c.遍歷右子樹
2)．中序遍歷的遞歸算法定義：
若二叉樹非空，則依次執(zhí)行如下操作：
a.遍歷左子樹
b.訪問根結(jié)點
c.遍歷右子樹
3)．后序遍歷得遞歸算法定義：
若二叉樹非空，則依次執(zhí)行如下操作：
a.遍歷左子樹
b.遍歷右子樹
c.訪問根結(jié)點
一、二叉樹的遞歸遍歷：
# -*- coding: utf - 8 - *-
class TreeNode(object):
def __init__(self, left=0, right=0, data=0):
self.left = left
self.right = right
self.data = data
class BTree(object):
def __init__(self, root=0):
self.root = root
def is_empty(self):
if self.root is 0:
return True
else:
return False
def preorder(self, treenode):
'前序（pre-order，NLR）遍歷'
if treenode is 0:
return
print treenode.data
self.preorder(treenode.left)
self.preorder(treenode.right)
def inorder(self, treenode):
'中序（in-order，LNR'
if treenode is 0:
return
self.inorder(treenode.left)
print treenode.data
self.inorder(treenode.right)
def postorder(self, treenode):
'后序（post-order，LRN）遍歷'
if treenode is 0:
return
self.postorder(treenode.left)
self.postorder(treenode.right)
print treenode.data
node1 = TreeNode(data=1)
node2 = TreeNode(node1, 0, 2)
node3 = TreeNode(data=3)
node4 = TreeNode(data=4)
node5 = TreeNode(node3, node4, 5)
node6 = TreeNode(node2, node5, 6)
node7 = TreeNode(node6, 0, 7)
node8 = TreeNode(data=8)
root = TreeNode(node7, node8, 'root')
bt = BTree(root)
print u'''
#生成的二叉樹
# ------------------------
# root
# 7 8
# 6
# 2 5
# 1 3 4
#
# -------------------------
'''
print '前序（pre-order，NLR）遍歷 ：\n'
bt.preorder(bt.root)
print '中序（in-order，LNR) 遍歷 ：\n'
bt.inorder(bt.root)
print '后序（post-order，LRN）遍歷 ：\n'
bt.postorder(bt.root)
二、.二叉樹的非遞歸遍歷
下面就用非遞歸的方式實現(xiàn)一遍。主要用到了 stack 和 queue維護一些數(shù)據(jù)節(jié)點：
# -*- coding: utf - 8 - *-
class TreeNode(object):
def __init__(self, left=0, right=0, data=0):
self.left = left
self.right = right
self.data = data
class BTree(object):
def __init__(self, root=0):
self.root = root
def is_empty(self):
if self.root is 0:
return True
else:
return False
def preorder(self, treenode):
'前序（pre-order，NLR）遍歷'
stack = []
while treenode or stack:
if treenode is not 0:
print treenode.data
stack.append(treenode)
treenode = treenode.left
else:
treenode = stack.pop()
treenode = treenode.right
def inorder(self, treenode):
'中序（in-order，LNR) 遍歷'
stack = []
while treenode or stack:
if treenode:
stack.append(treenode)
treenode = treenode.left
else:
treenode = stack.pop()
print treenode.data
treenode = treenode.right
# def postorder(self, treenode):
# stack = []
# pre = 0
# while treenode or stack:
# if treenode:
# stack.append(treenode)
# treenode = treenode.left
# elif stack[-1].right != pre:
# treenode = stack[-1].right
# pre = 0
# else:
# pre = stack.pop()
# print pre.data
def postorder(self, treenode):
'后序（post-order，LRN）遍歷'
stack = []
queue = []
queue.append(treenode)
while queue:
treenode = queue.pop()
if treenode.left:
queue.append(treenode.left)
if treenode.right:
queue.append(treenode.right)
stack.append(treenode)
while stack:
print stack.pop().data
def levelorder(self, treenode):
from collections import deque
if not treenode:
return
q = deque([treenode])
while q:
treenode = q.popleft()
print treenode.data
if treenode.left:
q.append(treenode.left)
if treenode.right:
q.append(treenode.right)
node1 = TreeNode(data=1)
node2 = TreeNode(node1, 0, 2)
node3 = TreeNode(data=3)
node4 = TreeNode(data=4)
node5 = TreeNode(node3, node4, 5)
node6 = TreeNode(node2, node5, 6)
node7 = TreeNode(node6, 0, 7)
node8 = TreeNode(data=8)
root = TreeNode(node7, node8, 'root')
bt = BTree(root)
print u'''
#生成的二叉樹
# ------------------------
# root
# 7 8
# 6
# 2 5
# 1 3 4
#
# -------------------------
'''
print '前序（pre-order，NLR）遍歷 ：\n'
bt.preorder(bt.root)
print '中序（in-order，LNR) 遍歷 ：\n'
bt.inorder(bt.root)
print '后序（post-order，LRN）遍歷 ：\n'
bt.postorder(bt.root)
print '層序（level-order，LRN）遍歷 ：\n'
bt.levelorder(bt.root)
相關(guān)文章
這篇文章主要介紹了python 中/ 和 % 和 //（地板除）的區(qū)別及簡介，本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友參考下吧2020-06-06
如何在windows下安裝Pycham2020軟件(方法步驟詳解)
這篇文章主要介紹了在windows下安裝Pycham2020軟件方法，本文通過圖文并茂的形式給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下2020-05-05
對于很多人來說,搶購火車票人們成了一個令人頭疼的問題,本文主要介紹了Python編寫一個多線程的12306搶票程序的示例,具有一定的參考價值,感興趣的可以了解一下2023-09-09
Python的地形三維可視化Matplotlib和gdal使用實例
這篇文章主要介紹了Python的地形三維可視化Matplotlib和gdal使用實例，具有一定借鑒價值，需要的朋友可以了解下。2017-12-12
這篇文章主要介紹了Python Scrapy框架第一個入門程序,結(jié)合實例形式分析了Python Scrapy框架項目的搭建、抓取字段設置、數(shù)據(jù)庫保存等相關(guān)操作技巧,需要的朋友可以參考下2020-02-02
作為一個運維人員，經(jīng)常需要獲取系統(tǒng)的的各種信息，使用python會很方便幫助獲得，這篇文章運用實例告訴大家如何利用Python來獲取操作系統(tǒng)的信息，有需要的可以參考借鑒。2016-09-09
簡單且有用的Python數(shù)據(jù)分析和機器學習代碼
Python編程是一種通用的編程語言,開源、靈活、功能強大且易于使用,python最重要的特性之一是其用于數(shù)據(jù)處理和分析任務的豐富實用程序和庫集,這篇文章主要給大家介紹了一些簡單且有用的Python數(shù)據(jù)分析和機器學習代碼,需要的朋友可以參考下2021-07-07
這篇文章主要為大家詳細介紹了python求解漢諾塔游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-07-07
在Python多線程編程中，我們常常需要處理多個線程同時訪問共享數(shù)據(jù)的情況，為了防止數(shù)據(jù)在多線程之間出現(xiàn)沖突，我們需要對線程進行同步。本文將詳細介紹Python中的線程同步的幾種常用方法,需要的朋友可以參考下2023-06-06
這篇文章主要介紹了Python Color類與文字繪制，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2022-08-08