樹型結(jié)構(gòu) 是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)，其中以樹和二叉樹最為常用，直觀來(lái)看，樹是以分支關(guān)系定義的層次結(jié)構(gòu)。樹型結(jié)構(gòu)在客觀世界中廣泛存在，比如人類社會(huì)中的祖輩關(guān)系，社會(huì)機(jī)構(gòu)組織等等都可以用樹來(lái)形象表示。樹型結(jié)構(gòu)在計(jì)算機(jī)領(lǐng)域中也得到了廣泛應(yīng)用。

Part1 樹

1.1 樹的定義

樹（Tree） 是n（n>=0）n（n>=0） n （ n >=0）個(gè)結(jié)點(diǎn)的有限集，在任意一棵非空樹中滿足：

有且僅有一個(gè)特定的結(jié)點(diǎn)稱為 根（Root） 的結(jié)點(diǎn)；
當(dāng)n>1 n>1 n>1時(shí)，其余結(jié)點(diǎn)可分為m（m>0） m（m>0）m（m>0）個(gè)互不相交的有限集T1、T2、?????、TmT1、T2、·····、TmT1、T2、?????、Tm，其中每一個(gè)集合本身又是一棵樹，并且稱為根的子樹（SubTree）。**

樹的結(jié)構(gòu)定義是一個(gè)遞歸的定義，即在樹的定義中又用到樹的概念， 遞歸是樹固有的特性 。在樹型結(jié)構(gòu)中，除了根結(jié)點(diǎn)以外，任何一個(gè)結(jié)點(diǎn)有且僅有一個(gè)前驅(qū)，每個(gè)結(jié)點(diǎn)可以有0個(gè)或多個(gè)后繼。結(jié)點(diǎn)數(shù)為0的樹又稱之為空樹。

1.2 樹的基本術(shù)語(yǔ)

樹的結(jié)點(diǎn)包含一個(gè)數(shù)據(jù)元素及若干指向其子樹的分支。結(jié)點(diǎn)擁有的子樹數(shù)稱為結(jié)點(diǎn)的 度（Degree） **，**以上圖為例，結(jié)點(diǎn)D的度為3，因?yàn)榻Y(jié)點(diǎn)D有三條分支結(jié)構(gòu)；依次列舉，結(jié)點(diǎn)C的度為1，結(jié)點(diǎn)B的度為2等等。

度為0的結(jié)點(diǎn)稱為葉子（Leaf）結(jié)點(diǎn)或 終端結(jié)點(diǎn) ，以上圖為例，結(jié)點(diǎn)K、L、F、G、M、I、J都是度為0的結(jié)點(diǎn)，所以他們也被稱為葉子結(jié)點(diǎn)或終端結(jié)點(diǎn)。

度不為0的結(jié)點(diǎn)稱為非終端結(jié)點(diǎn)或 分支結(jié)點(diǎn) 。除根節(jié)點(diǎn)外，分支結(jié)點(diǎn)也稱為內(nèi)部結(jié)點(diǎn)，以上圖為例，結(jié)點(diǎn)B、C、D、E、H的度都不為零，所以他們稱為非終端結(jié)點(diǎn)或分支結(jié)點(diǎn)。

樹的度是樹內(nèi)各結(jié)點(diǎn)的度的最大值，以上圖為例，在整棵樹中，結(jié)點(diǎn)中度的最大值是3，所以樹的度就為3。

結(jié)點(diǎn)的子樹的根稱為該結(jié)點(diǎn)的 孩子（Child） ，相應(yīng)地，該結(jié)點(diǎn)稱為孩子的 雙親（Parent） ，以上圖為例，結(jié)點(diǎn)B的孩子結(jié)點(diǎn)為E和F，反之，結(jié)點(diǎn)B也是結(jié)點(diǎn)E、F的雙親結(jié)點(diǎn)。

同一個(gè)雙親的孩子之間互稱 兄弟（Sibling）， 以上圖為例，結(jié)點(diǎn)H、I、J的雙親為同一個(gè)結(jié)點(diǎn)D，所以結(jié)點(diǎn)H、I、J互為兄弟結(jié)點(diǎn)。

