主頁 > 知識庫 > 如何在Python中創(chuàng)建二叉樹

如何在Python中創(chuàng)建二叉樹

熱門標(biāo)簽:千陽自動外呼系統(tǒng) 平頂山外呼系統(tǒng)免費 在哪里辦理400電話號碼 工廠智能電話機器人 西藏智能外呼系統(tǒng)五星服務(wù) 江蘇客服外呼系統(tǒng)廠家 清遠360地圖標(biāo)注方法 400電話申請服務(wù)商選什么 原裝電話機器人

前言

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

二叉樹節(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. 在我們的任務(wù)中,終止條件是什么?
  2. 在我們的任務(wù)中,本次遞歸要干嘛?
  3. 在我們的任務(wù)中,本次遞歸要返回給上一次遞歸的是啥?

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

這樣我們需要注意的那三個問題的回答自然就有了(做遞歸問題,心中要想著怎么回答這三個問題):

  • 在我們的任務(wù)中,終止條件是什么?

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

  • 在我們的任務(wù)中,本次遞歸要干嘛?

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

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

[當(dāng)然是返回一個本層構(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)文章!

您可能感興趣的文章:
  • Python對稱的二叉樹多種思路實現(xiàn)方法
  • python3實現(xiàn)在二叉樹中找出和為某一值的所有路徑(推薦)
  • Python實現(xiàn)二叉樹的最小深度的兩種方法
  • Python3 翻轉(zhuǎn)二叉樹的實現(xiàn)
  • Python3實現(xiàn)二叉樹的最大深度
  • Python3 合并二叉樹的實現(xiàn)
  • 用Python實現(xiàn)二叉樹、二叉樹非遞歸遍歷及繪制的例子
  • 基于python二叉樹的構(gòu)造和打印例子
  • Python 二叉樹的層序建立與三種遍歷實現(xiàn)詳解
  • python3實現(xiàn)二叉樹的遍歷與遞歸算法解析(小結(jié))

標(biāo)簽:天水 隨州 白城 安慶 西安 日照 股票 錦州

巨人網(wǎng)絡(luò)通訊聲明:本文標(biāo)題《如何在Python中創(chuàng)建二叉樹》,本文關(guān)鍵詞  如,何在,Python,中,創(chuàng)建,二叉,;如發(fā)現(xiàn)本文內(nèi)容存在版權(quán)問題,煩請?zhí)峁┫嚓P(guān)信息告之我們,我們將及時溝通與處理。本站內(nèi)容系統(tǒng)采集于網(wǎng)絡(luò),涉及言論、版權(quán)與本站無關(guān)。
  • 相關(guān)文章
  • 下面列出與本文章《如何在Python中創(chuàng)建二叉樹》相關(guān)的同類信息!
  • 本頁收集關(guān)于如何在Python中創(chuàng)建二叉樹的相關(guān)信息資訊供網(wǎng)民參考!
  • 推薦文章