樹和二叉樹
什么是樹結構
樹形結構是一類重要的非線性結構,樹形結構中結點之間具有分支,并具有層次結構關系,類似于自然界中的樹; 生活中也大量存在,如家譜,行政組織結構都可以用樹形象的表示;
既然自然界中存在這種結構的資料,那計算機中也需要相應的資料結構來存盤; 在計算機領域樹結構也有著廣泛的應用,如編譯程式中使用樹表示語法結構,資料庫中用樹(索引)來組織資料,分析演算法行為時可用樹描述其指向程序;
樹的定義
樹是n (n>=0)個結點的有限集,記做T;當結點數n為0時稱為空樹
且滿足以下特性:
當結點數n大于0時,有且僅有一個特定的根結點;
除根結點外的其余結點可分為m(m>=0)個互不相交的子集,T1.T2....Tn,其中每個子集Ti又是一棵樹,稱之為子樹
任意一棵樹的結點數=分支數+1
樹的邏輯表示
常見的表示法有如下四種:
-
一般表示法
-
文氏圖法
-
凹入表示法
-
嵌套括號法:
(根(子樹,子樹,子樹))
(A(B(E,F),C,D(G)))
其中第1,4兩種最為常見;
樹的相關術語
-
結點
- 由一個資料元素及若干個指向其他結點的分支組成
-
度
- 結點的度: 該結點的子樹數(分支數==子結點數)
- 樹的度: 樹中所有結點的度的最大值
-
葉子結點(終端結點)
- 度為0的結點(沒有孩子)
-
分支結點(非終端結點)
- 度不為0的結點(有孩子)
-
孩子(子結點)
- 結點的子樹的根結點,稱為該結點的孩子
-
雙親(父結點)
- 一個結點是該結點所有子結點的雙親
-
祖先
- 結點的祖先是指從根結點到該結點的一條路徑上的所有結點
-
子孫
- 從某結點到葉結點的路徑上所有結點(包括葉結點),稱為該結點的子孫
-
兄弟
- 具有相同父結點的結點
-
結點的層次(計算方式)
- 從根算起,根為第一層,根結點的所有孩子都在第二層; L層的所有結點的孩子都在L+1層;
-
堂兄弟
- 其雙親不同但處于同一層的結點
-
樹的深度(高度)
- 樹中結點的最大層次;
-
有序/無序樹
- 樹中各個節點的子樹從左到右是有次序的(升序/降序),不能互換,稱為有序樹
- 樹中各個節點的子樹從是無次序的可以互換,稱為無序樹
-
森林
- 是m(m>=0)棵樹的集合
樹的基本運算
- 求根Root(T):求樹T的根結點;
- 求雙親Parent(T,X):求結點X在樹T上的雙親; 若X是樹T的根或X不在T上，則結果為一特殊 標志(NULL);
- 求孩子Child(T,X,i):求樹T上結點X的第i個孩子 結點;若X不在T上或X沒有第i個孩子，則結 果為一特殊標志(NULL);
- 建樹Create(X,T1,...,Tk),k>1:建立一棵以X為根， 以T1,...,Tk為第1,...,k棵子樹的樹;
- 剪枝Delete(T,X,i):洗掉樹T上結點X的第i棵子 樹;若T無第i棵子樹，則為空操作;
- 遍歷TraverseTree(T):遍歷樹，即訪問樹中每個 結點，且每個結點僅被訪問一次，
二叉樹
二叉樹是樹的一種特殊情形,二叉樹在樹結構的應用中起著非常重要的作用,因為二叉樹有許多良好的性質和簡單的物理表示,且任何樹都可以與二叉樹相互轉換,這極大降低了樹的存盤結構及其運算復雜度;
二叉樹的定義
二叉樹是由n(n>=0)個節點組成的有限集合,當結點數n為0時稱為空二叉樹,當結點數n>0時,每個節點最多有兩個子樹,稱為左子樹和右子樹
特點
-
每個節點最多只能有兩個子樹
-
子樹有左右之分,且次序不能顛倒
-
即使只有一個子樹也必須明確左右,這是與樹最主要的差別
-
二叉樹與樹的對比:
五種基本形態
a. 空二叉樹
b. 左右子樹均為空的二叉樹
c. 右子樹為空的二叉樹
d. 左子樹為空的二叉樹
b. 左右子樹都非空的二叉樹
二叉樹的性質(*)
二叉樹之所以重要,因其具備以下5個重要特性
1.在二叉樹的第i(i>=1)層上最多有2^(i-1)個結點
根據該性質可通過層數計算該層結點數量
2.深度為k(k>=1)的二叉樹中最多有(2^k)-1
根據該性質可通過深度計算總節點數
3.任意一顆二叉樹,如果其葉子結點數為n0,度為2的節點數為n2,則n0 = n2 + 1
? 證明:
? 度為0的結點記為n0,度為1的結點記為n1,度為2的結點記為n2
? 設總結點數為1,即只有根節點,此時滿足n0 = n2+1;
? 若有總結點數為n的二叉樹,設n = k時滿足n0 = n2+1;
? 當總節點數n=k+1,即增加一個新節點,設為s,
? 若新節點s的的父節點為葉子結點(無子節點),則增加后葉子數n0不變,n2也不變,此時仍滿足n0 = n2+1
? 若新節點s的的父節點為有一個孩子的結點,則增加后葉子數n0 = n0+1,n2=n2+1,此時仍滿足n0 = n2+1,
? 故n=任意值均滿足n0 = n2+1
4.具有n個節點的完全二叉樹的深度為floor(log2n)+1
意為:以2為底n的對數向下取整后+1
根據該性質對于完全二叉樹,可通過結點數求樹的深度
5.若對有n個節點的完全二叉樹的結點從1開始按層編號(從1層到最后一層,每層從左到右)則樹中任意節點i(1<=i<=n)具有以下特性:
- 若i = 1,則結點i是二叉樹的根,無雙親節點
- 若i > 1,則i結點的雙親Parent是編號為floor(i/2)的節點
- 如果2*i<=n,結點i的左孩子節點編號為
2 * i,否則結點i無左孩子節點,且i為葉子節點 - 如果2*i+1<=n,結點i的右孩子節點編號為
2 * i + 1,否則結點i無右孩子節點
根據該性質,可方便的判斷節點是否是根節點,求父節點,求左/右子節點,判斷是否為葉子結點
二叉樹的分類
-
滿二叉樹
深度為k(k>=1),且有(2^k)-1個結點的二叉樹.
即:葉子結點的上一層中所有結點的度均為2的二叉樹為滿二叉樹,
-
完全二叉樹
深度為K的二叉樹中,K-1層是滿的,且K層結點是左連續的(結點編號是連續的),如圖:
即:倒數第二層是滿的,且最后一層結點是連續的;
滿二叉樹是完全二叉樹的特殊情形
二叉樹的基本運算
-
初始化Initial(BT):建立一顆空二叉樹
-
求雙親Parent(BT,X):求二叉樹BT上節點X的雙親節點,若X為BT的根或X不在BT上,結果為NULL;
-
求左孩子LChild(BT,X),右孩子RChild(BT,X):求二叉樹BT上結點X的左/右孩子; 若X為葉子節點或X不在BT上,結果為NULL;
-
建二叉樹Create(BT):建立一棵二叉樹BT
-
遍歷
每個節點被訪問一次,且每個節點僅訪問一次,有四種不同的遍歷方式
- 先序遍歷(根左右)
- 中序遍歷(左根右)
- 后續遍歷(左右根)
- 層次遍歷(按層次)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/51545.html
標籤：其他
上一篇：求專門接收驗證碼平臺。