結(jié)點(diǎn)的祖先是從根到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)，反之，以某結(jié)點(diǎn)為根的子樹中的任一結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的子孫。以上圖為例，結(jié)點(diǎn)G的祖先就為結(jié)點(diǎn)A和C，反之，結(jié)點(diǎn)C的子孫就為結(jié)點(diǎn)G。

結(jié)點(diǎn)的層次（Level） 是從根開始定義的，根為第一層，根的孩子為第二層（自上往下數(shù)）以上圖為例，結(jié)點(diǎn)G的層次為3。

樹中結(jié)點(diǎn)的最大層次稱為樹的深度(Depth) 或高度（其實(shí)就是整棵樹總共有多少層）以上圖為例，樹的深度或高度為4。

結(jié)點(diǎn)數(shù) = 總度數(shù) + 1 以上圖為例，結(jié)點(diǎn)A的度數(shù)為3；結(jié)點(diǎn)B的度數(shù)為2；結(jié)點(diǎn)C的度數(shù)為1，結(jié)點(diǎn)D的度數(shù)為3；結(jié)點(diǎn)E的度數(shù)為2；結(jié)點(diǎn)H的度數(shù)為1；其余結(jié)點(diǎn)K、L、F、G、M、I、J的度數(shù)為0，所以這棵樹的結(jié)點(diǎn)數(shù)就等于：

T結(jié)點(diǎn)數(shù) = 3+2+1+3+2+1+1；最后結(jié)果為13

1.3 有序樹和無(wú)序樹

有序樹 ——邏輯上看，樹中結(jié)點(diǎn)的各子樹從左至右是有次序的，不能互換；
無(wú)序樹 ——邏輯上看，樹中結(jié)點(diǎn)的各子樹從左至右是無(wú)次序的，可以互換。

1.4 森林

森林（Forest） 是m（m>=0) m（m>=0）m（m>=0）棵互不相交的樹的集合，對(duì)樹中的每個(gè)結(jié)點(diǎn)而言，其子樹的集合即為森林。

森林可以為空

Part2 二叉樹

2.1 二叉樹的定義

二叉樹（Binary Tree） 是另一種樹型結(jié)構(gòu)，它的特點(diǎn)是每個(gè)結(jié)點(diǎn)至多只有兩棵子樹（即二叉樹中不存在度大于2的結(jié)點(diǎn)），并且，二叉樹的子樹有左右之分， 其次序不能任意顛倒 。

二叉樹或?yàn)榭眨蚴怯梢粋€(gè)根結(jié)點(diǎn)加上兩棵分別稱為左子樹和右子樹的、互不相交的二叉樹構(gòu)成，由于這兩棵子樹也是二叉樹，則由二叉樹的定義，它們也可以是空樹。由此， 二叉樹可以有5種基本形態(tài) 。

2.2 二叉樹的性質(zhì)

二叉樹具有下列重要特性

性質(zhì)一： 在二叉樹的第iii層上之多有2i-1個(gè)結(jié)點(diǎn)（i> =1 i>=1 i>=1）；
性質(zhì)二： 深度為kkk的二叉樹之多有2k-1個(gè)結(jié)點(diǎn)（k> =1 k>=1 k>=1）；
性質(zhì)三： 對(duì)任何一棵二叉樹T，如果其終端結(jié)點(diǎn)數(shù)為n0 n0 n0，度為2的結(jié)點(diǎn)數(shù)為n 2 n2 n2，則有n0=n2+n1n0=n2+n1n0=n2+1。

2.3 二叉樹的分類

2.3.1 滿二叉樹

一棵深度為 kkk且有2k-1個(gè)結(jié)點(diǎn)的二叉樹稱為 滿二叉樹 ，這種樹的特點(diǎn)是每一層上的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù)，只有最后一層是葉子結(jié)點(diǎn)且不存在度為1的結(jié)點(diǎn)。

