樹與樹的表示

目錄

* 一、什么是樹 <https://www.cnblogs.com/nickchen121/p/11485023.html#一什么是樹>
* 二、查找 <https://www.cnblogs.com/nickchen121/p/11485023.html#二查找>
* 2.1 靜態(tài)查找 <https://www.cnblogs.com/nickchen121/p/11485023.html#靜態(tài)查找>
* 2.1.1 方法1：順序查找 <https://www.cnblogs.com/nickchen121/p/11485023.html#方法1順序查找>
* 2.1.2 方法2：二分查找（Binary Search）
<https://www.cnblogs.com/nickchen121/p/11485023.html#方法2二分查找binary-search>
* 三、二分查找判定樹 <https://www.cnblogs.com/nickchen121/p/11485023.html#三二分查找判定樹>
* 四、樹的定義 <https://www.cnblogs.com/nickchen121/p/11485023.html#四樹的定義>
* 五、樹與非樹 <https://www.cnblogs.com/nickchen121/p/11485023.html#五樹與非樹>
* 5.1 非樹 <https://www.cnblogs.com/nickchen121/p/11485023.html#非樹>
* 5.2 樹 <https://www.cnblogs.com/nickchen121/p/11485023.html#樹>
* 六、樹的一些基本術(shù)語 <https://www.cnblogs.com/nickchen121/p/11485023.html#六樹的一些基本術(shù)語>
* 七、樹的表示 <https://www.cnblogs.com/nickchen121/p/11485023.html#七樹的表示>
* 7.1 樹的鏈表表示 <https://www.cnblogs.com/nickchen121/p/11485023.html#樹的鏈表表示>
* 7.2 樹的鏈表（兒子-兄弟）表示法
<https://www.cnblogs.com/nickchen121/p/11485023.html#樹的鏈表兒子-兄弟表示法>
一、什么是樹

客觀世界中許多事物存在層次關(guān)系

* 人類社會家譜
* 社會組織結(jié)構(gòu)
* 圖書信息管理
其中，人類社會家譜如下圖所示：



通過上述所說的分層次組織，能夠使我們在數(shù)據(jù)的管理上有更高的效率！那么，對于數(shù)據(jù)管理的基本操作——查找，我們?nèi)绾螌崿F(xiàn)有效率的查找呢？

二、查找

查找：根據(jù)某個給定關(guān)鍵字K，從集合R中找出關(guān)鍵字與K相同的記錄

靜態(tài)查找：集合中記錄是固定的，即對集合的操作沒有插入和刪除，只有查找

動態(tài)查找：集合中記錄是動態(tài)變化的，即對集合的操作既有查找，還可能發(fā)生插入和刪除（動態(tài)查找不在我們考慮范圍內(nèi)）

2.1 靜態(tài)查找

2.1.1 方法1：順序查找


/* c語言實現(xiàn) */ int SequentialSearch (StaticTable *Tbl, ElementType K) { //
在表Tbl[1]~Tb1[n]中查找關(guān)鍵字為K的數(shù)據(jù)元素 int i; Tbl->Element[0] = K; //
建立哨兵，即沒找到可以返回哨兵的索引0表示未找到 for (i = Tbl->Length; Tbl->Element[i] != K; i--); //
查找成功返回所在單元下標；不成功放回0 return i; }
順序查找算法的時間復雜度為O(n)

2.1.2 方法2：二分查找（Binary Search）

假設n個數(shù)據(jù)元素的關(guān)鍵字滿足有序（比如：小到大），即\(k_1<k_2<\cdots<k_n\)，并且是連續(xù)存放（數(shù)組），那么可以進行二分查找。

例：假設有13個數(shù)據(jù)元素，按關(guān)鍵字由小到大順序存放。二分查找關(guān)鍵字為444的數(shù)據(jù)元素過程如下圖：



仍然以上面13個數(shù)據(jù)元素構(gòu)成的有序線性表為例，二分查找關(guān)鍵字為43的數(shù)據(jù)元素如下圖：


/* c語言實現(xiàn) */ int BinarySearch (StaticTable *Tbl, ElementType K) { //
在表中Tbl中查找關(guān)鍵字為K的數(shù)據(jù)元素 int left, right, mid, NoFound = -1; left = 1; // 初始左邊界
right = Tbl->Length; // 初始右邊界 while (left <= right) { mid = (left + right) / 2;
// 計算中間元素坐標 if (K < Tbl->Element[mid]) right = mid - 1; // 調(diào)整右邊界 else if (K >
Tbl->Element[mid]) left = mid + 1; // 調(diào)整左邊界 else return mid; // 查找成功，返回數(shù)據(jù)元素的下標
} return NotFound; // 查找不成功，返回-1 }
二分查找算法具有對數(shù)的時間復雜度O(logN)

