前言

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

二叉樹節(jié)點定義

二叉樹的節(jié)點定義如下：

class TreeNode():#二叉樹節(jié)點
  def __init__(self,val,lchild=None,rchild=None):
    self.val=val		#二叉樹的節(jié)點值
    self.lchild=lchild		#左孩子
    self.rchild=rchild		#右孩子

遞歸構(gòu)建二叉樹

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

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

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

1. 在我們的任務中，終止條件是什么？
2. 在我們的任務中，本次遞歸要干嘛？
3. 在我們的任務中，本次遞歸要返回給上一次遞歸的是啥？
   

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

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

• 在我們的任務中，終止條件是什么？
  

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

• 在我們的任務中，本次遞歸要干嘛？

[本次遞歸要創(chuàng)建三個節(jié)點，一個根節(jié)點，一個左節(jié)點，一個右節(jié)點]

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

[當然是返回一個本層構(gòu)造好的樹的根節(jié)點]
理解了上述三個問題的回答，遞歸的代碼自然可以寫出：

def Creat_Tree(Root,val):
  if len(vals)==0:#終止條件：val用完了
    return Root
  if vals[0]!='#':#本層需要干的就是構(gòu)建Root、Root.lchild、Root.rchild三個節(jié)點。
    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)造好的樹的根節(jié)點
  else:
    Root=None
    vals.pop(0)
    return Root#本次遞歸要返回給上一次的本層構(gòu)造好的樹的根節(jié)點

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

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

以上就是如何在Python中創(chuàng)建二叉樹的詳細內(nèi)容，更多關(guān)于Python創(chuàng)建二叉樹的資料請關(guān)注腳本之家其它相關(guān)文章！

最新評論