2.3.2 完全二叉樹

深度為 kkk的，有 nnn 個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為 kkk的滿二叉樹中編號(hào)從1至nnn的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱之為 完全二叉樹 ，在一棵完全二叉樹中只有最后兩層可能為葉子結(jié)點(diǎn)，且最多只有一個(gè)度為1的結(jié)點(diǎn)。

完全二叉樹的三個(gè)重要特性：

特性一 : 具有nnn個(gè)結(jié)點(diǎn)的完全二叉樹的深度為log2nlog2nlog2n向下取整+1；
特性二: 如果對(duì)一棵有nnn個(gè)結(jié)點(diǎn)的完全二叉樹（其深度為log2nlog2nlog2n向下取整+1）的結(jié)點(diǎn)按層序編號(hào)（從第一層到第log2nlog2nlog2n向下取整+1層，每層從左到右），則對(duì)任一結(jié)點(diǎn)i （1<=i<=n）i（1<=i<=n）i（1<=i<=n），有以下結(jié)論：

如果i = 1 i=1 i=1，則結(jié)點(diǎn)iii是二叉樹的根，無(wú)雙親，如果i >1 i>1 i>1，則雙親（Parent）為結(jié)點(diǎn)i /2i/2i/2向下取整；
如果2i >n2i>n2 i>n，則結(jié)點(diǎn)i無(wú)左孩子（結(jié)點(diǎn)iii為葉子結(jié)點(diǎn)）；否則其左孩子（Lchild）是結(jié)點(diǎn)2i；
如果2i+1>n2i+1>n2i+1>n，則結(jié)點(diǎn)i無(wú)右孩子，否則其右孩子（Rchild）是結(jié)點(diǎn)2i+1 2i+1 2i+1；

特性三： 滿二叉樹是一種特殊的完全二叉樹，但完全二叉樹不一定是滿二叉樹。

2.3.3 二叉排序樹

左子樹上所有結(jié)點(diǎn)的關(guān)鍵字均小于根結(jié)點(diǎn)的關(guān)鍵字，右子樹上所有結(jié)點(diǎn)的關(guān)鍵字均大于根結(jié)點(diǎn)的關(guān)鍵字，左子樹和右子樹又各是一棵二叉排序樹。

二叉排序樹用于元素的搜索和排序:

2.3.4 平衡二叉樹

樹上任何一個(gè)結(jié)點(diǎn)的左子樹和右子樹的深度之差不超過(guò)1；
平衡二叉樹能有更高的搜索效率。

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

2.4.1 順序存儲(chǔ)結(jié)構(gòu)

按照 順序存儲(chǔ)結(jié)構(gòu)的定義 ，用一組地址連續(xù)的存儲(chǔ)單元依次自上而下、從左往右存儲(chǔ)完全二叉樹的結(jié)點(diǎn)元素，即將完全二叉樹上編號(hào)為i ii的結(jié)點(diǎn)元素存儲(chǔ)在如上定義的一維數(shù)組中下標(biāo)為i?1 i-1 i?1的分量中。

//二叉樹的順序存儲(chǔ)表示
#define MaxSize 100     //二叉樹的最大結(jié)點(diǎn)數(shù)
struct TreeNode
{
   ElemType value;      //結(jié)點(diǎn)中的數(shù)據(jù)元素
   bool isEmpty;        //結(jié)點(diǎn)是否為空
};

//定義一個(gè)長(zhǎng)度為MaxSize的數(shù)組t，按照從上而下，從左至右的順序依次存儲(chǔ)二叉樹中的各個(gè)結(jié)點(diǎn)
TreeNode t[MaxSize];

對(duì)于一般二叉樹，則應(yīng)將其每個(gè)結(jié)點(diǎn)與完全二叉樹上的結(jié)點(diǎn)相對(duì)照，存儲(chǔ)在一維數(shù)組中的對(duì)應(yīng)分量中。順序存儲(chǔ)結(jié)構(gòu)更多僅適用于完全二叉樹的存儲(chǔ)。

