1、定義

1)非線性結構，每個元素可以有多個前驅和后繼。

2)樹是n(n>=0)個元素的集合。

n=0時，稱為空樹。

樹只有一個特殊的沒有前驅的元素，稱為樹的根root。

樹中除了根節點外，其余元素只能有一個前驅，可以有零個或者多個后繼。

2、遞歸定義

樹T是n(n>=0)個元素的集合，n=0時，稱為空樹。

有且只有一個特殊元素根，剩余元素都可以被劃分為m個互不相交的集合T1、T2、T3、.....、Tm，而每個元素都是樹，稱為T的子樹。

子樹也有自己的根。

3、樹的概念

結點：樹中的數據元素。

結點的度degree：結點擁有子樹的樹木稱為度。記作d(v)。

葉子結點：結點度為0，稱為葉子結點leaf、終端結點、末端結點。

分支結點：:結點的度不為0，稱為非終端結點或分支結點。

分支：結點之間的關系

內部結點：除了根結點外的分支結點，不包括子結點。

樹的度是樹內各結點的度的最大值。D的結點度最大為3，樹的度數就是3.

孩子結點：結點的子樹的根結點成為該結點的孩子。

雙親結點：一個結點是它各子樹的根結點的雙親。

兄弟結點：具有相同雙親結點的結點：

祖先結點：祖先結點：從根結點到該結點所經分支上所有的結點。Ａ、Ｂ、Ｄ都是Ｇ的祖先結點。

子孫結點：結點的所有子樹上的結點都是該結點的子孫》Ｂ的子孫是ＤＧＨＩ

結點的層次：根結點為第一層，根的孩子為第二層，依次類推，記作Ｌ(ｖ)

樹的深度(高度Ｄepth)：樹的層次的最大值，上圖的樹深度為４

堂兄弟：雙親的同一層的結點

有序樹：結點的子樹是有順序的(兄弟有大小，有先后次序)，不能交換。

無序樹:結點的子樹是有無序的，可以交換。

路徑：樹中的k個結點n1、n2、....、nk。滿足ni是n(i+1)的雙親，成為你到nk的一條路徑。就是一條線串下來的，前一個都是后一個的父(前驅)結點。? 路徑就是一串從上到下：a到g。

路徑長度=路徑上的結點樹-1，也是分支樹。長度就是-1.

森林：m(m》=0)棵不相交的樹的集合，對于結點而言，其樹的集合就是森林。A的結點的2棵子樹的集合就是森林。

4、樹的特點

唯一的根

子樹不相交

除了根以外。每個元素只能有一個前驅，可以有零個或者多個后繼。

根結點就沒有雙親結點(前驅)，葉子結點沒有孩子結點(后繼)

Vi是vj的雙親，則L(vi)=L(vi)-1，也就是雙親比孩子結點的層次小1.

堂兄弟的雙親不一定是兄弟關系。

5、二叉樹

1)每個結點最多兩棵子樹。(二叉樹不存在度數大于2的結點)

是有序樹，左子樹，右子樹是順序的，不能交換次序。

即使某個結點只有一個結點，也要確定其為左子樹還是右子樹。

2)二叉樹的五種基本形態。

空二叉樹

只有一個根結點

根結點只有左子樹

根結點只有右子樹

根結點左右都有子樹。

3)斜樹：

左斜樹，所有結點都在左結點。

右斜樹，所有結點都在右結點。

4)滿二叉樹

一顆二叉樹的所有分支結點都存在左子樹和右子樹，并且所有葉子結點只是存在最下面一層。

K為深度 ，結點總數為(2**k)-1

5)???? 完全二叉樹：(滿二叉樹是完全二叉樹，但是完全二叉樹不一定是滿二叉樹。)

若二叉樹的深度為k,二叉樹的層數從1到k-1層的結點樹都達到了最大數,在第k層的所有的結點都集中在左邊,這就是完全二叉樹.

完全二叉樹由滿二叉樹引出.

K為深度(1<=k<=n\),則結點總數的最大值為2**k-1,當達到最大值的時候就是滿二叉樹.

6)二叉樹的性質：

性質1：在二叉樹的第i層上至多有2^i -1個結點(i》=1) #例如第二層有兩個結點.

性質2：深度為k的二叉樹,至多有2**k-1個結點,一層:2-1?? 二層 4-1=1+2+3? 三層8-1=1+2+4=7

性質3：對任何一顆二叉樹T,如果其終端結點樹為n0,度數為2的結點為n2,則有n0=n2+1(就是葉子樹結點的樹-1就等于度數為2的結點樹.

證明:總結點數n=n1+n2+n3.

一棵樹的分支數為n-1，因為除了根結點外。其余結點都有一個分支,n0+n1+n2-1.

分支數還等于n0*0+n1*1+n2*2,n2是2分支結點所以乘以2,2*n2+n1.

可得2*n2+n1=n0+n1+n2-1=>n2=n0-1

其它性質：

高度為k的二叉樹,至少有k個結點

含有n(n>=1)的結點的二叉樹高度至多為n。

含有n(n>=1)的結點樹的二叉樹的高度至多為n，最小為math.ceil(log2(n+1))，不小于對數值的最小整數， 向上取整。層次樹是取整.

如果是8個結點,向上取整為4,為4層.

性質4:具有n個結點的完全二叉樹的深度為int(log.n)+1或者math.ceil(log2(n+1))

性質5:如果有一顆n個結點的完全二叉樹(深度為性質4),結點按照層序編號.

如果i=1,則結點i是二叉樹的根,無雙親,如果i>1,則雙親是int(i/2)，向下取整。就是子結點的編號整除2得到的就是父結點的編號，父結點如果是i，那么左孩子的結點就是2i，右結點是2i+1.

如果2i》n，則結點i無左孩子，即結點為葉子結點，否則其左孩子結點存在編號為2i

如果2i+1》n，則結點i無右孩子，不能說明結點i沒有左孩子，否則右孩子的結點存在編號為2i+1.

總結

以上是生活随笔為你收集整理的python 树_Python树的概念的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。