創(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)站改版、漏洞修補(bǔ)等服務(wù)。網(wǎng)站是否美觀、功能強(qiáng)大、用戶體驗(yàn)好、性價比高、打開快等等,這些對于網(wǎng)站建設(shè)都非常重要,創(chuàng)新互聯(lián)通過對建站技術(shù)性的掌握、對創(chuàng)意設(shè)計的研究為客戶提供一站式互聯(lián)網(wǎng)解決方案,攜手廣大客戶,共同發(fā)展進(jìn)步。這期內(nèi)容當(dāng)中小編將會給大家?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)個有限節(jié)點(diǎn)組成一個具有層次關(guān)系的集合。把它叫做“樹”是因?yàn)樗雌饋硐褚豢玫箳斓臉?也就是說它是根朝上,而葉朝下的。它具有以下的特點(diǎn):
每個節(jié)點(diǎn)有零個或多個子節(jié)點(diǎn);
沒有父節(jié)點(diǎn)的節(jié)點(diǎn)稱為根節(jié)點(diǎn);
每一個非根節(jié)點(diǎn)有且只有一個父節(jié)點(diǎn);
除了根節(jié)點(diǎn)外,每個子節(jié)點(diǎn)可以分為多個不相交的子樹;
樹的術(shù)語:
節(jié)點(diǎn)的度: 一個節(jié)點(diǎn)含有的子樹的個數(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): 具有同一個父節(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):
每個節(jié)點(diǎn)最多有兩個子樹,節(jié)點(diǎn)的度大為2
左子樹和右子樹是有順序的,次序不能顛倒
即是某節(jié)點(diǎn)只有一個子樹,也要區(qū)分左右子樹
二叉樹的性質(zhì):
在非空二叉樹的第i層,最多有2i-1個節(jié)點(diǎn)(i>=1)
在深度為K的二叉樹上最多有2k-1個節(jié)點(diǎn)(k>.1)
對于任意一個非空的二叉樹,如果葉子節(jié)點(diǎn)個數(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)個數(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個節(jié)點(diǎn),該二叉樹中共有()個葉子節(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個節(jié)點(diǎn)的完全二叉樹的深度為log2n+1。log2n結(jié)果取整數(shù)部分。
如果有一棵有n個節(jié)點(diǎn)的完全二叉樹的節(jié)點(diǎn)按層次序編號,對任一層的節(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時,為根節(jié)點(diǎn)。當(dāng)i>1時,比如結(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)知識,歡迎關(guān)注創(chuàng)新互聯(lián)-成都網(wǎng)站建設(shè)公司行業(yè)資訊頻道。