2.4.2 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

由二叉樹的定義得知， 二叉樹的結(jié)點(diǎn)由一個(gè)數(shù)據(jù)元素和分別指向其左、右子樹的兩個(gè)分支構(gòu)成 ，則表示二叉樹的鏈表中的結(jié)點(diǎn)至少包含三個(gè)域： 數(shù)據(jù)域 和 左、右指針域 。有時(shí)，為了便于找到結(jié)點(diǎn)的雙親，則還可以在結(jié)點(diǎn)結(jié)構(gòu)中增加一個(gè)指向其雙親結(jié)點(diǎn)的指針域。 利用這兩種結(jié)點(diǎn)結(jié)構(gòu)所得的二叉樹的存儲(chǔ)結(jié)構(gòu)分別稱之為 二叉鏈表 和三叉鏈表。

//二叉樹的二叉鏈表存儲(chǔ)表示
typedefstruct BiTNode
{
    TElemType data;		//數(shù)據(jù)域
    struct BiTNode *lchild, *rchild      //左右孩子指針
}BiTNode,*BiTree;

2.5 二叉樹的遍歷

在二叉樹的一些應(yīng)用中，常常要求在樹中查找具有某種特征的結(jié)點(diǎn)，或者對(duì)樹中全部結(jié)點(diǎn)逐一進(jìn)行某種處理。回顧二叉樹的遞歸定義可知，二叉樹是由三個(gè)基本單元組成： 根節(jié)點(diǎn)、左子樹和右子樹 ，因此，二叉樹的遍歷分為先（根）序遍歷、中（根）序遍歷、后（根）序遍歷和層次遍歷。

2.5.1 先（根）序遍歷

若二叉樹為空，則空操作，否則：

訪問(wèn)根結(jié)點(diǎn)；
先序遍歷左子樹；
先序遍歷右子樹；

2.5.2 中（根）序遍歷

若二叉樹為空，則空操作，否則：

中序遍歷左子樹；
訪問(wèn)根結(jié)點(diǎn)；
中序遍歷右子樹；

2.5.3 后（根）序遍歷

若二叉樹為空，則空操作，否則：

后序遍歷左子樹；
后序遍歷右子樹；
訪問(wèn)根結(jié)點(diǎn)；

2.5.4 層次遍歷

初始化一個(gè)隊(duì)列；
根結(jié)點(diǎn)入隊(duì)；
若隊(duì)列非空，則隊(duì)頭結(jié)點(diǎn)出隊(duì)，訪問(wèn)該結(jié)點(diǎn)，并將其左、右孩子插入隊(duì)尾；
重復(fù)上一步，直到隊(duì)列為空。

2.6 線索二叉樹

在遍歷二叉樹時(shí)，要想找到某個(gè)結(jié)點(diǎn)的前驅(qū)和后繼的信息，得運(yùn)用二叉樹已知的遍歷方法從頭開始遍歷，然后在遍歷的過(guò)程中動(dòng)態(tài)獲取其結(jié)點(diǎn)的前驅(qū)和后繼的信息，那有沒(méi)有一種方法是已知該結(jié)點(diǎn)就已經(jīng)知道其前驅(qū)和后繼的信息了呢？答案肯定是有的，為了解決二叉樹遍歷時(shí)所存在的一些問(wèn)題，線索二叉樹也孕育而生。那什么是 線索二叉樹 呢？

簡(jiǎn)單理解就是利用空鏈域來(lái)存放結(jié)點(diǎn)的前驅(qū)和后繼的信息，方便尋找前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)，提高遍歷效率。因?yàn)閚個(gè)結(jié)點(diǎn)的二叉樹，有n+1 n+1 n+1個(gè)空鏈域，所以可以利用這些空鏈域來(lái)記錄前驅(qū)，后繼的信息。若結(jié)點(diǎn)有左子樹，則其lchild lchildlchild域指示其左孩子，否則令lchild lchildlchild域指示其前驅(qū)；若結(jié)點(diǎn)有右子樹，則其rchild rchildrchild域指示其右孩子，否則令rchild rchildrchild域指示其后繼。為了避免混淆，尚需改變結(jié)點(diǎn)結(jié)構(gòu)，增加兩個(gè)標(biāo)志域。

