python數據結構之二叉樹的統(tǒng)計與轉換實例
更新時間：2014年04月29日 09:16:33 作者：
這篇文章主要介紹了python數據結構之二叉樹的統(tǒng)計與轉換實例，例如統(tǒng)計二叉樹的葉子、分支節(jié)點，以及二叉樹的左右兩樹互換等,需要的朋友可以參考下
一、獲取二叉樹的深度
就是二叉樹最后的層次，如下圖：
實現代碼：
復制代碼 代碼如下:
def getheight(self):
''' 獲取二叉樹深度 '''
return self.__get_tree_height(self.root)
def __get_tree_height(self, root):
if root is 0:
return 0
if root.left is 0 and root.right is 0:
return 1
else:
left = self.__get_tree_height(root.left)
right = self.__get_tree_height(root.right)
if left < right:
return right + 1
else:
return left + 1
二、葉子的統(tǒng)計
葉子就是二叉樹的節(jié)點的 left 指針和 right 指針分別指向空的節(jié)點
復制代碼 代碼如下:
def getleafcount(self):
''' 獲取二叉樹葉子數 '''
return self.__count_leaf_node(self.root)
def __count_leaf_node(self, root):
res = 0
if root is 0:
return res
if root.left is 0 and root.right is 0:
res += 1
return res
if root.left is not 0:
res += self.__count_leaf_node(root.left)
if root.right is not 0:
res += self.__count_leaf_node(root.right)
return res
三、統(tǒng)計葉子的分支節(jié)點
與葉子節(jié)點相對的其他節(jié)點 left 和 right 的指針指向其他節(jié)點
復制代碼 代碼如下:
def getbranchcount(self):
''' 獲取二叉樹分支節(jié)點數 '''
return self.__get_branch_node(self.root)
def __get_branch_node(self, root):
if root is 0:
return 0
if root.left is 0 and root.right is 0:
return 0
else:
return 1 + self.__get_branch_node(root.left) + self.__get_branch_node(root.right)
四、二叉樹左右樹互換
復制代碼 代碼如下:
def replacelem(self):
''' 二叉樹所有結點的左右子樹相互交換 '''
self.__replace_element(self.root)
def __replace_element(self, root):
if root is 0:
return
root.left, root.right = root.right, root.left
self.__replace_element(root.left)
self.__replace_element(root.right)
這些方法和操作，都是運用遞歸。其實二叉樹的定義也是一種遞歸。附上最后的完整代碼：
復制代碼 代碼如下:
# -*- 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 BinaryTree(object):
def __init__(self, root=0):
self.root = root
def is_empty(self):
if self.root is 0:
return True
else:
return False
def create(self):
temp = input('enter a value:')
if temp is '#':
return 0
treenode = TreeNode(data=temp)
if self.root is 0:
self.root = treenode
treenode.left = self.create()
treenode.right = self.create()
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
def preorders(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 inorders(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 postorders(self, treenode):
'后序（post-order，LRN）非遞歸遍歷'
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 postorders(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 levelorders(self, treenode):
'層序（post-order，LRN）非遞歸遍歷'
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)
def getheight(self):
''' 獲取二叉樹深度 '''
return self.__get_tree_height(self.root)
def __get_tree_height(self, root):
if root is 0:
return 0
if root.left is 0 and root.right is 0:
return 1
else:
left = self.__get_tree_height(root.left)
right = self.__get_tree_height(root.right)
if left < right:
return right + 1
else:
return left + 1
def getleafcount(self):
''' 獲取二叉樹葉子數 '''
return self.__count_leaf_node(self.root)
def __count_leaf_node(self, root):
res = 0
if root is 0:
return res
if root.left is 0 and root.right is 0:
res += 1
return res
if root.left is not 0:
res += self.__count_leaf_node(root.left)
if root.right is not 0:
res += self.__count_leaf_node(root.right)
return res
def getbranchcount(self):
''' 獲取二叉樹分支節(jié)點數 '''
return self.__get_branch_node(self.root)
def __get_branch_node(self, root):
if root is 0:
return 0
if root.left is 0 and root.right is 0:
return 0
else:
return 1 + self.__get_branch_node(root.left) + self.__get_branch_node(root.right)
def replacelem(self):
''' 二叉樹所有結點的左右子樹相互交換 '''
self.__replace_element(self.root)
def __replace_element(self, root):
if root is 0:
return
root.left, root.right = root.right, root.left
self.__replace_element(root.left)
self.__replace_element(root.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 = BinaryTree(root)
print u'''
生成的二叉樹
------------------------
root
7 8
6
2 5
1 3 4
-------------------------
'''
相關文章
Scrapy是一個基于Python的強大的開源網絡爬蟲框架,用于從網站上抓取信息,它提供了廣泛的功能,使得爬取和分析數據變得相對容易,本文小編將給給大家介紹一下如何使用python框架Scrapy爬取數據,需要的朋友可以參考下2023-10-10
用python記錄運行pid,并在需要時kill掉它們的實例
下面小編就為大家?guī)硪黄胮ython記錄運行pid,并在需要時kill掉它們的實例。小編覺得挺不錯的，現在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-01-01
這篇文章主要為大家介紹了python密碼學黑客攻擊RSA密碼，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-05-05
這篇文章主要為大家詳細介紹了使用python實現ANN的相關資料，具有一定的參考價值，感興趣的小伙伴們可以參考一下2017-12-12
這篇文章主要介紹了python兩個_多個字典合并相加,本文通過實例代碼給大家介紹的非常詳細，具有一定的參考借鑒價值，需要的朋友可以參考下2019-12-12
這篇文章主要介紹了Python中的進程、線程、協(xié)程的相關資料,需要的朋友可以參考下2016-03-03
這篇文章主要給大家介紹了在Python中模塊與包有相同名字的處理方法，文中介紹的非常詳細，對大家具有一定的參考學習價值，需要的朋友們下面來一起看看吧。2017-05-05
這篇文章主要介紹了簡單有效上手Python3異步asyncio問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-01-01
在本篇文章里小編給大家分享了關于PyCharm中代碼字體大小調整方法以及相關知識點，需要的朋友們學習下。2019-07-07
微軟開源最強Python自動化神器Playwright(不用寫一行代碼)
這篇文章主要介紹了微軟開源最強Python自動化神器Playwright(不用寫一行代碼),文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2021-01-01