Python中的?樹和二叉樹

這期內(nèi)容當(dāng)中小編將會(huì)給大家?guī)碛嘘P(guān)Python中的樹和二叉樹，文章內(nèi)容豐富且以專業(yè)的角度為大家分析和敘述，閱讀完這篇文章希望大家可以有所收獲。

什么是樹？

樹(英語:tree)是一種抽象數(shù)據(jù)類型(ADT)或是實(shí)作這種抽象數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu),用來模擬具有樹狀結(jié)構(gòu)性質(zhì)的數(shù)據(jù)集合。

它是由n(n>=1)個(gè)有限節(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合。把它叫做“樹”是因?yàn)樗雌饋硐褚豢玫箳斓臉?也就是說它是根朝上,而葉朝下的。它具有以下的特點(diǎn):

每個(gè)節(jié)點(diǎn)有零個(gè)或多個(gè)子節(jié)點(diǎn);

沒有父節(jié)點(diǎn)的節(jié)點(diǎn)稱為根節(jié)點(diǎn);

每一個(gè)非根節(jié)點(diǎn)有且只有一個(gè)父節(jié)點(diǎn);

除了根節(jié)點(diǎn)外,每個(gè)子節(jié)點(diǎn)可以分為多個(gè)不相交的子樹;

樹的術(shù)語：

節(jié)點(diǎn)的度: 一個(gè)節(jié)點(diǎn)含有的子樹的個(gè)數(shù)稱為該節(jié)點(diǎn)的度;

樹的度: 一棵樹中,最大的節(jié)點(diǎn)的度稱為樹的度;

根結(jié)點(diǎn)： 樹的最頂端的節(jié)點(diǎn)，繼續(xù)往下分為子節(jié)點(diǎn)

父節(jié)點(diǎn)： 子節(jié)點(diǎn)的上一層為父節(jié)點(diǎn)

兄弟節(jié)點(diǎn)： 具有同一個(gè)父節(jié)點(diǎn)的節(jié)點(diǎn)稱為兄弟節(jié)點(diǎn)

葉子節(jié)點(diǎn)/終端節(jié)點(diǎn)： 不再有子節(jié)點(diǎn)的節(jié)點(diǎn)為葉子節(jié)點(diǎn)

二叉樹：

二叉樹是樹的特殊一種，具有如下特點(diǎn)：

每個(gè)節(jié)點(diǎn)最多有兩個(gè)子樹，節(jié)點(diǎn)的度最大為2

左子樹和右子樹是有順序的，次序不能顛倒

即是某節(jié)點(diǎn)只有一個(gè)子樹，也要區(qū)分左右子樹

二叉樹的性質(zhì)：

在非空二叉樹的第i層，最多有2i-1個(gè)節(jié)點(diǎn)(i>=1)

在深度為K的二叉樹上最多有2k-1個(gè)節(jié)點(diǎn)(k>.1)

對于任意一個(gè)非空的二叉樹，如果葉子節(jié)點(diǎn)個(gè)數(shù)為n0，度數(shù)為2的節(jié)點(diǎn)數(shù)為n2，則有n0=n2+1

推倒過程：在一棵二叉樹中，除了葉子節(jié)點(diǎn)（度為0）外，就剩下度為2(n2)和度為1(n1)的節(jié)點(diǎn)了。則樹的節(jié)點(diǎn)總數(shù)為T = n0 + n1 + n2；在二叉樹中節(jié)點(diǎn)總數(shù)為T，而連線總數(shù)為T-1 = 2*n2 + n1，所以就有：n0 + n1 + n2 - 1 = 2 *n2 + n1，得到n0=n2+1。

特殊的二叉樹

滿二叉樹

在二叉樹中除了葉子節(jié)點(diǎn)，其他所有節(jié)點(diǎn)的度為2，且所有的葉子節(jié)點(diǎn)都在同一層上，這樣的二叉樹成為滿二叉樹。

滿二叉樹的特點(diǎn)：

葉子節(jié)點(diǎn)只能出現(xiàn)在最下一層

非葉子節(jié)點(diǎn)度數(shù)一定為2

在同樣深度的二叉樹中，滿二叉樹的節(jié)點(diǎn)個(gè)數(shù)最多，葉子節(jié)點(diǎn)數(shù)最多

完全二叉樹

如果二叉樹中除去最后一層葉子節(jié)點(diǎn)后為滿二叉樹，且最后一層的葉子節(jié)點(diǎn)依次從左到右分布，則這樣的二叉樹稱為完全二叉樹

完全二叉樹的特點(diǎn)：

葉子節(jié)點(diǎn)一般出現(xiàn)在最下一層，如果倒數(shù)第二層出現(xiàn)葉子節(jié)點(diǎn)，一定出現(xiàn)在右部連續(xù)位置

最下層葉子節(jié)點(diǎn)一定集中在左部連續(xù)位置

同樣節(jié)點(diǎn)的二叉樹，完全二叉樹的深度最小（滿二叉樹也對）

小例題：

某完全二叉樹共有200個(gè)節(jié)點(diǎn)，該二叉樹中共有（）個(gè)葉子節(jié)點(diǎn)？

解：n0 + n1 + n2 = 200， 其中n0 = n2 + 1，n1 = 0或者1 （n1=1，出現(xiàn)在最下一層節(jié)點(diǎn)數(shù)為奇數(shù)，最下一層節(jié)點(diǎn)數(shù)為偶數(shù)，則n1=0）， 因?yàn)閚0為整數(shù)，所以最后算得n0 = 100。

完全二叉樹的性質(zhì)：

具有n個(gè)節(jié)點(diǎn)的完全二叉樹的深度為log2n+1。log2n結(jié)果取整數(shù)部分。

如果有一棵有n個(gè)節(jié)點(diǎn)的完全二叉樹的節(jié)點(diǎn)按層次序編號(hào)，對任一層的節(jié)點(diǎn)i(1 <= i <= n)

1. 如果i=1，則節(jié)點(diǎn)是二叉樹的根，無父節(jié)點(diǎn)，如果i>1,則其父節(jié)點(diǎn)為i/2，向下取整

2. 如果2*1>n，那么節(jié)點(diǎn)i沒有左孩子，否則其左孩子為2i

3. 如果2i+1>n那么節(jié)點(diǎn)沒有右孩子，否則右孩子為2i+1

驗(yàn)證：

第一條：

當(dāng)i=1時(shí)，為根節(jié)點(diǎn)。當(dāng)i>1時(shí)，比如結(jié)點(diǎn)為7，他的雙親就是7/2= 3；結(jié)點(diǎn)9雙親為4.

第二條：

結(jié)點(diǎn)6,62 = 12>10，所以結(jié)點(diǎn)6無左孩子，是葉子結(jié)點(diǎn)。結(jié)點(diǎn)5，52 = 10，左孩子是10,結(jié)點(diǎn)4，為8.

第三條：

結(jié)點(diǎn)5，2*5+1>10,沒有右孩子，結(jié)點(diǎn)4，則有右孩子。

上述就是小編為大家分享的Python中的樹和二叉樹了，如果剛好有類似的疑惑，不妨參照上述分析進(jìn)行理解。如果想知道更多相關(guān)知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道。