以這種結(jié)點(diǎn)結(jié)構(gòu)構(gòu)成的二叉鏈表作為二叉樹的存儲(chǔ)結(jié)構(gòu)，叫做 線索鏈表 。其中指向結(jié)點(diǎn)前驅(qū)和后繼的指針，叫做線索。加上線索的二叉樹又稱之為 線索二叉樹（Threaded Binary Tree） 。對(duì)二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過(guò)程叫做 線索化 。

在線索樹上進(jìn)行遍歷，只要先找到序列中的第一個(gè)結(jié)點(diǎn)，然后依次找結(jié)點(diǎn)后繼直至其后繼為空時(shí)而止。

Part3樹和森林

3.1 樹的存儲(chǔ)結(jié)構(gòu)

3.1.1 雙親表示法

每個(gè)結(jié)點(diǎn)中保存指向 “雙親” 的指針；
優(yōu)點(diǎn)：查找指定結(jié)點(diǎn)的雙親很方便；
缺點(diǎn)：查找指定結(jié)點(diǎn)的孩子只能從頭遍歷。

//樹的雙親表示法存儲(chǔ)表示
#define MAX_TREE_SIZE 100
typedefstruct PTNode{//結(jié)點(diǎn)結(jié)構(gòu)
    TElemType data;
    int parent;     //雙親位置域
}PTNode;
typedefstruct{//樹結(jié)構(gòu)
    PTNode nodes[MAX_TREE_SIZE];
    int r,n;    //根的位置和結(jié)點(diǎn)數(shù)
}PTree;

3.1.2 孩子表示法（順序+鏈?zhǔn)酱鎯?chǔ)）

//樹的孩子表示法鏈表存儲(chǔ)表示
typedefstruct CTNode{//孩子結(jié)點(diǎn)
    int child;
    struct CTNode *next;
}*ChildPtr;
typedefstruct{
    TElemType data;
    ChildPtr firstchild;    //孩子鏈表頭指針
}CTBox;
typedefstruct{
    CTBox nodes[MAX_TREE_SIZE];
    int n,r;        //結(jié)點(diǎn)數(shù)和根的位置
}CTree;

3.1.3 子兄弟表示法（鏈?zhǔn)酱鎯?chǔ)）

優(yōu)點(diǎn)：可以利用二叉樹操作來(lái)處理樹

//樹的孩子兄弟表示法鏈表存儲(chǔ)表示
typedefstruct CSNode{//孩子結(jié)點(diǎn)
    ElemType data;
    struct CSNode *firstchild, *nextsibling;
}CSNode,*CSTree;

3.2 樹和森林的遍歷

3.2.1 樹的遍歷

樹的 先根遍歷 ：若樹非空、先訪問(wèn)根結(jié)點(diǎn)，再依次對(duì)每棵子樹進(jìn)行先根遍歷；
樹的 后根遍歷 ：若樹非空、先依次對(duì)每棵子樹進(jìn)行后根遍歷，最后再訪問(wèn)根結(jié)點(diǎn)。
樹的 層次遍歷 （用隊(duì)列實(shí)現(xiàn)）：

若樹非空，則根結(jié)點(diǎn)入隊(duì)；
若隊(duì)列非空，隊(duì)頭元素出隊(duì)并訪問(wèn)，同時(shí)將該元素的孩子依次入隊(duì)；
重復(fù)2直到隊(duì)列為空。

3.2.2 森林的遍歷

（1）先序遍歷森林

若森林非空，則可按照下述規(guī)則遍歷：

訪問(wèn)森林中第一棵樹的根結(jié)點(diǎn)；
先序遍歷第一棵樹中根結(jié)點(diǎn)的子樹森林；
先序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。

