一、什么是樹(shù)

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

人類(lèi)社會(huì)家譜社會(huì)組織結(jié)構(gòu)圖書(shū)信息管理

其中，人類(lèi)社會(huì)家譜如下圖所示：

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

二、查找

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

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

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

2.1 靜態(tài)查找 2.1.1 方法1：順序查找

/* c語(yǔ)言實(shí)現(xiàn) */

int SequentialSearch (StaticTable *Tbl, ElementType K)
{
// 在表Tbl[1]~Tb1[n]中查找關(guān)鍵字為K的數(shù)據(jù)元素
 int i;
 Tbl->Element[0] = K; // 建立哨兵，即沒(méi)找到可以返回哨兵的索引0表示未找到
 for (i = Tbl->Length; Tbl->Element[i] != K; i--); // 查找成功返回所在單元下標(biāo)；不成功放回0
 return i;
}

順序查找算法的時(shí)間復(fù)雜度為O(n)

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

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

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

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

/* c語(yǔ)言實(shí)現(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; // 計(jì)算中間元素坐標(biāo)
  if (K < Tbl->Element[mid]) right = mid - 1; // 調(diào)整右邊界
  else if (K > Tbl->Element[mid]) left = mid + 1; // 調(diào)整左邊界
  else return mid; // 查找成功，返回?cái)?shù)據(jù)元素的下標(biāo)
 }
 return NotFound; // 查找不成功，返回-1
}

# python語(yǔ)言實(shí)現(xiàn)

def binary_chop(alist, data):
  n = len(alist)
  first = 0
  last = n - 1
  while first <= last:
    mid = (last + first) // 2
    if alist[mid] > data:
      last = mid - 1
    elif alist[mid] < data:
      first = mid + 1
    else:
      return True
  return False

二分查找算法具有對(duì)數(shù)的時(shí)間復(fù)雜度O(logN)

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

三、二分查找判定樹(shù)

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

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

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

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

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

五、樹(shù)與非樹(shù)

牢記樹(shù)有以下3個(gè)特性：

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

5.2 樹(shù)

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

結(jié)點(diǎn)的度（Degree）：結(jié)點(diǎn)的子樹(shù)個(gè)數(shù)樹(shù)的度：樹(shù)的所有結(jié)點(diǎn)中最大的度數(shù)葉結(jié)點(diǎn)（Leaf）： 度為0的結(jié)點(diǎn)父結(jié)點(diǎn)（Parent）：有子樹(shù)的結(jié)點(diǎn)是其子樹(shù)的根結(jié)點(diǎn)的父結(jié)點(diǎn)子結(jié)點(diǎn)（Child）：若A結(jié)點(diǎn)是B結(jié)點(diǎn)的父結(jié)點(diǎn)，則稱(chēng)B結(jié)點(diǎn)是A結(jié)點(diǎn)的子結(jié)點(diǎn)；子結(jié)點(diǎn)也稱(chēng)孩子結(jié)點(diǎn)

兄弟結(jié)點(diǎn)（Sibling）：具有同一父結(jié)點(diǎn)的各結(jié)點(diǎn)彼此是兄弟結(jié)點(diǎn)

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

祖先結(jié)點(diǎn)(Ancestor)：沿樹(shù)根到某一結(jié)點(diǎn)路徑上的所有結(jié)點(diǎn)都是這個(gè)結(jié)點(diǎn)的祖先結(jié)點(diǎn)

子孫結(jié)點(diǎn)(Descendant)：某一結(jié)點(diǎn)的子樹(shù)中的所有結(jié)點(diǎn)是這個(gè)結(jié)點(diǎn)的子孫

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

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

七、樹(shù)的表示

7.1 樹(shù)的鏈表表示

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

7.2 樹(shù)的鏈表（兒子-兄弟）表示法

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

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

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

以上就是本次全部相關(guān)知識(shí)點(diǎn)內(nèi)容，感謝大家的閱讀和對(duì)腳本之家的支持。

最新評(píng)論