python使用遞歸的方式建立二叉樹
更新時(shí)間：2019年07月03日 14:53:25 作者：aguncn
這篇文章主要介紹了python使用遞歸的方式建立二叉樹，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
樹和圖的數(shù)據(jù)結(jié)構(gòu)，就很有意思啦。
# coding = utf-8
class BinaryTree:
def __init__(self, root_obj):
self.key = root_obj
self.left_child = None
self.right_child = None
def insert_left(self, new_node):
node = BinaryTree(new_node)
if self.left_child is None:
self.left_child = node
else:
node.left_child = self.left_child
self.left_child = node
def insert_right(self, new_node):
node = BinaryTree(new_node)
if self.right_child is None:
self.right_child = node
else:
node.right_child = self.right_child
self.right_child = node
def get_right_child(self):
return self.right_child
def get_left_child(self):
return self.left_child
def set_root_val(self, obj):
self.key = obj
def get_root_val(self):
return self.key
root = BinaryTree('a')
print(root.get_root_val())
print(root.get_left_child())
root.insert_left('b')
print(root.get_left_child())
print(root.get_left_child().get_root_val())
root.insert_right('c')
print(root.get_right_child())
print(root.get_right_child().get_root_val())
root.get_right_child().set_root_val('hello')
print(root.get_right_child().get_root_val())
C:\Users\Sahara\.virtualenvs\test\Scripts\python.exe C:/Users/Sahara/PycharmProjects/test/python_search.py a None <__main__.BinaryTree object at 0x00000000024139B0> b <__main__.BinaryTree object at 0x00000000024139E8> c hello Process finished with exit code 0
Python實(shí)現(xiàn)二叉樹遍歷的遞歸和非遞歸算法
前序遍歷
# -----------前序遍歷 ------------
# 遞歸算法
def pre_order_recursive(self, T):
if T == None:
return
print(T.root, end=' ')
self.pre_order_recursive(T.lchild)
self.pre_order_recursive(T.rchild)
# 非遞歸算法
def pre_order_non_recursive(self, T):
"""借助棧實(shí)現(xiàn)前驅(qū)遍歷
"""
if T == None:
return
stack = []
while T or len(stack) > 0:
if T:
stack.append(T)
print(T.root, end=' ')
T = T.lchild
else:
T = stack[-1]
stack.pop()
T = T.rchild
中序遍歷
# -----------中序遍歷 ------------
# 遞歸算法
def mid_order_recursive(self, T):
if T == None:
return
self.mid_order_recursive(T.lchild)
print(T.root, end=' ')
self.mid_order_recursive(T.rchild)
# 非遞歸算法
def mid_order_non_recursive(self, T):
"""借助棧實(shí)現(xiàn)中序遍歷
"""
if T == None:
return
stack = []
while T or len(stack) > 0:
if T:
stack.append(T)
T = T.lchild
else:
T = stack.pop()
print(T.root, end=' ')
T = T.rchild
后序遍歷
# -----------后序遍歷 ------------
# 遞歸算法
def post_order_recursive(self, T):
if T == None:
return
self.post_order_recursive(T.lchild)
self.post_order_recursive(T.rchild)
print(T.root, end=' ')
# 非遞歸算法
def post_order_non_recursive(self, T):
"""借助兩個(gè)棧實(shí)現(xiàn)后序遍歷
"""
if T == None:
return
stack1 = []
stack2 = []
stack1.append(T)
while stack1:
node = stack1.pop()
if node.lchild:
stack1.append(node.lchild)
if node.rchild:
stack1.append(node.rchild)
stack2.append(node)
while stack2:
print(stack2.pop().root, end=' ')
return
層次遍歷
# -----------層次遍歷 ------------
def level_order(self, T):
"""借助隊(duì)列（其實(shí)還是一個(gè)棧）實(shí)現(xiàn)層次遍歷
"""
if T == None:
return
stack = []
stack.append(T)
while stack:
node = stack.pop(0) # 實(shí)現(xiàn)先進(jìn)先出
print(node.root, end=' ')
if node.lchild:
stack.append(node.lchild)
if node.rchild:
stack.append(node.rchild)
完整代碼
class NodeTree:
def __init__(self, root=None, lchild=None, rchild=None):
"""創(chuàng)建二叉樹
Argument:
lchild: BinTree
左子樹
rchild: BinTree
右子樹
Return:
Tree
"""
self.root = root
self.lchild = lchild
self.rchild = rchild
class BinTree:
# -----------前序遍歷 ------------
# 遞歸算法
def pre_order_recursive(self, T):
if T == None:
return
print(T.root, end=' ')
self.pre_order_recursive(T.lchild)
self.pre_order_recursive(T.rchild)
# 非遞歸算法
def pre_order_non_recursive(self, T):
"""借助棧實(shí)現(xiàn)前驅(qū)遍歷
"""
if T == None:
return
stack = []
while T or len(stack) > 0:
if T:
stack.append(T)
print(T.root, end=' ')
T = T.lchild
else:
T = stack[-1]
stack.pop()
T = T.rchild
# -----------中序遍歷 ------------
# 遞歸算法
def mid_order_recursive(self, T):
if T == None:
return
self.mid_order_recursive(T.lchild)
print(T.root, end=' ')
self.mid_order_recursive(T.rchild)
# 非遞歸算法
def mid_order_non_recursive(self, T):
"""借助棧實(shí)現(xiàn)中序遍歷
"""
if T == None:
return
stack = []
while T or len(stack) > 0:
if T:
stack.append(T)
T = T.lchild
else:
T = stack.pop()
print(T.root, end=' ')
T = T.rchild
# -----------后序遍歷 ------------
# 遞歸算法
def post_order_recursive(self, T):
if T == None:
return
self.post_order_recursive(T.lchild)
self.post_order_recursive(T.rchild)
print(T.root, end=' ')
# 非遞歸算法
def post_order_non_recursive(self, T):
"""借助兩個(gè)棧實(shí)現(xiàn)后序遍歷
"""
if T == None:
return
stack1 = []
stack2 = []
stack1.append(T)
while stack1:
node = stack1.pop()
if node.lchild:
stack1.append(node.lchild)
if node.rchild:
stack1.append(node.rchild)
stack2.append(node)
while stack2:
print(stack2.pop().root, end=' ')
return
# -----------層次遍歷 ------------
def level_order(self, T):
"""借助隊(duì)列（其實(shí)還是一個(gè)棧）實(shí)現(xiàn)層次遍歷
"""
if T == None:
return
stack = []
stack.append(T)
while stack:
node = stack.pop(0) # 實(shí)現(xiàn)先進(jìn)先出
print(node.root, end=' ')
if node.lchild:
stack.append(node.lchild)
if node.rchild:
stack.append(node.rchild)
# ----------- 前序遍歷序列、中序遍歷序列 —> 重構(gòu)二叉樹 ------------
def tree_by_pre_mid(self, pre, mid):
if len(pre) != len(mid) or len(pre) == 0 or len(mid) == 0:
return
T = NodeTree(pre[0])
index = mid.index(pre[0])
T.lchild = self.tree_by_pre_mid(pre[1:index + 1], mid[:index])
T.rchild = self.tree_by_pre_mid(pre[index + 1:], mid[index + 1:])
return T
# ----------- 后序遍歷序列、中序遍歷序列 —> 重構(gòu)二叉樹 ------------
def tree_by_post_mid(self, post, mid):
if len(post) != len(mid) or len(post) == 0 or len(mid) == 0:
return
T = NodeTree(post[-1])
index = mid.index(post[-1])
T.lchild = self.tree_by_post_mid(post[:index], mid[:index])
T.rchild = self.tree_by_post_mid(post[index:-1], mid[index + 1:])
return T
if __name__ == '__main__':
# ----------- 測(cè)試：前序、中序、后序、層次遍歷 -----------
# 創(chuàng)建二叉樹
nodeTree = NodeTree(1,
lchild=NodeTree(2,
lchild=NodeTree(4,
rchild=NodeTree(7))),
rchild=NodeTree(3,
lchild=NodeTree(5),
rchild=NodeTree(6)))
T = BinTree()
print('前序遍歷遞歸\t')
T.pre_order_recursive(nodeTree) # 前序遍歷-遞歸
print('\n')
print('前序遍歷非遞歸\t')
T.pre_order_non_recursive(nodeTree) # 前序遍歷-非遞歸
print('\n')
print('中序遍歷遞歸\t')
T.mid_order_recursive(nodeTree) # 中序遍歷-遞歸
print('\n')
print('中序遍歷非遞歸\t')
T.mid_order_non_recursive(nodeTree) # 中序遍歷-非遞歸
print('\n')
print('后序遍歷遞歸\t')
T.post_order_recursive(nodeTree) # 后序遍歷-遞歸
print('\n')
print('后序遍歷非遞歸\t')
T.post_order_non_recursive(nodeTree) # 后序遍歷-非遞歸
print('\n')
print('層次遍歷\t')
T.level_order(nodeTree) # 層次遍歷
print('\n')
print('==========================================================================')
# ----------- 測(cè)試：由遍歷序列構(gòu)造二叉樹 -----------
T = BinTree()
pre = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I']
mid = ['B', 'C', 'A', 'E', 'D', 'G', 'H', 'F', 'I']
post = ['C', 'B', 'E', 'H', 'G', 'I', 'F', 'D', 'A']
newT_pre_mid = T.tree_by_pre_mid(pre, mid) # 由前序序列、中序序列構(gòu)造二叉樹
T.post_order_recursive(newT_pre_mid) # 獲取后序序列
print('\n')
newT_post_mid = T.tree_by_post_mid(post, mid) # 由后序序列、中序序列構(gòu)造二叉樹
T.pre_order_recursive(newT_post_mid) # 獲取前序序列
運(yùn)行結(jié)果
前序遍歷遞歸
1 2 4 7 3 5 6前序遍歷非遞歸
1 2 4 7 3 5 6中序遍歷遞歸
4 7 2 1 5 3 6中序遍歷非遞歸
4 7 2 1 5 3 6后序遍歷遞歸
7 4 2 5 6 3 1后序遍歷非遞歸
7 4 2 5 6 3 1層次遍歷
1 2 3 4 5 6 7==========================================================================
C B E H G I F D AA B C D E F G H I
以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
您可能感興趣的文章:
相關(guān)文章
使用pyplot.matshow()函數(shù)添加繪圖標(biāo)題
這篇文章主要介紹了使用pyplot.matshow()函數(shù)添加繪圖標(biāo)題，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2020-06-06
python實(shí)現(xiàn)QQ郵箱群發(fā)郵件實(shí)例
大家好，本篇文章主要講的是python實(shí)現(xiàn)QQ郵箱群發(fā)郵件實(shí)例，感興趣的同學(xué)趕快來(lái)看一看吧，對(duì)你有幫助的話記得收藏一下2022-01-01
解決json中ensure_ascii=False的問(wèn)題
這篇文章主要介紹了解決json中ensure_ascii=False的問(wèn)題，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2020-04-04
Python實(shí)現(xiàn)聊天機(jī)器人的示例代碼
這篇文章主要介紹了Python實(shí)現(xiàn)聊天機(jī)器人，小編覺得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2018-07-07
TensorBoard 計(jì)算圖的可視化實(shí)現(xiàn)
今天小編就為大家分享一篇TensorBoard 計(jì)算圖的可視化實(shí)現(xiàn)，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2020-02-02
opencv python統(tǒng)計(jì)及繪制直方圖的方法
這篇文章主要介紹了opencv python統(tǒng)計(jì)及繪制直方圖的方法，小編覺得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2019-01-01
這篇文章主要介紹了django框架ModelForm組件用法,結(jié)合實(shí)例形式較為詳細(xì)的分析了Django框架ModelForm組件相關(guān)功能、原理、使用方法及操作注意事項(xiàng),需要的朋友可以參考下2019-12-12
這篇文章主要為大家介紹了Python中獲取協(xié)程返回值的四種方法的示例代碼，文中的代碼詳細(xì)易懂，對(duì)我們學(xué)習(xí)Python有一定的幫助，需要的朋友可以了解一下2021-12-12
使用Python實(shí)現(xiàn)微信提醒備忘錄功能
最近工作比較繁雜，經(jīng)常忘事，有時(shí)候記了備忘錄結(jié)果卻忘記看備忘錄，但是微信是每天都會(huì)看的，于是就想到寫 一個(gè)基于微信的提醒系統(tǒng)。這篇文章主要介紹了使用Python實(shí)現(xiàn)微信提醒備忘錄功能,需要的朋友可以參考下2018-12-12
Python爬蟲爬取電影票房數(shù)據(jù)及圖表展示操作示例
這篇文章主要介紹了Python爬蟲爬取電影票房數(shù)據(jù)及圖表展示操作,結(jié)合實(shí)例形式分析了Python爬蟲爬取、解析電影票房數(shù)據(jù)并進(jìn)行圖表展示操作相關(guān)實(shí)現(xiàn)技巧,需要的朋友可以參考下2020-03-03