（2）中序遍歷森林

若森林非空，則可按照下述規(guī)則遍歷：

中序遍歷森林中第一顆樹的根結(jié)點(diǎn)的子樹森林；
訪問(wèn)第一棵樹的根結(jié)點(diǎn)；
中序遍歷除去第一棵樹的根結(jié)點(diǎn)的子樹森林。

Part4 哈夫曼樹

哈夫曼（Huffman）樹 ，又稱為 最優(yōu)樹 ，是一類帶權(quán)路徑長(zhǎng)度最短的樹。

4.1 最優(yōu)二叉樹（哈夫曼樹）

假設(shè)有nnn個(gè)權(quán)值( W1，W2，???????，Wm) (W1，W2，·······，Wm)(W1，W2，???????，Wm)，試構(gòu)造一棵有n個(gè)葉子結(jié)點(diǎn)的二叉樹，每個(gè)葉子結(jié)點(diǎn)帶權(quán)值為WiWiWi，則其中帶權(quán)路徑長(zhǎng)度WPL最小的二叉樹稱為最優(yōu)二叉樹或哈夫曼樹。

路徑和路徑長(zhǎng)度的概念

從樹中的一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支構(gòu)成這兩個(gè)結(jié)點(diǎn)之間的路徑，路徑上的分支數(shù)目稱之為 路徑長(zhǎng)度 。 樹的路徑長(zhǎng)度 是從樹根到每一個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度之和。

結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度為該結(jié)點(diǎn)到樹根之間的路徑長(zhǎng)度與結(jié)點(diǎn)上權(quán)值的乘積， 樹的帶權(quán)路徑長(zhǎng)度 為樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和，通常記作WPL。

樹的帶權(quán)路徑長(zhǎng)度

4.2 哈夫曼樹的構(gòu)造

根據(jù)給定的nnn個(gè)權(quán)值( W1，W2，??????，Wn)(W1，W2，······，Wn)(W1，W2，??????，Wn)構(gòu)成的n棵二叉樹的集合F = (T1，T2，??????，Tn)F=(T1，T2，······，Tn)F=(T1，T2，??????，T**n)，其中每棵二叉樹Ti中只有一個(gè)帶權(quán)為WiWiWi的根結(jié)點(diǎn)，其左右子樹均為空。

在F中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的樹作為左右子樹構(gòu)造一棵新的二叉樹，且置新的二叉樹的根結(jié)點(diǎn)的權(quán)值為其左、右子樹上根結(jié)點(diǎn)的權(quán)值之和。

在F中刪除這兩棵樹，同時(shí)將新得到的二叉樹加入FFF中。

重復(fù)上述2和3，直到FFF只喊一棵樹為止，這棵樹便是哈夫曼樹。

4.3 哈夫曼編碼

