Python中的?樹和二叉樹-創(chuàng)新互聯(lián)

創(chuàng)新互聯(lián)www.cdcxhl.cn八線動態(tài)BGP香港云服務(wù)器提供商，新人活動買多久送多久，劃算不套路！

創(chuàng)新互聯(lián)成立10余年來，這條路我們正越走越好，積累了技術(shù)與客戶資源，形成了良好的口碑。為客戶提供做網(wǎng)站、成都網(wǎng)站建設(shè)、網(wǎng)站策劃、網(wǎng)頁設(shè)計、域名與空間、網(wǎng)絡(luò)營銷、VI設(shè)計、網(wǎng)站改版、漏洞修補等服務(wù)。網(wǎng)站是否美觀、功能強大、用戶體驗好、性價比高、打開快等等，這些對于網(wǎng)站建設(shè)都非常重要，創(chuàng)新互聯(lián)通過對建站技術(shù)性的掌握、對創(chuàng)意設(shè)計的研究為客戶提供一站式互聯(lián)網(wǎng)解決方案，攜手廣大客戶，共同發(fā)展進步。

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

什么是樹？

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

它是由n(n>=1)個有限節(jié)點組成一個具有層次關(guān)系的集合。把它叫做“樹”是因為它看起來像一棵倒掛的樹,也就是說它是根朝上,而葉朝下的。它具有以下的特點:

每個節(jié)點有零個或多個子節(jié)點;

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

每一個非根節(jié)點有且只有一個父節(jié)點;

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

樹的術(shù)語：

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

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

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

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

兄弟節(jié)點： 具有同一個父節(jié)點的節(jié)點稱為兄弟節(jié)點

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

二叉樹：

二叉樹是樹的特殊一種，具有如下特點：

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

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

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

二叉樹的性質(zhì)：

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

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

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

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

特殊的二叉樹

滿二叉樹

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

滿二叉樹的特點：

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

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

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

完全二叉樹

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

完全二叉樹的特點：

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

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

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

小例題：

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

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

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

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

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

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

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

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

驗證：

第一條：

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

第二條：

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

第三條：

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

上述就是小編為大家分享的Python中的樹和二叉樹了，如果剛好有類似的疑惑，不妨參照上述分析進行理解。如果想知道更多相關(guān)知識，歡迎關(guān)注創(chuàng)新互聯(lián)-成都網(wǎng)站建設(shè)公司行業(yè)資訊頻道。

網(wǎng)站名稱：Python中的?樹和二叉樹-創(chuàng)新互聯(lián)
當前URL：http://bm7419.com/article28/dpcocp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供域名注冊、服務(wù)器托管、電子商務(wù)、網(wǎng)站維護、App開發(fā)、全網(wǎng)營銷推廣

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)