這篇文章將為大家詳細(xì)講解有關(guān)Python如何實(shí)現(xiàn)二叉樹(shù)的層序建立，小編覺(jué)得挺實(shí)用的，因此分享給大家做個(gè)參考，希望大家閱讀完這篇文章后可以有所收獲。
樹(shù)節(jié)點(diǎn)定義
代碼來(lái)
class BSTreeNode(object): def __init__(self, data): self.val = data self.leftChild = None self.rightChild = None
這一段代碼太好理解了好吧，就不BB了。
二叉樹(shù)層序建立
不多說(shuō)，先上代碼
# 建立二叉樹(shù)是以層序遍歷方式輸入，節(jié)點(diǎn)不存在時(shí)以 'None' 表示 def creatTree(nodeList): if nodeList[0] == None: return None head = BSTreeNode(nodeList[0]) Nodes = [head] j = 1 for node in Nodes: if node != None: node.leftChild = (BSTreeNode(nodeList[j]) if nodeList[j] != None else None) Nodes.append(node.leftChild) j += 1 if j == len(nodeList): return head node.rightChild = (BSTreeNode(nodeList[j])if nodeList[j] != None else None) j += 1 Nodes.append(node.rightChild) if j == len(nodeList): return head
creatTree即為層序建立二叉樹(shù)的函數(shù)，傳入的參數(shù)為一個(gè)層序遍歷的數(shù)組，就是將樹(shù)節(jié)點(diǎn)從左往右，從上往下一次放入數(shù)組中，如果某個(gè)節(jié)點(diǎn)不存在則用None來(lái)表示。
比如：
圖所示的二叉樹(shù)則需輸入a = [1,2,3,4,5,None,6,None,None,7,8]，接下來(lái)將會(huì)以這個(gè)二叉樹(shù)為例講解代碼。
第3-4行，判斷根節(jié)點(diǎn)是否為空。 如果根節(jié)點(diǎn)都為空，那樹(shù)（shuo）就（ge）不（j）存（8）在了，直接返回就好了。
第5行，將元素列表中的第一個(gè)元素取出新建根節(jié)點(diǎn)，最后返回的即為根節(jié)點(diǎn)
第6行，創(chuàng)建了一個(gè)Nodes列表中，用于存放樹(shù)中的節(jié)點(diǎn)，每生成一個(gè)節(jié)點(diǎn)就將其放入該列表中，可以看成是一個(gè)隊(duì)列（這么說(shuō)好像也不是特別規(guī)范，因?yàn)楹竺嬷皇侨×斜碇械脑?，沒(méi)有彈出首元素），此處將根節(jié)點(diǎn)存入。
第7行，創(chuàng)建變量j用于nodeList中元素的索引，初始為1.因?yàn)榈?個(gè)元素已經(jīng)創(chuàng)建根節(jié)點(diǎn)了。
第8行，依次取出Nodes列表中的節(jié)點(diǎn)，對(duì)其創(chuàng)建左子節(jié)點(diǎn)和右子節(jié)點(diǎn)
第9行，首先判斷取出的Nodes是否為空，如果為空，說(shuō)明此處沒(méi)有節(jié)點(diǎn)，就無(wú)需創(chuàng)建子節(jié)點(diǎn)，否則進(jìn)行子節(jié)點(diǎn)的創(chuàng)建
第10行，為該節(jié)點(diǎn)創(chuàng)建左節(jié)點(diǎn)，其值就是索引j的所對(duì)應(yīng)的值，如果nodeLists[j] == None 說(shuō)明沒(méi)有該子節(jié)點(diǎn)，就不用創(chuàng)建了，即Child = None
第11行，將新建的節(jié)點(diǎn)加入Nodes數(shù)組，使其在for循環(huán)中可以繼續(xù)為其添加子節(jié)點(diǎn)
第12行，j加1，這樣剛好使每一個(gè)nodeList的元素對(duì)應(yīng)一個(gè)節(jié)點(diǎn)了
第13行，判斷j的值，如果與nodeList值相等說(shuō)明全部節(jié)點(diǎn)已經(jīng)添加完畢了，直接返回head根節(jié)點(diǎn)就完成了樹(shù)的建立
第15-19行，為節(jié)點(diǎn)添加右節(jié)點(diǎn)，與添加左節(jié)點(diǎn)的邏輯是一樣的，就不在贅述了
好了代碼注釋完畢，我們?cè)偻ㄟ^(guò)結(jié)合實(shí)例來(lái)解釋一下：
nodeList = [1,2,3,4,5,None,6,None,None,7,8],下面節(jié)點(diǎn)統(tǒng)一用n(值)來(lái)表示
建立根節(jié)點(diǎn) head = n(1), j=1, len(nodeList) = 11
開(kāi)始for循環(huán)：Nodes = [n(1)]
nodeList[j]=nodeList[9]=7 非空，所以新建節(jié)點(diǎn)n(7),n(5)的左節(jié)點(diǎn)即為n(7),新建節(jié)點(diǎn)放入Nodes, 則Nodes=[n(1),n(2)，n(3),n(4),n(5),None,n(6),None，None，n(9)] j+1=10, j未溢出
nodeList[j]=nodeList[10]=8 非空，所以新建節(jié)點(diǎn)n(8),n(5)的右節(jié)點(diǎn)即為n(8),新建節(jié)點(diǎn)放入Nodes, 則Nodes=[n(1),n(2)，n(3),n(4),n(5),None,n(6),None，None，n(9)，n(10)] j+1=11, j溢出
nodeList[j]=nodeList[7]=None 為空，所以n(4)的左節(jié)點(diǎn)直接等于None,同時(shí)將None也放入Nodes, 則Nodes=[n(1),n(2)，n(3),n(4),n(5),None,n(6),None], j+1=8, j未溢出
nodeList[j]=nodeList[8]=None 為空，所以n(4)的右節(jié)點(diǎn)直接等于None,同時(shí)將None也放入Nodes, 則Nodes=[n(1),n(2)，n(3),n(4),n(5),None,n(6),None，None], j+1=9, j未溢出
nodeList[j]=nodeList[5]=None 為空，所以n(3)的左節(jié)點(diǎn)直接等于None, 同時(shí)將None也放入Nodes, 則Nodes=[n(1),n(2)，n(3),n(4),n(5),None] j+1=6, j未溢出
nodeList[j]=nodeList[6]=6 非空，所以新建節(jié)點(diǎn)n(6),n(3)的右節(jié)點(diǎn)即為n(6),新建節(jié)點(diǎn)放入Nodes, 則Nodes=[n(1),n(2)，n(3),n(4),n(5),None,n(6)], j+1=7, j未溢出
nodeList[j]=nodeList[3]=4 非空，所以新建節(jié)點(diǎn)n(4),n(2)的左節(jié)點(diǎn)即為n(4),新建節(jié)點(diǎn)放入Nodes, 則Nodes=[n(1),n(2),n(3),n(4)], j+1=4, j未溢出
nodeList[j]=nodeList[4]=5 非空，所以新建節(jié)點(diǎn)n(5),n(2)的右節(jié)點(diǎn)即為n(5),新建節(jié)點(diǎn)放入Nodes, 則Nodes=[n(1),n(2)，n(3),n(4),n(5)], j+1=5, j未溢出
nodeList[j]=nodeList[1]=2 非空，所以新建節(jié)點(diǎn)n(2),n(1)的左節(jié)點(diǎn)即為n(2),新建節(jié)點(diǎn)放入Nodes, 則Nodes=[n(1),n(2)] j+1=2, j未溢出
nodeList[j]=nodeList[2]=3 非空，所以新建節(jié)點(diǎn)n(3),n(1)的右節(jié)點(diǎn)即為n(3),新建節(jié)點(diǎn)放入Nodes, 則Nodes=[n(1),n(2),n(3)], 然后j+1=3, j未溢出
node為n(1)，非空
node為n(2)，非空
node為n(3)，非空
node為n(4),非空
node為n(5), 非空
j溢出，則返回head根節(jié)點(diǎn)，結(jié)束二叉樹(shù)的建立
PS：如果node為空節(jié)點(diǎn)的話，就會(huì)直接跳過(guò)空節(jié)點(diǎn)。
二叉樹(shù)遍歷（神用的遞歸）
1. 前序遍歷
#head為二叉樹(shù)的根節(jié)點(diǎn) def PreorderTraverse(head): if head: print(head.val) PreorderTraverse(head.leftChild) PreorderTraverse(head.rightChild)
2. 中序遍歷
#head為二叉樹(shù)的根節(jié)點(diǎn) def InorderTrverse(head): if head: InorderTrverse(head.leftChild) print(head.val) InorderTrverse(head.rightChild)
3. 后續(xù)遍歷
#head為二叉樹(shù)的根節(jié)點(diǎn) def PostorderTraverse(head): if head: PostorderTraverse(head.leftChild) PostorderTraverse(head.rightChild) print(head.val)
對(duì)中序遍歷，費(fèi)了我九牛二虎之力畫了一個(gè)程序執(zhí)行的圖，紅色箭頭代表程序執(zhí)行的過(guò)程，依然以a = [1,2,3,4,5,None,6,None,None,7,8]為例
這個(gè)圖看上去不是很清楚，右鍵保存到本地看會(huì)清楚很多的，我把每一步遞歸的樹(shù)都畫出來(lái)了，這樣更加方便理解。
所以程序打印出來(lái)的順序?yàn)椋? 2 7 5 8 1 3 6
關(guān)于“Python如何實(shí)現(xiàn)二叉樹(shù)的層序建立”這篇文章就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，使各位可以學(xué)到更多知識(shí)，如果覺(jué)得文章不錯(cuò)，請(qǐng)把它分享出去讓更多的人看到。
另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無(wú)理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。
重慶分公司
重慶分公司
