如何在Python中創建二叉樹

前言

本文的內容是數據結構中二叉樹部分最基礎的，之所以寫一下主要是為瞭方便刷題的時候，能夠在自己電腦上很快的使用這種小的demo進行復雜的練習。

二叉樹節點定義

二叉樹的節點定義如下：

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

遞歸構建二叉樹

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

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

既然是使用遞歸的方法構建二叉樹，主要需要理解遞歸的過程，這種思路將在之後的很多地方用的到。
要知道如何遞歸的構建二叉樹，我們不能糾結於遞歸每一層到底幹瞭什麼，這樣就會一直糾結下去（所有的遞歸問題都一樣）。我們需要註意的是：

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

在遞歸構建二叉樹的任務中，我們要做到不糾結於每一層，而是隻關註該層在做什麼，這樣，對於下圖左側的樹，我們就可以看作為右側的樹，它隻有自己a (a)，左子樹B (bcd)和右子樹C (e)。

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

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

[給我們的字符用完，也就不需要再創建節點瞭]

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

[本次遞歸要創建三個節點，一個根節點，一個左節點，一個右節點]

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

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

def Creat_Tree(Root,val):
  if len(vals)==0:#終止條件：val用完瞭
    return Root
  if vals[0]!='#':#本層需要幹的就是構建Root、Root.lchild、Root.rchild三個節點。
    Root = TreeNode(vals[0])
    vals.pop(0)
    Root.lchild = Creat_Tree(Root.lchild,val)
    Root.rchild = Creat_Tree(Root.rchild,val)
    return Root#本次遞歸要返回給上一次的本層構造好的樹的根節點
  else:
    Root=None
    vals.pop(0)
    return Root#本次遞歸要返回給上一次的本層構造好的樹的根節點

看懂瞭上述內容，構建一棵我們想象的二叉樹就很簡單瞭，隻要輸入一個我們心目中前序遍歷擴展的二叉樹序列即可：

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

以上就是如何在Python中創建二叉樹的詳細內容，更多關於Python創建二叉樹的資料請關註WalkonNet其它相關文章！

推薦閱讀：

None Found