目錄

1.樹的概念及結(jié)構(gòu)

1.1樹的概念

1.2樹的表示

1.3樹在實際生活中的運用

2.二叉樹的概念及結(jié)構(gòu)?

2.1概念

2.2特殊的二叉樹

2.3二叉樹的性質(zhì)

2.4二叉樹的存儲結(jié)構(gòu)

1.樹的概念及結(jié)構(gòu)

1.1樹的概念

樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)，它是由n (n>=0)個有限結(jié)點組成一個具有層次關(guān)系的集合。把它叫做樹是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的。

• 有一個特殊的結(jié)點，稱為根結(jié)點，根節(jié)點沒有前驅(qū)結(jié)點
• 除根節(jié)點外，其余結(jié)點被分成M(M>0)個互不相交的集合T1、T2、.......Tm，其中每一個集合Ti(1 <= i <= m)又是一棵結(jié)構(gòu)與樹類似的子樹。每棵子樹的根結(jié)點有且只有一個前驅(qū)，可以有0個或多個后繼
• 因此，樹是遞歸定義的。

樹型結(jié)構(gòu)：注意：樹形結(jié)構(gòu)中，子樹之間不能有交集，否則就不是樹形結(jié)構(gòu)

?

樹的相關(guān)概念：

?

結(jié)點的度：一個結(jié)點含有的子樹的個數(shù)稱為該結(jié)點的度；如上圖：A的為6

葉結(jié)點或終端結(jié)點：度為0的結(jié)點稱為葉結(jié)點；如上圖：B、C、H、I...等結(jié)點為葉結(jié)點

非終端結(jié)點或分支結(jié)點：度不為0的結(jié)點；如上圖：D、E、F、G...等結(jié)點為分支結(jié)點

雙親結(jié)點或父結(jié)點：若一個結(jié)點含有子結(jié)點，則這個結(jié)點稱為其子結(jié)點的父結(jié)點；如上圖：A是B的父結(jié)點

孩子結(jié)點或子結(jié)點：一個結(jié)點含有的子樹的根結(jié)點稱為該結(jié)點的子結(jié)點；如上圖：B是A的孩子結(jié)點

兄弟結(jié)點：具有相同父結(jié)點的結(jié)點互稱為兄弟結(jié)點；如上圖：B、C是兄弟結(jié)點親兄弟

樹的度：一棵樹中，最大的結(jié)點的度稱為樹的度；如上圖：樹的度為6

結(jié)點的層次：從根開始定義起，根為第1層，根的子結(jié)點為第2層，以此類推;

樹的高度或深度：樹中結(jié)點的最大層次；如上圖：樹的高度為4

堂兄弟結(jié)點：雙親在同一層的結(jié)點互為堂兄弟；如上圖：H、l互為兄弟結(jié)點

結(jié)點的祖先：從根到該結(jié)點所經(jīng)分支上的所有結(jié)點；如上圖：A是所有結(jié)點的祖先

子孫：以某結(jié)點為根的子樹中任一結(jié)點都稱為該結(jié)點的子孫。如上圖：所有結(jié)點都是A的子孫

森林：由m (m>0）棵互不相交的樹的集合稱為森林；

1.2樹的表示

樹結(jié)構(gòu)相對線性表就比較復(fù)雜了，要存儲表示起來就比較麻煩了，既要保存值域，也要保存結(jié)點和結(jié)點之間的關(guān)系，實際中樹有很多種表示方式如：雙親表示法，孩子表示法、孩子雙親表示法以及孩子兄弟表示法等。我們這里就簡單的了解一下，其中最常用的是孩子兄弟表示法。

1.雙親表示法

struct TreeNode
{
    int data;
    int parent;    //雙親的下標(biāo)
}

2.孩子表示法

如果明確了樹的度可以定義：

struct TreeNode
{
    int data;
    struct TreeNode* child1;
    struct TreeNode* child2;
    // . . .
    //樹的度是幾就定于幾個孩子
}

不知道樹的度可以采用線性表存儲孩子，通常采用的是“順序表+鏈表”的組合結(jié)構(gòu)

typedef struct CTNode{
    //鏈表中每個結(jié)點存儲的不是數(shù)據(jù)本身，
    //而是數(shù)據(jù)在數(shù)組中存儲的位置下標(biāo)!!
    int child;
    struct CTNode * next;
}ChildPtr;

typedef struct TreeNode
    //結(jié)點的數(shù)據(jù)類型
    TElemType data;
    //孩子鏈表的頭指針
    ChildPtr* firstchild;
}TreeNode;

