建站
咨詢
售后
建站咨詢
新聞中心
樹與二叉樹
在了解二叉樹之前，我們要先了解樹的一些概念，方便我們對二叉樹的理解。
什么是樹？
樹(英語:tree)是一種抽象數(shù)據(jù)類型(ADT)或是實作這種抽象數(shù)據(jù)類型的數(shù)據(jù)結構,用來模擬具有樹狀結構性質的數(shù)據(jù)集合。
它是由n(n>=1)個有限節(jié)點組成一個具有層次關系的集合。把它叫做“樹”是因為它看起來像一棵倒掛的樹,也就是說它是根朝上,而葉朝下的。它具有以下的特點:
每個節(jié)點有零個或多個子節(jié)點;
沒有父節(jié)點的節(jié)點稱為根節(jié)點;
每一個非根節(jié)點有且只有一個父節(jié)點;
除了根節(jié)點外,每個子節(jié)點可以分為多個不相交的子樹;
樹的術語：
節(jié)點的度: 一個節(jié)點含有的子樹的個數(shù)稱為該節(jié)點的度;
樹的度: 一棵樹中,節(jié)點的度稱為樹的度;
根結點： 樹的最頂端的節(jié)點，繼續(xù)往下分為子節(jié)點
父節(jié)點： 子節(jié)點的上一層為父節(jié)點
兄弟節(jié)點： 具有同一個父節(jié)點的節(jié)點稱為兄弟節(jié)點
葉子節(jié)點/終端節(jié)點： 不再有子節(jié)點的節(jié)點為葉子節(jié)點
二叉樹：
二叉樹是樹的特殊一種，具有如下特點：
每個節(jié)點最多有兩個子樹，節(jié)點的度為2
左子樹和右子樹是有順序的，次序不能顛倒
即是某節(jié)點只有一個子樹，也要區(qū)分左右子樹
二叉樹的性質：
在非空二叉樹的第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é)點的二叉樹，完全二叉樹的深度最?。M二叉樹也對）
小例題：
某完全二叉樹共有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。
完全二叉樹的性質：
具有n個節(jié)點的完全二叉樹的深度為log2n+1。log2n結果取整數(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時，比如結點為7，他的雙親就是7/2= 3；結點9雙親為4.
第二條：
結點6,62 = 12>10，所以結點6無左孩子，是葉子結點。結點5，52 = 10，左孩子是10,結點4，為8.
第三條：
結點5，2*5+1>10,沒有右孩子，結點4，則有右孩子。
更多python相關知識，請移步Python視頻教程繼續(xù)學習！！
分享名稱：創(chuàng)新互聯(lián)Python教程：Python中的樹你知道嗎？
轉載注明：http://www.dlmjj.cn/article/djdidcc.html
