前言

本文的內(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)題都一樣）。我們需要注意的是：

1. 在我們的任務(wù)中，終止條件是什么？
2. 在我們的任務(wù)中，本次遞歸要干嘛？
3. 在我們的任務(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)注腳本之家其它相關(guān)文章！

最新評(píng)論