二分查找算法雖然解決了查找的時間復雜度問題，但是對于數(shù)據(jù)的插入和刪除確是O(n)的，因此有沒有一種數(shù)據(jù)結(jié)構(gòu)，既可以減少數(shù)據(jù)查找的時間復雜度，又可以
減少數(shù)據(jù)的插入和刪除的復雜度呢？

三、二分查找判定樹

除了使用上述兩個方法進行關(guān)鍵字的查找，我們還可以通過二叉樹這種數(shù)據(jù)結(jié)構(gòu)完成關(guān)鍵字的查找。



從上圖可以看出，如果我們需要尋找數(shù)字8，可以通過以下4步實現(xiàn)（可能看不懂，未來會看得懂）：

* 根節(jié)點6小于8，往6的右子節(jié)點9找
* 結(jié)點9大于8，往9的左子結(jié)點7找
* 結(jié)點7小于8，往7的左子結(jié)點找
* 找到8
* 判定樹上每個結(jié)點需要的查找次數(shù)剛好為該結(jié)點所在的層數(shù)；
* 查找成功時查找次數(shù)不會超過判定樹的深度
* N個結(jié)點的判定樹的深度為\([log_2{n}]+1\)
* \(ASL = (4*4+4*3+2*2+1)/11 = 3\)
四、樹的定義

樹（Tree）：\(n(n\geq{0})\)個結(jié)點構(gòu)成的有限集合。

* 當n=0時，稱為空樹
* 對于任一顆非空樹（n>0），它具備以下性質(zhì)：
* 樹中有一個稱為根（Root）的特殊結(jié)點，用r表示
* 其余結(jié)點可分為m（m>0）個互不相交的有限集\(T_1,T_2,\cdots,T_m\)，其中每個集合本身又是一棵樹，稱為原來樹的子樹（SubTree）


五、樹與非樹

牢記樹有以下3個特性：

* 子樹是不相交的；
* 除了根結(jié)點外，每個結(jié)點有且僅有一個父結(jié)點；
* 一顆N個結(jié)點的樹有N-1條邊
5.1 非樹



5.2 樹



六、樹的一些基本術(shù)語



* 結(jié)點的度（Degree）：結(jié)點的子樹個數(shù)
* 樹的度：樹的所有結(jié)點中最大的度數(shù)
* 葉結(jié)點（Leaf）： 度為0的結(jié)點
* 父結(jié)點（Parent）：有子樹的結(jié)點是其子樹的根結(jié)點的父結(jié)點
* 子結(jié)點（Child）：若A結(jié)點是B結(jié)點的父結(jié)點，則稱B結(jié)點是A結(jié)點的子結(jié)點；子結(jié)點也稱孩子結(jié)點
*
兄弟結(jié)點（Sibling）：具有同一父結(jié)點的各結(jié)點彼此是兄弟結(jié)點

*
路徑和路徑長度：從結(jié)點\(n_1\)到\(n_k\)的路徑為一個結(jié)點序列\(zhòng)(n_1 , n_2 ,\cdots, n_k\) , \(n_i\)是
\(n_{i+1}\)的父結(jié)點。路徑所包含邊的個數(shù)為路徑的長度

* 祖先結(jié)點(Ancestor)：沿樹根到某一結(jié)點路徑上的所有結(jié)點都是這個結(jié)點的祖先結(jié)點
*
子孫結(jié)點(Descendant)：某一結(jié)點的子樹中的所有結(jié)點是這個結(jié)點的子孫

*
結(jié)點的層次（Level）：規(guī)定根結(jié)點在1層，其它任一結(jié)點的層數(shù)是其父結(jié)點的層數(shù)加1

*
樹的深度（Depth）：樹中所有結(jié)點中的最大層次是這棵樹的深度

七、樹的表示

7.1 樹的鏈表表示



上圖所示樹的鏈表表示法有很大的缺陷，假設樹的深度非常大，并且不能保證所有樹的子結(jié)點都有3個，那么會造成很大程度的浪費。

7.2 樹的鏈表（兒子-兄弟）表示法

為了解決樹的普通鏈表表示會有空間的浪費的缺陷，我們可以把鏈表的指針設置兩個鏈接，一個鏈接指向兒子結(jié)點，另一個鏈接指向兄弟結(jié)點，如下圖所示：



上圖所示的樹的表示方法，已經(jīng)足夠完美了，但是如果我們把鏈表表示的樹旋轉(zhuǎn)45°角，會發(fā)現(xiàn)如下圖所示：



經(jīng)過45°角的旋轉(zhuǎn)，我們會發(fā)現(xiàn)一顆二叉樹（一個結(jié)點至多擁有2個子結(jié)點的樹），也就是說最普通的樹其實可以通過二叉樹表示，也就是說
我們只要把二叉樹研究透了，我們即研究透了樹。

• ? 上一篇：FreeSql （二十八）事務
• ? 下一篇：認證方案之初步認識JWT