對(duì)于任意一棵二叉樹來(lái)說(shuō)，把二叉樹上的所有分支都進(jìn)行編號(hào)，將所有左分支都標(biāo)記為0，所有右分支都標(biāo)記為1。（左0右1）`那么對(duì)于樹上的任何一個(gè)結(jié)點(diǎn)，都可以根據(jù)從根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑唯一確定一個(gè)編號(hào)。對(duì)于哈夫曼樹上的葉子結(jié)點(diǎn)，根據(jù)從根結(jié)點(diǎn)到該葉子結(jié)點(diǎn)的路徑所確定的一個(gè)編號(hào)，就是該葉子結(jié)點(diǎn)的哈夫曼編碼。

Part5 總結(jié)

本節(jié)文章到此結(jié)束，在數(shù)據(jù)結(jié)構(gòu)與算法中，樹與二叉樹這一章是比較重要且晦澀難懂的一章，本篇文章知識(shí)點(diǎn)較多，有些寫的也不是很全面。希望大家在閱讀的時(shí)候能多看看圖，多理解，結(jié)合圖像表達(dá)來(lái)理解理論知識(shí)。其重點(diǎn)是二叉樹的所有相關(guān)知識(shí)，在實(shí)際開發(fā)中，二叉樹的應(yīng)用較為廣泛，希望我的文章對(duì)大家學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)能有所幫助，希望大家都能有所收獲。

聲明：本文內(nèi)容及配圖由入駐作者撰寫或者入駐合作網(wǎng)站授權(quán)轉(zhuǎn)載。文章觀點(diǎn)僅代表作者本人，不代表電子發(fā)燒友網(wǎng)立場(chǎng)。文章及其配圖僅供工程師學(xué)習(xí)之用，如有內(nèi)容侵權(quán)或者其他違規(guī)問(wèn)題，請(qǐng)聯(lián)系本站處理。舉報(bào)投訴

計(jì)算機(jī)

計(jì)算機(jī)

+關(guān)注

關(guān)注
19

文章
7520

瀏覽量
88221
終端

終端

+關(guān)注

關(guān)注
1

文章
1145

瀏覽量
29927
數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)

+關(guān)注

關(guān)注
3

文章
573

瀏覽量
40158
二叉樹

二叉樹

+關(guān)注

關(guān)注
0

文章
74

瀏覽量
12349

評(píng)論

相關(guān)推薦

數(shù)據(jù)結(jié)構(gòu)：樹和二叉樹的定義(1)#結(jié)構(gòu)數(shù)據(jù)

數(shù)據(jù)結(jié)構(gòu)與算法

學(xué)習(xí)硬聲知識(shí)

發(fā)布于 :2022年12月18日 07:43:15

數(shù)據(jù)結(jié)構(gòu)：樹和二叉樹的定義(2)#結(jié)構(gòu)數(shù)據(jù)

數(shù)據(jù)結(jié)構(gòu)與算法

學(xué)習(xí)硬聲知識(shí)

發(fā)布于 :2022年12月18日 07:43:44

數(shù)據(jù)結(jié)構(gòu)：樹和二叉樹的定義(3)#結(jié)構(gòu)數(shù)據(jù)

數(shù)據(jù)結(jié)構(gòu)與算法

學(xué)習(xí)硬聲知識(shí)

發(fā)布于 :2022年12月18日 07:44:15

數(shù)據(jù)結(jié)構(gòu)與算法：4.1.1 樹與二叉樹的定義(1)#結(jié)構(gòu)數(shù)據(jù)

數(shù)據(jù)結(jié)構(gòu)與算法

學(xué)習(xí)硬聲知識(shí)

發(fā)布于 :2022年12月18日 11:33:34

數(shù)據(jù)結(jié)構(gòu)與算法：4.1.1 樹與二叉樹的定義(2)#結(jié)構(gòu)數(shù)據(jù)

數(shù)據(jù)結(jié)構(gòu)與算法

學(xué)習(xí)硬聲知識(shí)

發(fā)布于 :2022年12月18日 11:34:02

數(shù)據(jù)結(jié)構(gòu)與分析：[4.1]--樹和二叉樹的定義(1)#硬聲創(chuàng)作季

數(shù)據(jù)結(jié)構(gòu)

學(xué)習(xí)電子

發(fā)布于 :2022年12月24日 16:36:43

數(shù)據(jù)結(jié)構(gòu)與分析：[4.1]--樹和二叉樹的定義(2)#硬聲創(chuàng)作季

數(shù)據(jù)結(jié)構(gòu)

學(xué)習(xí)電子

發(fā)布于 :2022年12月24日 16:37:10

詳解電源二叉樹到底是什么

作為數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)，樹分很多種，像 AVL 樹、紅黑樹、二叉搜索樹....今天我想分享的是關(guān)于二叉樹

發(fā)表于 06-06 15:05 ?1w次閱讀

二叉樹操作的相關(guān)知識(shí)和代碼詳解

樹是數(shù)據(jù)結(jié)構(gòu)中的重中之重，尤其以各類二叉樹為學(xué)習(xí)的難點(diǎn)。在面試環(huán)節(jié)中，二叉樹也是必考的模塊。本文主要講二叉樹操作的相關(guān)知識(shí)，梳理面試常考的內(nèi)容。請(qǐng)大家跟隨小編一起來(lái)復(fù)習(xí)吧。本篇針對(duì)面

發(fā)表于 12-12 11:04 ?2060次閱讀

二叉樹的前序遍歷非遞歸實(shí)現(xiàn)

我們之前說(shuō)了二叉樹基礎(chǔ)及二叉的幾種遍歷方式及練習(xí)題，今天我們來(lái)看一下二叉樹的前序遍歷非遞歸實(shí)現(xiàn)。前序遍歷的順序是，對(duì)于樹中的某節(jié)點(diǎn)，先遍歷該節(jié)點(diǎn)，然后再遍歷其左子樹，最后遍歷其右子

發(fā)表于 05-28 13:59 ?1975次閱讀

C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)：什么是二叉樹？

完全二叉樹：完全二叉樹是效率很高的數(shù)據(jù)結(jié)構(gòu)。對(duì)于深度為K，有n個(gè)節(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)每一個(gè)節(jié)點(diǎn)都與深度為K的滿二叉樹中編號(hào)從1至n的節(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱為完全

發(fā)表于 04-21 16:20 ?2546次閱讀

怎么就能構(gòu)造成二叉樹呢？

一直跟著公眾號(hào)學(xué)算法的錄友應(yīng)該知道，我在二叉樹：構(gòu)造二叉樹登場(chǎng)！，已經(jīng)講過(guò)，只有中序與后序和中序和前序可以確定一顆唯一的二叉樹。前序和后序是不能確定唯一的二叉樹的。

發(fā)表于 07-14 11:20 ?1618次閱讀

使用C語(yǔ)言代碼實(shí)現(xiàn)平衡二叉樹

這篇博客主要總結(jié)平衡二叉樹，所以，二叉排序樹知識(shí)不會(huì)提及，但是會(huì)用到。

發(fā)表于 09-21 11:00 ?1113次閱讀

二叉樹的代碼實(shí)現(xiàn)

二叉樹的主要操作有遍歷，例如有先序遍歷、中序遍歷、后序遍歷。在遍歷之前，就是創(chuàng)建一棵二叉樹，當(dāng)然，還需要有刪除二叉樹的算法。

發(fā)表于 01-18 10:41 ?1243次閱讀

C++自定義二叉樹并輸出二叉樹圖形

使用C++構(gòu)建一個(gè)二叉樹并輸出。

發(fā)表于 01-10 16:29 ?1772次閱讀

搜索歷史

樹與二叉樹的定義

Part1 樹

1.1 樹的定義

1.2 樹的基本術(shù)語(yǔ)

1.3 有序樹和無(wú)序樹

1.4 森林

Part2 二叉樹

2.1 二叉樹的定義

2.2 二叉樹的性質(zhì)

2.3 二叉樹的分類

2.3.1 滿二叉樹

2.3.2 完全二叉樹

2.3.3 二叉排序樹

2.3.4 平衡二叉樹

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

2.4.1 順序存儲(chǔ)結(jié)構(gòu)

2.4.2 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

2.5 二叉樹的遍歷

2.5.1 先（根）序遍歷

2.5.2 中（根）序遍歷

2.5.3 后（根）序遍歷

2.5.4 層次遍歷

2.6 線索二叉樹

Part3樹和森林

3.1 樹的存儲(chǔ)結(jié)構(gòu)

3.1.1 雙親表示法

3.1.2 孩子表示法（順序+鏈?zhǔn)酱鎯?chǔ)）

3.1.3 子兄弟表示法（鏈?zhǔn)酱鎯?chǔ)）

3.2 樹和森林的遍歷

3.2.1 樹的遍歷

3.2.2 森林的遍歷

Part4 哈夫曼樹

4.1 最優(yōu)二叉樹（哈夫曼樹）

4.2 哈夫曼樹的構(gòu)造

4.3 哈夫曼編碼

Part5 總結(jié)

評(píng)論