Python二叉搜索樹與雙向鏈表轉(zhuǎn)換實(shí)現(xiàn)方法
本文實(shí)例講述了Python二叉搜索樹與雙向鏈表實(shí)現(xiàn)方法。分享給大家供大家參考,具體如下:
# encoding=utf8 ''' 題目:輸入一棵二叉搜索樹,將該二叉搜索樹轉(zhuǎn)換成一個(gè)排序的雙向鏈表。 要求不能創(chuàng)建任何新的結(jié)點(diǎn),只能調(diào)整樹中結(jié)點(diǎn)指針的指向。 ''' class BinaryTreeNode(): def __init__(self, value, left = None, right = None): self.value = value self.left = left self.right = right def create_a_tree(): node_4 = BinaryTreeNode(4) node_8 = BinaryTreeNode(8) node_6 = BinaryTreeNode(6, node_4, node_8) node_12 = BinaryTreeNode(12) node_16 = BinaryTreeNode(16) node_14 = BinaryTreeNode(14, node_12, node_16) node_10 = BinaryTreeNode(10, node_6, node_14) return node_10 def print_a_tree(root): if root is None:return print_a_tree(root.left) print root.value, ' ', print_a_tree(root.right) def print_a_linked_list(head): print 'linked_list:' while head is not None: print head.value, ' ', head = head.right print '' def create_linked_list(root): '''構(gòu)造樹的雙向鏈表,返回這個(gè)雙向鏈表的最左結(jié)點(diǎn)和最右結(jié)點(diǎn)的指針''' if root is None: return (None, None) # 遞歸構(gòu)造出左子樹的雙向鏈表 (l_1, r_1) = create_linked_list(root.left) left_most = l_1 if l_1 is not None else root (l_2, r_2) = create_linked_list(root.right) right_most = r_2 if r_2 is not None else root # 將整理好的左右子樹和root連接起來 root.left = r_1 if r_1 is not None:r_1.right = root root.right = l_2 if l_2 is not None:l_2.left = root # 由于是雙向鏈表,返回給上層最左邊的結(jié)點(diǎn)和最右邊的結(jié)點(diǎn)指針 return (left_most, right_most) if __name__ == '__main__': tree_1 = create_a_tree() print_a_tree(tree_1) (left_most, right_most) = create_linked_list(tree_1) print_a_linked_list(left_most) pass
更多關(guān)于Python相關(guān)內(nèi)容可查看本站專題:《Python正則表達(dá)式用法總結(jié)》、《Python數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Python Socket編程技巧總結(jié)》、《Python函數(shù)使用技巧總結(jié)》、《Python字符串操作技巧匯總》、《Python入門與進(jìn)階經(jīng)典教程》及《Python文件與目錄操作技巧匯總》
希望本文所述對(duì)大家Python程序設(shè)計(jì)有所幫助。
相關(guān)文章
Python和JS反爬之解決反爬參數(shù)?signKey
這篇文章主要介紹了Python和JS反爬之解決反爬參數(shù)?signKey,Python?反爬中有一大類,叫做字體反爬,核心的理論就是通過字體文件或者?CSS?偏移,接下來文章的詳細(xì)介紹,需要的小伙伴可以參考一下2022-05-05詳解python os.path.exists判斷文件或文件夾是否存在
這篇文章主要介紹了詳解python os.path.exists判斷文件或文件夾是否存在,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-11-11PyCharm上安裝Package的實(shí)現(xiàn)(以pandas為例)
這篇文章主要介紹了PyCharm上安裝Package的實(shí)現(xiàn)(以pandas為例),文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-09-09tkinter動(dòng)態(tài)顯示時(shí)間的兩種實(shí)現(xiàn)方法
這篇文章主要介紹了tkinter動(dòng)態(tài)顯示時(shí)間的兩種實(shí)現(xiàn)方法,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-01-01Python面向?qū)ο筮M(jìn)階學(xué)習(xí)
在本文里我們整理了關(guān)于Python面向?qū)ο蟮倪M(jìn)階學(xué)習(xí)知識(shí)點(diǎn)以及學(xué)習(xí)路線等內(nèi)容,有興趣的朋友們學(xué)習(xí)下。2019-05-05