數據結構與算法樹形結構

NO IMAGE

數據結構與算法系列文章
數據結構與算法 – 時間複雜度
數據結構與算法 – 線性表
數據結構與算法 – 樹形結構

目錄

一、
二、二叉樹
三、樹、森林與二叉樹的轉換

一、樹

    樹形結構 是數據元素(結點)之間有分支,並且具有層次關係的結構,可用於表示數據元素之間存在的一對多關係。
    樹(Tree) 是由n(n≥0)個結點構成的有限集合,當n=0時稱為空樹。若樹非空,則具有以下兩個性質:
    (1)有且僅有一個特定的結點,稱為根(Root)。
    (2)其餘的結點可分為m個互不相交的集合T1,T2,…,Tm,其中每一個集合都是一棵樹,並且稱為根的子樹( Subtree)。
    如下圖所示是有13個結點的樹,A是根,其餘結點分成三個互斥的集合T1={B,E,F,K,L}、T2={C,G}、T3={D,H,I,J,M},T1、T2、T3都是A的子樹,其本身也是一棵樹。

數據結構與算法樹形結構

樹的基本術語:

    樹結點( Tree Node) :樹中一個獨立單元。包含一個數據元素及若干指向其子樹的分支,如上圖中的A、B、C、D等。
    樹根(Root) :樹中唯一沒有前驅的結點,如上圖中的A結點。
    結點的度( Node Degree) :結點擁有的子樹數,稱為結點的度。例如,在上圖中A的度為3,B的度為2,K的度為0。
    樹的度( Tree Degree) :樹中各結點的度的最大值。如上圖中樹的度為3。
    樹葉(Leaf) :度為0的結點。例如,在圖中,K、L、F、G、1、J、M都是樹葉,也稱葉結點。除根和葉子以外的其他結點稱為中間結點。
    雙親( Parent)和孩子( Child) :把一個樹結點的直接前驅稱為該結點的雙親;反之;把一個樹結點的所有直接後繼稱為該結點的孩子。例如,上圖中,結點B是結點A的孩子,結點A是結點B的雙親。
    兄弟( Sibling) :同一雙親的孩子之間互稱為兄弟。例如,上圖中,結點K、L互為兄弟,結點H、I、J互為兄弟。將這些關係進一步推廣,結點的祖先就是從根到該結點的所經分支上的所有結點。以某結點為根的子樹中的任一結點都稱為該結點的子孫。此外雙親在同一層上的結點互為堂兄弟.
    樹的層次( Level)和深度( Depth) :從根算起,根為第一層,根的孩子為第二層,樹中任一結點的層次等於它的雙親的層次加1。樹中各結點層次的最大值稱為樹的深度或高度。例如,上圖中的樹的深度為4。
    有序樹和無序樹( Ordered Tree8。 Unordered Tree) :如果樹中結點的各子樹可看成從左至右是有次序的(即不能互換),則稱該樹為有序樹,否則稱為無序樹。在有序樹最左邊子樹的根稱為第一孩子,最右邊子樹的根稱為最後一個孩子。
    森林( Forest) :m(m≥0)棵互不相交的樹的集合。對樹中每個結點而言,其子樹的集合即為森林。由此也可以以森林和樹的相互遞歸定義來描述樹。

1.1、樹的存儲結構

    樹是一種非線性結構。為了存儲一探樹,必須把樹中各結點之間一對多的關係反映在存儲結構中。由於在一個m階的普通樹中,每一個結點的孩子可是0~m個,所以相對於二又樹而言,樹的存錯結構要複雜,一般有如下幾種存儲結構:

  • 1.1.1、雙親表示法

雙親表示法是以一組連續空間存儲樹的結點,同時在每個結點中附設一個標誌指示其雙親結點在表中的位置,該存儲結構定義如下;

數據結構與算法樹形結構

  • 1.1.2、孩子表示法

    由於樹中的每個結點可能有多棵子樹,因此可以採用多重鏈表來表示,即每個結點有多個指針域,分別指向其孩子結點。
   如圖6-13所示,樹的孩子表示法需要按照樹的度m為每個結點分配指針域,而每個結點的孩子個數可不同,當m很大時,指針域的存儲單元利用率很低。如果按每個結點的實際孩子數來分配指針單元,結點的大小可變,會給存儲管理帶來不便。一個較好的解決辦法就是為每個結點建立一個孩子鏈表,n個結點的樹由n個這樣的單鏈表組成,每個鏈表的表頭結點存放該結點的值和指向其孩子的頭指針,如圖614所示

