前言

本文的內(nèi)容是數(shù)據(jù)結(jié)構(gòu)中二叉樹(shù)部分最基礎(chǔ)的，之所以寫(xiě)一下主要是為了方便刷題的時(shí)候，能夠在自己電腦上很快的使用這種小的demo進(jìn)行復(fù)雜的練習(xí)。

二叉樹(shù)節(jié)點(diǎn)定義

二叉樹(shù)的節(jié)點(diǎn)定義如下：

class TreeNode():#二叉樹(shù)節(jié)點(diǎn) def __init__(self,val,lchild=None,rchild=None): self.val=val#二叉樹(shù)的節(jié)點(diǎn)值 self.lchild=lchild#左孩子 self.rchild=rchild#右孩子遞歸構(gòu)建二叉樹(shù)

本文使用的前序遞歸構(gòu)建的方法（其余順序讀者自行變化，本文主要意在如何快速構(gòu)建能夠執(zhí)行的二叉樹(shù)）例如，我們想構(gòu)建一個(gè)如下圖所示的樹(shù)（其前序遍歷結(jié)果為：abcde）:

這里我們需要使用到擴(kuò)展的二叉樹(shù)，也就是要告訴計(jì)算機(jī)什么是葉結(jié)點(diǎn)，什么是空節(jié)點(diǎn)，否側(cè)無(wú)法分辨左右節(jié)點(diǎn)。例如先序遍歷的順序?yàn)?abcde'，擴(kuò)展的二叉樹(shù)前序序列為：“abc##d##e##”，#代表此處節(jié)點(diǎn)為None，如下圖：

既然是使用遞歸的方法構(gòu)建二叉樹(shù)，主要需要理解遞歸的過(guò)程，這種思路將在之后的很多地方用的到。要知道如何遞歸的構(gòu)建二叉樹(shù)，我們不能糾結(jié)于遞歸每一層到底干了什么，這樣就會(huì)一直糾結(jié)下去（所有的遞歸問(wèn)題都一樣）。我們需要注意的是：

在我們的任務(wù)中，終止條件是什么？ 在我們的任務(wù)中，本次遞歸要干嘛？ 在我們的任務(wù)中，本次遞歸要返回給上一次遞歸的是啥？

在遞歸構(gòu)建二叉樹(shù)的任務(wù)中，我們要做到不糾結(jié)于每一層，而是只關(guān)注該層在做什么，這樣，對(duì)于下圖左側(cè)的樹(shù)，我們就可以看作為右側(cè)的樹(shù)，它只有自己a (a)，左子樹(shù)B (bcd)和右子樹(shù)C (e)。

這樣我們需要注意的那三個(gè)問(wèn)題的回答自然就有了（做遞歸問(wèn)題，心中要想著怎么回答這三個(gè)問(wèn)題）：

在我們的任務(wù)中，終止條件是什么？

[給我們的字符用完，也就不需要再創(chuàng)建節(jié)點(diǎn)了]

在我們的任務(wù)中，本次遞歸要干嘛？

[本次遞歸要?jiǎng)?chuàng)建三個(gè)節(jié)點(diǎn)，一個(gè)根節(jié)點(diǎn)，一個(gè)左節(jié)點(diǎn)，一個(gè)右節(jié)點(diǎn)]

在我們的任務(wù)中，本次遞歸要返回給上一次遞歸的是啥？

[當(dāng)然是返回一個(gè)本層構(gòu)造好的樹(shù)的根節(jié)點(diǎn)]理解了上述三個(gè)問(wèn)題的回答，遞歸的代碼自然可以寫(xiě)出：

def Creat_Tree(Root,val): if len(vals)==0:#終止條件：val用完了 return Root if vals[0]!=’#’:#本層需要干的就是構(gòu)建Root、Root.lchild、Root.rchild三個(gè)節(jié)點(diǎn)。 Root = TreeNode(vals[0]) vals.pop(0) Root.lchild = Creat_Tree(Root.lchild,val) Root.rchild = Creat_Tree(Root.rchild,val) return Root#本次遞歸要返回給上一次的本層構(gòu)造好的樹(shù)的根節(jié)點(diǎn) else: Root=None vals.pop(0) return Root#本次遞歸要返回給上一次的本層構(gòu)造好的樹(shù)的根節(jié)點(diǎn)

看懂了上述內(nèi)容，構(gòu)建一棵我們想象的二叉樹(shù)就很簡(jiǎn)單了，只要輸入一個(gè)我們心目中前序遍歷擴(kuò)展的二叉樹(shù)序列即可：

if __name__ == ’__main__’: Root = None strs='abc##d##e##'#前序遍歷擴(kuò)展的二叉樹(shù)序列 vals = list(strs) Roots=Creat_Tree(Root,vals)#Roots就是我們要的二叉樹(shù)的根節(jié)點(diǎn)。

以上就是如何在Python中創(chuàng)建二叉樹(shù)的詳細(xì)內(nèi)容，更多關(guān)于Python創(chuàng)建二叉樹(shù)的資料請(qǐng)關(guān)注好吧啦網(wǎng)其它相關(guān)文章！