Python利用前序和中序遍歷結(jié)果重建二叉樹的方法
本文實(shí)例講述了Python利用前序和中序遍歷結(jié)果重建二叉樹的方法。分享給大家供大家參考,具體如下:
題目:輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果,請重建出該二叉樹。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字。
這道題比較容易,前序遍歷的結(jié)果中,第一個(gè)結(jié)點(diǎn)一定是根結(jié)點(diǎn),然后在中序遍歷的結(jié)果中查找這個(gè)根結(jié)點(diǎn),根結(jié)點(diǎn)左邊的就是左子樹,根結(jié)點(diǎn)右邊的就是右子樹,遞歸構(gòu)造出左、右子樹即可。示意圖如圖所示:
利用前序和中序遍歷的結(jié)果重建二叉樹
Python代碼:
# coding: utf-8 ''' 題目:輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果,請重建出該二叉樹。 假設(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)造左子樹和右子樹 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)容感興趣的讀者可查看本站專題:《Python數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Python Socket編程技巧總結(jié)》、《Python函數(shù)使用技巧總結(jié)》、《Python字符串操作技巧匯總》、《Python入門與進(jìn)階經(jīng)典教程》及《Python文件與目錄操作技巧匯總》
希望本文所述對大家Python程序設(shè)計(jì)有所幫助。
相關(guān)文章
對python以16進(jìn)制打印字節(jié)數(shù)組的方法詳解
今天小編就為大家分享一篇對python以16進(jìn)制打印字節(jié)數(shù)組的方法詳解,具有很好的參考價(jià)值,希望對大家有所幫助。一起跟隨小編過來看看吧2019-01-01python實(shí)現(xiàn)自動解數(shù)獨(dú)小程序
這篇文章主要為大家詳細(xì)介紹了python實(shí)現(xiàn)自動解數(shù)獨(dú)小程序,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2019-01-01在Python中操作字符串之startswith()方法的使用
這篇文章主要介紹了在Python中操作字符串之startswith()方法的使用,是Python入門學(xué)習(xí)中的基礎(chǔ)知識,需要的朋友可以參考下2015-05-05pycharm 設(shè)置項(xiàng)目的根目錄教程
今天小編就為大家分享一篇pycharm 設(shè)置項(xiàng)目的根目錄教程,具有很好的參考價(jià)值,希望對大家有所幫助。一起跟隨小編過來看看吧2020-02-02