建站
咨詢
售后
建站咨詢
新聞中心
樹與二叉樹
在了解二叉樹之前，我們要先了解樹的一些概念，方便我們對二叉樹的理解。
什么是樹？
樹(英語: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)的二叉樹，完全二叉樹的深度最?。M二叉樹也對）
小例題：
某完全二叉樹共有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)按層次序編號，對任一層的節(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相關(guān)知識，請移步Python視頻教程繼續(xù)學(xué)習(xí)??！
網(wǎng)站題目：創(chuàng)新互聯(lián)Python教程：Python中的樹你知道嗎？
URL鏈接：http://www.5511xx.com/article/djdidcc.html