3.孩子雙親表示法相當(dāng)于鏈表中的循環(huán)鏈表，這里就不做介紹了

4.孩子兄弟表示法

typedef int DataType
struct Node
{
    struct Node* fristChild;    //指向該節(jié)點的第一個孩子節(jié)點
    struct Node* NextBrother;   //指向該節(jié)點的下一個兄弟節(jié)點
    DataType data;    //該節(jié)點中的數(shù)據(jù)
}

?

1.3樹在實際生活中的運用

Windows操作系統(tǒng)文件系統(tǒng)，文件樹，C盤D盤兩個文件樹，可以認(rèn)為是森林。

Linux操作系統(tǒng)樹狀目錄結(jié)構(gòu)

2.二叉樹的概念及結(jié)構(gòu)?

2.1概念

—棵二叉樹是結(jié)點的一個有限集合，該集合:

1. 或者為空
2. 由一個根節(jié)點加上兩棵別稱為左子樹和右子樹的二叉樹組成

?從上圖可以看出:

1. 二叉樹不存在度大于2的結(jié)點
2. 二叉樹的子樹有左右之分，次序不能顛倒，因此二叉樹是有序樹

注意:對于任意的二叉樹都是由以下幾種情況復(fù)合而成的：

現(xiàn)實中的二叉樹：

2.2特殊的二叉樹

1. 滿二叉樹：一個二叉樹，如果每一個層的結(jié)點數(shù)都達(dá)到最大值，則這個二叉樹就是滿二叉樹。也就是說，如果一個二叉樹的層數(shù)為K，且結(jié)點總數(shù)是2^K-1，則它就是滿二叉樹。
2. 完全二叉樹：完全二叉樹是效率很高的數(shù)據(jù)結(jié)構(gòu)，完全二叉樹是由滿二叉樹而引出來的。對于深度為K的，有n個結(jié)點的二叉樹，當(dāng)且僅當(dāng)其每一個結(jié)點都與深度為K的滿二叉樹中編號從1至n相同的結(jié)點一一對應(yīng)時稱之為完全二叉樹。要注意的是滿二叉樹是一種特殊的完全二叉樹。完全二叉樹節(jié)點個數(shù)取值范圍是【2^(K-1)，2^K-1】。

?

?

2.3二叉樹的性質(zhì)

1.若規(guī)定根節(jié)點1，則一棵非空二叉樹的第i層上最多有2^(i-1)個結(jié)點

⒉.若規(guī)定根節(jié)點的層數(shù)為1，則深度為h的二叉樹的最大結(jié)點數(shù)是2^h-1.

3.對任何一棵二叉樹,如果度為0的葉結(jié)點個數(shù)為N0，度為2的分支結(jié)點個數(shù)為N2，則有N0?= N2+1

二叉樹總節(jié)點數(shù)目為N,有 N=N0+N1+N2，二叉樹度數(shù)總和為0*N0+1*N1+2*N2 = N-1

N0+N1+N2-1 =? 0*N0+1*N1+2*N2

N0 = N2+1;

4.若規(guī)定根節(jié)點的層數(shù)為1，具有n個結(jié)點的滿二叉樹的深度，h=log2(n + 1)。(ps: log2(n ＋1)是log以2為底，n+1為對數(shù))
5.對于具有n個結(jié)點的完全二叉樹，如果按照從上至下從左至右的數(shù)組順序?qū)λ泄?jié)點從0開始編號，則對于序號為i的結(jié)點有:

