Python利用前序和中序遍歷結(jié)果重建二叉樹(shù)的方法
本文實(shí)例講述了Python利用前序和中序遍歷結(jié)果重建二叉樹(shù)的方法。分享給大家供大家參考，具體如下：
題目：輸入某二叉樹(shù)的前序遍歷和中序遍歷的結(jié)果，請(qǐng)重建出該二叉樹(shù)。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字。
這道題比較容易，前序遍歷的結(jié)果中，第一個(gè)結(jié)點(diǎn)一定是根結(jié)點(diǎn)，然后在中序遍歷的結(jié)果中查找這個(gè)根結(jié)點(diǎn)，根結(jié)點(diǎn)左邊的就是左子樹(shù)，根結(jié)點(diǎn)右邊的就是右子樹(shù)，遞歸構(gòu)造出左、右子樹(shù)即可。示意圖如圖所示：
利用前序和中序遍歷的結(jié)果重建二叉樹(shù)
Python代碼：
# coding: utf-8
'''
題目：輸入某二叉樹(shù)的前序遍歷和中序遍歷的結(jié)果，請(qǐng)重建出該二叉樹(shù)。
假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字。
'''
class Node:
def __init__(self, data, left, right):
self.data = data
self.left = left
self.right = right
def construct_tree(pre_order, mid_order):
# 忽略參數(shù)合法性判斷
if len(pre_order) == 0 :
return None
# 前序遍歷的第一個(gè)結(jié)點(diǎn)一定是根結(jié)點(diǎn)
root_data = pre_order[0]
for i in range(0, len(mid_order)):
if mid_order[i] == root_data:
break
# 遞歸構(gòu)造左子樹(shù)和右子樹(shù)
left = construct_tree(pre_order[1 : 1 + i], mid_order[:i])
right = construct_tree(pre_order[1 + i:], mid_order[i+1:])
return Node(root_data, left, right)
if __name__ == '__main__':
pre_order = [1, 2, 4, 7, 3, 5, 6, 8]
mid_order = [4, 7, 2, 1, 5, 3, 8, 6]
root = construct_tree(pre_order, mid_order)
print root.data
print root.left.data
print root.right.data
print root.left.left.data
print root.left.left.right.data
print root.right.right.left
print root.right.left.data
更多關(guān)于Python相關(guān)內(nèi)容感興趣的讀者可查看本站專(zhuān)題：《Python數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Python Socket編程技巧總結(jié)》、《Python函數(shù)使用技巧總結(jié)》、《Python字符串操作技巧匯總》、《Python入門(mén)與進(jìn)階經(jīng)典教程》及《Python文件與目錄操作技巧匯總》
希望本文所述對(duì)大家Python程序設(shè)計(jì)有所幫助。
相關(guān)文章
本文主要介紹了python實(shí)現(xiàn)矩陣的示例代碼，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2023-07-07
pycharm右鍵沒(méi)有run,run不了問(wèn)題的解決
這篇文章主要介紹了pycharm右鍵沒(méi)有run,run不了問(wèn)題的解決方案,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-08-08
Python實(shí)現(xiàn)克里金插值法的過(guò)程詳解
克里金算法提供的半變異函數(shù)模型有高斯、線形、球形、阻尼正弦和指數(shù)模型等，在對(duì)氣象要素場(chǎng)插值時(shí)球形模擬比較好。本文將用Python實(shí)現(xiàn)克里金插值法，感興趣的可以了解一下2022-11-11
python和Appium移動(dòng)端多設(shè)備自動(dòng)化測(cè)試框架實(shí)現(xiàn)
這篇文章主要介紹了python和Appium移動(dòng)端多設(shè)備自動(dòng)化測(cè)試框架實(shí)現(xiàn)，基于pytest和Appium框架，支持Android和iOS功能自動(dòng)化的測(cè)試框架的相關(guān)內(nèi)容，需要的小伙伴可以參考一下2022-04-04
python中關(guān)于日期時(shí)間處理的問(wèn)答集錦
python中有關(guān)日期時(shí)間處理的問(wèn)答集錦，有需要的朋友不妨參考下2013-03-03
一篇文章帶你了解python標(biāo)準(zhǔn)庫(kù)--os模塊
在本篇內(nèi)容里小編給大家整理的是關(guān)于Python中os模塊及用法相關(guān)知識(shí)點(diǎn)，有興趣的朋友們可以學(xué)習(xí)下,希望能給你帶來(lái)幫助2021-08-08
這篇文章主要介紹了Python jieba庫(kù)用法及實(shí)例解析,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2019-11-11
Python:二維列表下標(biāo)互換方式(矩陣轉(zhuǎn)置)
今天小編就為大家分享一篇Python:二維列表下標(biāo)互換方式(矩陣轉(zhuǎn)置)，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2019-12-12
Python讀取大量Excel文件并跨文件批量計(jì)算平均值的方法
這篇文章主要介紹了Python讀取大量Excel文件并跨文件批量計(jì)算平均值,介紹基于Python語(yǔ)言，實(shí)現(xiàn)對(duì)多個(gè)不同Excel文件進(jìn)行數(shù)據(jù)讀取與平均值計(jì)算的方法，需要的朋友可以參考下2023-02-02
使用Python在PowerPoint演示文稿之間復(fù)制樣式
在專(zhuān)業(yè)演示文稿設(shè)計(jì)與制作領(lǐng)域,多場(chǎng)演示間保持一致性至關(guān)重要,在PowerPoint演示文稿之間復(fù)制幻燈片母版成為了一項(xiàng)關(guān)鍵技巧,本文中,我們將探討如何使用Python在不同的PowerPoint演示文稿之間復(fù)制幻燈片母版,提升演示文稿創(chuàng)作流程的效率與美觀度,需要的朋友可以參考下2024-05-05