您好,登錄后才能下訂單哦!
這篇文章主要介紹了怎么在python中將有序數(shù)組轉(zhuǎn)換為二叉樹,此處通過實例代碼給大家介紹的非常詳細,對大家的學習或工作具有一定的參考價值,需要的朋友可以參考下:
Python主要應用于:1、Web開發(fā);2、數(shù)據(jù)科學研究;3、網(wǎng)絡(luò)爬蟲;4、嵌入式應用開發(fā);5、游戲開發(fā);6、桌面應用開發(fā)。
題目:將[0,1,2,3,4,5,6,7,8,9,10]存儲到二叉樹,原數(shù)組有序,轉(zhuǎn)換為二叉排序樹。
二叉排序樹的特點:當前節(jié)點的左子樹上的所有節(jié)點都小于該節(jié)點,右子樹上的所有節(jié)點都小于該節(jié)點。
二叉排序也稱為二叉查找樹。
我的實現(xiàn)思路:
取有序數(shù)組的中間節(jié)點作為根節(jié)點,將數(shù)組分為左右兩個部分,對左右兩個子數(shù)組做相同的操作,遞歸的實現(xiàn)。
圖示:
1
2
3
代碼實現(xiàn):
def array_to_bitree(array): #判斷arr是否為空 if len(array)==0: return BiTNode(array[0]) mid=len(array)//2 # 有序數(shù)組的中間元素的下標 #print(mid) #start=0 # 數(shù)組第一個元素的下標 #end=-1 # 數(shù)組最后一個元素的下標 if len(array)>0: #將中間元素作為二叉樹的根 root=BiTNode(array[mid]) #如果左邊的元素個數(shù)不為零,則遞歸調(diào)用函數(shù),生成左子樹 if len(array[:mid])>0: root.left_child = arrayToBiTree(array[:mid]) #如果右邊的元素個數(shù)不為零,則遞歸調(diào)用函數(shù),生成左子樹 if len(array[mid+1:])>0: root.right_child = arrayToBiTree(array[mid+1:]) return root
我們調(diào)用前面寫的三種遍歷方法看一看,我們構(gòu)造的樹是否正確:
#將[0,1,2,3,4,5,6,7,8,9,10]存儲到二叉樹 if __name__ == '__main__': #先構(gòu)造一個有序數(shù)組、鏈表 arr=[] for i in range(10): arr.append(i) print(arr) #調(diào)用函數(shù) BT=arrayToBiTree(arr) #前序遍歷二叉樹 print("前序") print_tree_pre_order(BT) # 中序遍歷二叉樹 print("中序") print_tree_mid_order(BT) # 后序遍歷二叉樹 print("后序") print_tree_after_order(BT)
輸出:
根據(jù)這三種遍歷結(jié)果可以判斷出二叉樹的結(jié)構(gòu),結(jié)果和前面的是一樣的,代碼如下:
#定義二叉樹結(jié)點類型 class BiTNode: """docstring for BiTNode""" def __init__(self,arg): self.data = arg self.left_child = None self.right_child = None #前序遍歷 def print_tree_pre_order(root): #先判斷二叉樹是否為空 #if root.left_child is None and root.right_child is None: if root is None: return root #先根 print(root.data) #再左 if root.left_child is not None: print_tree_pre_order(root.left_child) #再右 if root.right_child is not None: print_tree_pre_order(root.right_child) #中序遍歷二叉樹 def print_tree_mid_order(root): #先判斷二叉樹是否為空,當左右節(jié)點都為空時 if root is None: return #中序遍歷 左根右 #遍歷左子樹 if root.left_child is not None: print_tree_mid_order(root.left_child) #遍歷根節(jié)點 print(root.data) #遍歷右子樹 if root.right_child is not None: print_tree_mid_order(root.right_child) #后序遍歷 def print_tree_after_order(root): #先判斷二叉樹是否為空 if root is None: return root #再左 if root.left_child is not None: print_tree_after_order(root.left_child) #再右 if root.right_child is not None: print_tree_after_order(root.right_child) #先根 print(root.data) def array_to_bitree(array): #判斷arr是否為空 if len(array)==0: return BiTNode(array[0]) mid=len(array)//2 # 有序數(shù)組的中間元素的下標 #print(mid) #start=0 # 數(shù)組第一個元素的下標 #end=-1 # 數(shù)組最后一個元素的下標 if len(array)>0: #將中間元素作為二叉樹的根 root=BiTNode(array[mid]) #如果左邊的元素個數(shù)不為零,則遞歸調(diào)用函數(shù),生成左子樹 if len(array[:mid])>0: root.left_child = array_to_bitree(array[:mid]) #如果右邊的元素個數(shù)不為零,則遞歸調(diào)用函數(shù),生成左子樹 if len(array[mid+1:])>0: root.right_child = array_to_bitree(array[mid+1:]) return root #將[0,1,2,3,4,5,6,7,8,9,10]存儲到二叉樹 if __name__ == '__main__': #先構(gòu)造一個有序數(shù)組、鏈表 arr=[] for i in range(9): arr.append(i) print(arr) #調(diào)用函數(shù) BT=array_to_bitree(arr) #前序遍歷二叉樹 print("前序") print_tree_pre_order(BT) # 中序遍歷二叉樹 print("中序") print_tree_mid_order(BT) # 后序遍歷二叉樹 print("后序") print_tree_after_order(BT)
到此這篇關(guān)于怎么在python中將有序數(shù)組轉(zhuǎn)換為二叉樹的文章就介紹到這了,更多相關(guān)怎么在python中將有序數(shù)組轉(zhuǎn)換為二叉樹的內(nèi)容請搜索億速云以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持億速云!
免責聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。