1. 若 i>0，i位置節(jié)點的雙親序號：(i-1)/2;；i=0，i為根節(jié)點編號，無雙親節(jié)點
2. 若 2i+1<n，左孩子序號:2i+1，2i+1 >= n無左孩子
3. 若 2i+2<n，右孩子序號:2i+2，2i+2 >= n無右孩子

*6.給定N個節(jié)點，能構(gòu)成h(N)種不同的二叉樹。h(N)為卡特蘭數(shù)的第N項。h(n)=C(n,2*n)/(n+1)。

*7.設(shè)有i個枝點，I為所有枝點的道路長度總和，J為葉的道路長度總和J=I+2i

帶*太難，一般不用。

例題：

1．某二叉樹共有399個結(jié)點，其中有199個度為2的結(jié)點，則該二叉樹中的葉子結(jié)點數(shù)為（)

A 不存在這樣的二叉樹
B 200
C 198

D 199

2.下列數(shù)據(jù)結(jié)構(gòu)中，不適合采用順序存儲結(jié)構(gòu)的是（)

A 非完全二叉樹
B 堆
C 隊列

D 棧

3.在具有2n個結(jié)點的完全二叉樹中，葉子結(jié)點個數(shù)為（)
A n
B n+1

C n-1

D n/2

4.一棵完全二叉樹的節(jié)點數(shù)位為531個，那么這棵樹的高度為()

A 11
B 10

C 8

D12

5.一個具有767個節(jié)點的完全二叉樹，其葉子節(jié)點個數(shù)為()
A 383
B 384

C 385

D 386

答案:1.B 2.A 3.A 4.B 5.B

第3題解析：

因為N0 = N2 + 1

N0+N1+N2 = 2n

N0+N1+N0-1 = 2n

2N0 +N1-1 = 2n? 2n為偶數(shù)，完全二叉樹度為1的結(jié)點個數(shù)要么是1個，要么沒有。所以只能是1

2N0 = 2n? ? ? N0 = n? 同理得出N1= 1? N2 = n-1

2.4二叉樹的存儲結(jié)構(gòu)

二叉樹一般可以使用兩種結(jié)構(gòu)存儲，一種順序結(jié)構(gòu)，一種鏈?zhǔn)浇Y(jié)構(gòu)。
1.順序存儲
順序結(jié)構(gòu)存儲就是使用數(shù)組來存儲，一般使用數(shù)組只適合表示完全二叉樹，因為不是完全二叉樹會有空間的浪費。而現(xiàn)實中使用中只有堆才會使用數(shù)組來存儲，關(guān)于堆我們后面的文章會專門講解。二叉樹順序存儲在物理上是一個數(shù)組，在邏輯上是一顆二叉樹。

2.鏈?zhǔn)酱鎯?/strong>
二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)是指，用鏈表來表示一棵二叉樹，即用鏈來指示元素的邏輯關(guān)系。通常的方法是鏈表中每個結(jié)點由三個域組成，數(shù)據(jù)域和左右指針域，左右指針分別用來給出該結(jié)點左孩子和右孩子所在的鏈結(jié)點的存儲地址。鏈?zhǔn)浇Y(jié)構(gòu)又分為二叉鏈和三叉鏈，當(dāng)前我們學(xué)習(xí)中一般都是二叉鏈，后面課程學(xué)到高階數(shù)據(jù)結(jié)構(gòu)如紅黑樹等會用到三叉鏈。

typedef int BTDataType;
//二叉鏈
struct BinaryTreeNode
{
    struct BinTreeNode* pLeft;    //指向當(dāng)前節(jié)點左孩子
    struct BinTreeNode* pRight;   //指向當(dāng)前節(jié)點右孩子
    BTDataType data;     //當(dāng)前節(jié)點值域
}
//三叉鏈
struct BinaryTreeNode{
    struct BinTreeNode* pParent; //指向當(dāng)前節(jié)點的雙親
    struct BinTreeNode* pLeft;   //指向當(dāng)前節(jié)點左孩子
    struct BinTreeNode* pRight;  //指向當(dāng)前節(jié)點右孩子
    BTDataType _data;     //當(dāng)前節(jié)點值域
};