文章目錄
- 二叉樹
- 樹的概念及結構
- 樹的概念
- ==注意：樹形結構中，子樹之間不能有交集，否則就不是樹形結構==
- 如何表示樹呢（其他方法不說了最近很忙，直接玩最牛逼的方法）
- 二叉樹概念及結構
- 概念
- 特殊的二叉樹：
- 滿二叉樹
- 完全二叉樹
- 二叉樹的性質
- 還有明天定時再發 略略略[主要是為了偷塔哈哈哈]
二叉樹
樹的概念及結構
樹的概念
樹是一種非線性的資料結構，它是由n（n>=0）個有限結點組成一個具有層次關系的集合，把它叫做樹是因
為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的，
- 有一個特殊的結點，稱為根結點，根節點沒有前驅結點
- 除根節點外，其余結點被分成M(M>0)個互不相交的集合T1、T2、……、Tm，其中每一個集合Ti(1<= i
<= m)又是一棵結構與樹類似的子樹，每棵子樹的根結點有且只有一個前驅，可以有0個或多個后繼 - 因此，樹是遞回定義的，
注意：樹形結構中，子樹之間不能有交集，否則就不是樹形結構
任何樹都被分成根和子樹（子樹也可能是空樹）
**節點的度：**一個節點含有的子樹的個數稱為該節點的度； 如上圖：A的度為6
葉節點或終端節點：度為0的節點稱為葉節點； 如上圖：B、C、H、I…等節點為葉節點
非終端節點或分支節點：度不為0的節點； 如上圖：D、E、F、G…等節點為分支節點
**雙親節點或父節點：**若一個節點含有子節點，則這個節點稱為其子節點的父節點； 如上圖：A是B的父節點
**孩子節點或子節點：**一個節點含有的子樹的根節點稱為該節點的子節點； 如上圖：B是A的孩子節點
**兄弟節點：**具有相同父節點的節點互稱為兄弟節點； 如上圖：B、C是兄弟節點
**樹的度：**一棵樹中，最大的節點的度稱為樹的度； 如上圖：樹的度為6
**節點的層次：**從根開始定義起，根為第1層，根的子節點為第2層，以此類推；
樹的高度或深度：樹中節點的最大層次； 如上圖：樹的高度為4
**堂兄弟節點：**雙親在同一層的節點互為堂兄弟；如上圖：H、I互為兄弟節點
**節點的祖先：**從根到該節點所經分支上的所有節點；如上圖：A是所有節點的祖先
**子孫：**以某節點為根的子樹中任一節點都稱為該節點的子孫，如上圖：所有節點都是A的子孫
**森林：**由m（m>0）棵互不相交的樹的集合稱為森林；
如何表示樹呢（其他方法不說了最近很忙，直接玩最牛逼的方法）
左孩子右兄弟表示法
二叉樹概念及結構
概念
一棵二叉樹是結點的一個有限集合，該集合:
- 或者為空
- 由一個根節點加上兩棵別稱為左子樹和右子樹的二叉樹組成
- 二叉樹不存在度大于2的結點 度最大為2
- 二叉樹的子樹有左右之分，次序不能顛倒，因此二叉樹是有序樹
注意：對于任意的二叉樹都是由以下幾種情況復合而成的：
特殊的二叉樹：
滿二叉樹
一個二叉樹，如果每一個層的結點數都達到最大值，則這個二叉樹就是滿二叉樹，也就是說，如果一個二叉樹的層數為K，且結點總數是 2k-1，則它就是滿二叉樹，
完全二叉樹
完全二叉樹是效率很高的資料結構，完全二叉樹是由滿二叉樹而引出來的，對于深度為K的，有n個結點的二叉樹，當且僅當其每一個結點都與深度為K的滿二叉樹中編號從1至n的結點一一對應時稱之為完全二叉樹， 要注意的是滿二叉樹是一種特殊的完全二叉樹，
二叉樹的性質
- 若規定根節點的層數為1，則一棵非空二叉樹的第i層上最多有2(i-1) 個結點.
- 若規定根節點的層數為1，則深度為h的二叉樹的最大結點數(就是滿二叉樹的時候)是2h-1.
- 對任何一棵二叉樹, 如果度為0其葉結點個數為n0 , 度為2的分支結點個數為n2 ,則有n0 ＝ n2＋1（度為0的永遠比度為2的多一個）
- 若規定根節點的層數為1，具有n個結點的滿二叉樹的深度，h=log2(n+1) . (ps： 是log2(n+1)以2為底，n+1為對數)
- 對于具有n個結點的完全二叉樹，如果按照從上至下從左至右的陣列順序對所有節點==從0開始編號，==則對于序號為i的結點有：
? 1.若i>0，i位置節點的雙親序號：(i-1)/2；i=0，i為根節點編號，無雙親節點
? 2.若2i+1<n，左孩子序號：2i+1，2i+1>=n否則無左孩子
? 3.若2i+2<n，右孩子序號：2i+2，2i+2>=n否則無右孩子
還有明天定時再發 略略略[主要是為了偷塔哈哈哈]
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/350944.html
標籤：其他
上一篇：Linux權限
下一篇：IP協議資料報格式詳解