數據結構與算法樹形結構

  • 1.1.3、孩子兄弟表示法

    孩子兄弟表示法又稱樹的二又鏈表表示法。樹中的每個結點由三個域組成:data域 結點的數據信息, firstchild域為指向結點的第一個孩子的指針, nextbrother域為指向下一個兄弟的指針,如下圖所示。
    由下圖可以看出,每個結點的左指針指向孩子結點,而右指針指向兄弟結點,並且根結點的右指針為空。樹的孩子兄弟表示法為實現樹、森林與二又樹之間的轉換提供了基礎。

數據結構與算法樹形結構

二、二叉樹

    二叉樹 就是度為2的有序樹,是最重要的一種樹形結構。二又樹的存儲和處理比普通樹簡單,同時普通樹都可以方便地轉化為二又樹來存儲和處理。
    二叉樹( Binary Tree) 是一種特殊的樹形結構。定義如下:
    (1)由n(n≥0)個結點所構成的集合,此集合可以為空。
    (2)二叉樹的根結點下可分為兩個互不相交的子樹,子樹有左右之分,次序不能任意顛倒,稱為左子樹和右子樹:且左右子樹均為二叉樹。

數據結構與算法樹形結構

2.1、二叉樹的性質

二叉樹是有序樹的特例,具有下列重要性質:
性質1、在二叉樹的第i層上至多有2^(i-1)個結點(i>=1)。
性質2、深度為k的二叉樹至多有2^(k) – 1個結點,(k>=1)。
性質3、對任何一顆二叉樹T,如果其終端結點數為n0,度為2的結點數為n2,則n0 = n2 + 1;
性質4、具有n個結點的完全二叉樹的深度為 (logn以2為底的對數 + 1) 。
性質5、如果對一棵有n結點的深度為(logn以2為底的對數 + 1) ,完全二叉樹的結點按層序編號,同層按從左至右,則對任一結點i(1 ≤ i ≤ n)。於是有:
    (1)如果=1,則結點i是二叉樹的根,無雙親;如果i>1,則其雙親 PARENT(i)是結點i/2。
    (2)如果2i>n,則結點i無左孩子(結點i為葉子結點);否則,其左孩子 LCHILD(i)是結點2i。
    (3)如果2i+1>n,則結點i無右孩子;否則,其右孩子 RCHILD(i)是結點2i+1。

數據結構與算法樹形結構

    一棵深度為k且有2^k – 1個結點的二叉樹稱為 滿二叉樹 。滿二叉樹的特點是每一層上的結點數都是最大結點數。
    對滿二叉樹的結點進行連續編號,約定編號從根結點起,自上而下,自左至右。由此可引出完全二叉樹的定義。深度為k、有n個結點的二叉樹,當且僅當其每一個結點都與深度為k的滿二叉樹中編號從1~n的結點一一對應時,稱為 完全二叉樹 。如上圖所示完全二叉樹具有的特點是:
    (1)葉子結點只可能在層次最大的兩層上出現。
    (2)對任一結點,若其右分支下的子孫的最大層次為r,則其左分支下的子孫的最大層次必為r或r+1。

2.2、二叉樹的存儲結構

  • 2.2.1、順序存儲結構

    用一組地址連續的存儲單元存儲二叉樹中的各個結點。為了便於對二叉樹結點進行查找或處理,存儲時需要將普通二叉樹的各個結點按照它們在完全二叉樹的對應結點位置依次存放到數組相應的存儲單元中。如圖所示,二又樹的順序存儲結構定義如下:

數據結構與算法樹形結構

    一般來說,順序存儲結構只適用於完全二叉樹或滿二叉樹的存儲,因為普通二叉樹採用順序存儲結構進行存儲時,將導致存儲單元的浪費。最壞情況下,對於一個深度為k且只有k個結點的右支樹來說,存儲時需要2^k-1個存儲單元。

  • 2.2.2、鏈式存儲結構

    採用鏈式存儲結構存儲二叉樹時,可以根據樹中的結點數動態申請所需要的結點,從而避免存儲空間的浪費。
    由二叉樹的定義可知,每個二叉樹的結點由一個數據元素和分別指向其左、右子樹的兩個分支組成。因此,定義二叉樹的結點結構時至少應包含三個域:數據域和左、右指針域。其中,數據域保存結點的信息左指針域存放指向其左子樹根的信息右指針域存放指向其右子樹根的信息,如下圖所示。有時,為了便於找到結點的雙親,則可在上述結點結構中增加一個指向其雙親結點的指針域,如下圖所示。利用這兩種結點結構所得的二叉樹的存儲結構分別稱為二又鏈表和三又鏈表。如下圖所示二叉樹的鏈式存儲結構。

