樹的定義

樹是由n（n≥0）個結點組成的有限集合（記為T）。

如果n=0，它是一棵空樹，這是樹的特例。

如果n>0，這n個結點中存在（有僅存在）一個結點作為樹的根結點（root），其餘結點可分為m（m≥0）個互不相交的有限集T1、T2、…、Tm，其中每個子集本身又是一棵符合本定義的樹，稱為根結點的子樹。

樹是一種非線性數據結構，具有以下特點：

每一結點可以有零個或多個後繼結點，但有且隻有一個前驅結點（根結點除外）。

數據結點按分支關系組織起來，清晰地反映了數據元素之間的層次關系。

抽象數據類型樹的描述

樹的邏輯結構表示方法

樹形表示法。這是樹的最基本的表示，使用一棵倒置的樹表示樹結構，非常直觀和形象。

文氏圖表示法。使用集合以及集合的包含關系描述樹結構。

凹入表示法。使用線段的伸縮關系描述樹結構。

括号表示法。将樹的根結點寫在括号的左邊，除根結點之外的其餘結點寫在括号中并用逗号分隔。

列表表示法。 "[根結點，子樹1，子樹2，…，子樹m]"。

樹的基本術語

結點的度。樹中每個結點具有的子樹數或者後繼結點數稱為該結點的度。

樹的度。樹中所有結點的度的最大值稱之為樹的度。

分支結點。度大于0的結點稱為分支結點或非終端結點。度為1的結點稱為單分支結點，度為2的結點稱為雙分支結點，依次類推。

葉子結點（或葉結點）。度為零的結點稱為葉子結點或終端結點。

孩子結點。一個結點的後繼稱之為該結點的孩子結點。

雙親結點（或父親結點）。一個結點稱為其後繼結點的雙親結點。

子孫結點。一個結點的子樹中除該結點外的所有結點稱之為該結點的子孫結點。

祖先結點。從樹根結點到達某個結點的路徑上通過的所有結點稱為該結點的祖先結點（不含該結點自身）。

兄弟結點。具有同一雙親的結點互相稱之為兄弟結點。

結點層次。樹具有一種層次結構，根結點為第一層，其孩子結點為第二層，如此類推得到每個結點的層次。

樹的高度。樹中結點的最大層次稱為樹的高度或深度。

森林。零棵或多棵互不相交的樹的集合稱為森林。

樹的性質

性質1： 樹中的結點數等于所有結點的度數加1。

性質2：度為m的樹中第i層上至多有mi-1個結點，這裡應有i≥1。

數學歸納法證明

當一棵m次樹的第i層有mi-1個結點（i≥1）時，稱該層是滿的，若一棵m次樹的所有葉子結點在同一層，并且每一層都是滿的，稱為滿m次樹。顯然，滿m次樹是所有相同高度的m次樹中結點總數最多的樹。

也可以說，對于n個結點，構造的m次樹為滿m次樹或者接近滿m次樹，此時樹的高度最小。

若一棵三次樹中度為3的結點為2個，度為2的結點為1個，度為1的結點為2個，則該三次樹中總的結點個數和度為0的結點個數分别是多少？

樹的基本運算

樹的運算主要分為三大類：

查找滿足某種特定關系的結點，如尋找當前結點的雙親結點等；

插入或删除某個結點，如在樹的當前結點上插入一個新結點或删除當前結點的第i個孩子結點等；

遍曆樹中每個結點。

樹的遍曆運算是指按某種方式訪問樹中的每一個結點且每一個結點隻被訪問一次。

有以下3種遍曆方法：

先根遍曆

若樹不空，則先訪問根結點，然後依次先根遍曆各棵子樹。

後根遍曆

若樹不空，則先依次後根遍曆各棵子樹，然後訪問根結點。

層次遍曆

若樹不空，則自上而下自左至右訪問樹中每個結點。

注意：先根和後根遍曆算法都是遞歸的。

樹的存儲結構

雙親存儲結構

這種存儲結構是一種順序存儲結構，用一組連續空間存儲樹的所有結點，同時在每個結點中附設一個僞指針指示其雙親結點的位置。

雙親存儲結構

利用了每個結點（根結點除外）隻有唯一雙親的性質。

這種存儲結構中，求某個結點的雙親結點十分容易，但求某個結點的孩子結點時需要遍曆整個結構。

例子：若一棵樹采用雙親存儲結構t存儲，設計一個算法求指定索引是i的結點的層次。

孩子鍊存儲結構

個結點包含結點值和所有孩子結點指針，可按一個結點的度設計結點的孩子結點指針個數

孩子鍊存儲結構

優點是查找某結點的孩子結點十分方便。

缺點是查找某結點的雙親結點比較費時。

若一棵樹采用孩子鍊存儲結構t存儲，設計一個算法求其高度

解：一棵樹的高度為根的所有子樹高度的最大值加1。求整棵樹的高度為"大問題"，求每棵子樹高度為"小問題"。設f(t)為求樹t的高度，對應的遞歸模型如下：

長子兄弟鍊存儲結構

長子兄弟鍊存儲結構是為每個結點設計三個域：一個數據元素域，一個指向該結點的長子的指針域，一個指向該結點的下一個兄弟結點指針域。

長子兄弟鍊存儲結構

優點是查找某結點的孩子結點十分方便。

缺點是查找某結點的雙親結點比較費時。

若一棵樹采用長子兄弟鍊存儲結構t存儲，設計一個算法求其高度。

解：一棵樹的高度為根的所有子樹高度的最大值加1。求整棵樹的高度為"大問題"，求每棵子樹高度為"小問題"。設f(t)為求樹t的高度，對應的遞歸模型如下：

列表存儲結構

将樹的列表表示（樹的邏輯表示法之一）直接采用Python中的列表數據類型表示，稱為樹的列表存儲結構。

若一棵樹采用列表存儲結構t存儲，設計一個算法求其高度。 解：一棵樹的高度為根的所有子樹高度的最大值加1。求整棵樹的高度為"大問題"，求每棵子樹高度為"小問題"。設f(t)為求樹t的高度，對應的遞歸模型如下：

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!