前言

本文的內容是數據結構中二叉樹部分最基礎的，之所以寫一下主要是為了方便刷題的時候，能夠在自己電腦上很快的使用這種小的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，如下圖：

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

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

在遞歸構建二叉樹的任務中，我們要做到不糾結于每一層，而是只關注該層在做什么，這樣，對于下圖左側的樹，我們就可以看作為右側的樹，它只有自己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創建二叉樹的資料請關注好吧啦網其它相關文章！