數據結構與算法樹形結構

數據結構與算法樹形結構

2.3、遍歷二叉樹

    二叉樹的遍歷 是指按照一定次序訪問樹中所有結點,並且每個結點僅被訪問一次的過程。它是二叉樹最基本的運算,也是二叉樹中所有其他運算的基礎。遍歷二叉樹的實質是對二叉樹的線性化過程,即遍歷的結果是將非線性結構的樹中結點排成一個線性序列,二叉樹的遍歷按訪問根結點的先後次序不同,可分為 先序遍歷、中序遍歷 和 後序遍歷
下面對二叉樹的遍歷討論中,二叉樹都採用二叉鏈表的存儲結構。

  • 1、二叉樹的先序遍歷

根據二叉樹的遞歸特性,先序遍歷二叉樹的遞歸
過程如下:
  (1)訪問根結點。
  (2)先序遍歷左子樹
  (3)先序遍歷右子樹。

  • 2、二叉樹的中序遍歷

中序遍歷二叉樹的遞歸過程如下:
  (1)中序遍歷左子樹。
  (2)訪問根結點。
  (3)中序遍歷右子樹。

  • 3、二叉樹的後序遍歷

後序遍歷二叉樹的遞歸過程如下:
  (1)後序遍歷左子樹。
  (2)後序遍歷右子樹。
  (3)訪問根結點。

數據結構與算法樹形結構

   遍歷二又樹的算法中的基本操作是訪問結點,則無論按哪種次序進行遍歷,對含有n個結點的二又樹,其時間複雜度均為0(n)。所需輔助空間為遍歷過程中棧的最大容量,即樹的深度,最壞情況下為n,則空間複雜度也為O(n)。

三、樹、森林與二叉樹的轉換

   二叉樹的二叉鏈表表示法和樹的孩子兄弟表示法都是以二叉鏈表作為存儲結構,結點的定義相同,只是解釋不同。因此,可以找到樹和二又樹之間的對應關係,即給定一棵樹,可以找到唯一的一棵二叉樹與之對應。

數據結構與算法樹形結構

   森林是樹的有限集合,可以將森林看成一棵樹,其中所有樹的根結點彼此看成兄弟結點。這樣也可以導出森林和二叉樹的對應關係。

數據結構與算法樹形結構

下面給出森林和二叉樹相互轉換的遞歸定義:
1、森林轉換成二叉樹
   若F={T1,T2,…,Tm}是森林(m≥0),則可按如下規則轉換成一棵二叉樹B=(root,LB,RB)。
  (1)若m=0,則B為空樹。
  (2)若m>0,則B的根root即為森林F中第一棵樹的根ROOT(T1);B的左子樹LB是從森林的第一棵樹T1中根結點的子樹森林F1={T1,T2,…,Tm}轉換而成的二叉樹;B的右子樹RB是從森林F中除T1外的剩餘部分F={T2,T3,…,Tm}轉換而成的二叉樹。
   具體操作步驟如下:
   (1)先將森林中的每一棵樹轉換為二叉樹。
   (2)按森林中樹的次序,依次將後一棵樹作為前一棵樹的右子樹,並將第一棵樹的根作為目標二又樹的根。
2、二叉樹轉換成森林
  如果B=(roo,LB,RB)是一棵二叉樹,則可按如下規則轉換成森林F={T,,…,Tm}。
  (1)若B為空,則F為空。
  (2)若B非空,則F中第一棵樹T1的根ROOT(T1)即為二叉樹B的根root;T1中根結點的子樹森林F1是由B的左子樹LB轉換而成的森林;F中除T1之外其餘樹組成的森林F’={T2,T3,…,Tm}是由B的右子樹RB轉換而成的森林。
   具體操作步驟如下:
   (1)若二叉樹非空,則二叉樹根及其左子樹為第一棵樹的二叉樹形式。
   (2)二又樹根的右子樹又可看作是剩餘二叉樹構成的森林,再繼續分離出一棵樹,直至產生一顆沒有右子樹的二叉樹為止。

注:文中的圖片均轉摘自網絡

如果需要跟我交流的話:
※ Github: github.com/wsl2ls
※ 簡書:www.jianshu.com/u/e15d1f644…
※ 微信公眾號:iOS2679114653
※ QQ:1685527540

相關文章

關於IOS屬性atomic(原子性)的理解

GYHttpMock:使用及源碼解析

IOS組件化方案總結

數據結構與算法查找