標(biāo)題：二叉樹的思路及代碼實(shí)現(xiàn)
作者：@Ggggggtm
寄語：與其忙著訴苦，不如低頭趕路，奮路前行，終將遇到一番好風(fēng)景
文章目錄
一、樹的概念及結(jié)構(gòu)
二、二叉樹的概念及結(jié)構(gòu)
2、1?二叉樹的概念
2、2 二叉樹的特點(diǎn)
2、3 二叉樹的結(jié)構(gòu)（圖片）
2、4 特殊的二叉樹
三、二叉樹的代碼及思路實(shí)現(xiàn)
3、1 二叉樹的存儲結(jié)構(gòu)
3、1、1 二叉樹的順序存儲結(jié)構(gòu)
3、1、2 二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)
3、2 二叉樹鏈?zhǔn)浇Y(jié)構(gòu)的實(shí)現(xiàn)
3、2、1 定義結(jié)構(gòu)體
3、2、2 自定義一個二叉樹
3、2、3 前序遍歷
3、2、4 中序遍歷
3、2、5 后序遍歷
3、2、6 求樹中節(jié)點(diǎn)的個數(shù)
3、2、7 求樹中葉節(jié)點(diǎn)的個數(shù)
3、3 二叉樹的性質(zhì)
一、樹的概念及結(jié)構(gòu)
? 二叉樹是樹的一種，所以在學(xué)習(xí)二叉樹之前我們先了解一下樹的概念及結(jié)構(gòu)。
? 樹是一種 非線性 的數(shù)據(jù)結(jié)構(gòu)，它是由 n （ n>=0 ）個有限節(jié)點(diǎn)組成一個具有層次關(guān)系的集合。 把它 叫做樹是因?yàn)樗雌饋硐褚豢玫箳斓臉?，也就是說它是根朝上，而葉朝下的 。
- 有一個特殊的結(jié)點(diǎn)，稱為根結(jié)點(diǎn)，根節(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)；
- 除根節(jié)點(diǎn)外，其余結(jié)點(diǎn)被分成M(M>0)個互不相交的集合T1、T2、……、Tm，其中每一個集合Ti(1<= i <= m)又是一棵結(jié)構(gòu)與樹類似的子樹。每棵子樹的根結(jié)點(diǎn)有且只有一個前驅(qū)，可以 有0個或多個后繼；
- 因此，樹是遞歸定義的。??
這里還有我們熟知的樹中的一些概念：
- 節(jié)點(diǎn)的度：一個節(jié)點(diǎn)含有的子樹的個數(shù)稱為該節(jié)點(diǎn)的度； 如上圖：A的為6；
? 在這里我們要注意樹與非樹的區(qū)別是；
- 子樹是不相交的；
- 除了根結(jié)點(diǎn)外，每個節(jié)點(diǎn)有且僅有一個父結(jié)點(diǎn)；
- 一顆N個結(jié)點(diǎn)的樹有N-1條邊。
以下我給大家舉幾個樹和非樹的例子，可以先簡單了解以下。
樹：
非樹：
二、二叉樹的概念及結(jié)構(gòu)
2、1?二叉樹的概念
? 一棵二叉樹是結(jié)點(diǎn)的一個有限集合，該集合或者為空，或者是由一個根節(jié)點(diǎn)加上兩棵別稱為左子樹和右子樹的二叉樹組成。
2、2 二叉樹的特點(diǎn)
- 每個結(jié)點(diǎn)最多有兩棵子樹，即二叉樹不存在度大于2的結(jié)點(diǎn)。
- 二叉樹的子樹有左右之分，其子樹的次序不能顛倒。
2、3 二叉樹的結(jié)構(gòu)（圖片）
2、4 特殊的二叉樹
- 滿二叉樹：一個二叉樹，如果每一個層的結(jié)點(diǎn)數(shù)都達(dá)到最大值，則這個二叉樹就是滿二叉 樹。也就是說，如果一個二叉樹的層數(shù)為K，且結(jié)點(diǎn)總數(shù)是(2^k) -1 ，則它就是滿二叉樹。
- 完全二叉樹：完全二叉樹是效率很高的數(shù)據(jù)結(jié)構(gòu)，完全二叉樹是由滿二叉樹而引出來的。對 于深度為K的，有n個結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個結(jié)點(diǎn)都與深度為K的滿二叉樹中編號 從1至n的結(jié)點(diǎn)一一對應(yīng)時(shí)稱之為完全二叉樹。 要注意的是滿二叉樹是一種特殊的完全二叉樹。
三、二叉樹的代碼及思路實(shí)現(xiàn)
3、1 二叉樹的存儲結(jié)構(gòu)
? ?二叉樹一般可以使用兩種結(jié)構(gòu)存儲，一種順序結(jié)構(gòu)，一種鏈?zhǔn)浇Y(jié)構(gòu)。
3、1、1 二叉樹的順序存儲結(jié)構(gòu)
? 順序結(jié)構(gòu)存儲就是使用 數(shù)組來存儲 ，一般使用數(shù)組 只適合表示完全二叉樹 ，因?yàn)椴皇峭耆鏄?會有空間的浪費(fèi)。而現(xiàn)實(shí)中使用中只有堆才會使用數(shù)組來存儲。二叉樹順序存儲在物理上是一個數(shù)組，在邏輯上是一顆二叉樹。
3、1、2 二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)
? 二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)是指，用鏈表來表示一棵二叉樹，即用鏈來指示元素的邏輯關(guān)系。 通常的方法是鏈表中每個結(jié)點(diǎn)由三個域組成，數(shù)據(jù)域和左右指針域，左右指針分別用來給出該結(jié)點(diǎn)左孩子和右孩子所在的鏈結(jié)點(diǎn)的存儲地址 。鏈?zhǔn)浇Y(jié)構(gòu)又分為二叉鏈和三叉鏈，當(dāng)前我們學(xué)習(xí)中一般都是二叉鏈。
3、2 二叉樹鏈?zhǔn)浇Y(jié)構(gòu)的實(shí)現(xiàn)
? 二叉樹的鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)都有哪些模塊呢？接下來我簡單的給大家總結(jié)一下：
- 定義結(jié)構(gòu)體；
- 自定義一個二叉樹；
- 前序遍歷；
- 中序遍歷；
- 后序遍歷；
- 求樹中節(jié)點(diǎn)的個數(shù)；
- 求葉節(jié)點(diǎn)的個數(shù)。
接下來我們來看一下各個模塊實(shí)現(xiàn)的細(xì)節(jié)以及詳解。
3、2、1 定義結(jié)構(gòu)體
? ?定義結(jié)構(gòu)體時(shí)，由上面的鏈?zhǔn)酱鎯Y(jié)構(gòu)我們直到該結(jié)構(gòu)體應(yīng)該包含一個存儲數(shù)據(jù)的變量，和指向左右分支節(jié)點(diǎn)的指針；我們看代碼實(shí)現(xiàn)。
typedef char BTDataType;
typedef struct BinaryTreeNode
{
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
BTDataType data;
}BTNode;3、2、2 自定義一個二叉樹
? 首先我們自己要有一個二叉樹，簡單的二叉樹即可。因?yàn)橄旅娴牟僮鞫际窃诙鏄渖线M(jìn)行的。這里給出一個簡單的二叉樹，如下圖及代碼實(shí)現(xiàn)：
BTNode* A = (BTNode*)malloc(sizeof(BTNode));
A->data = 'A';
A->left = NULL;
A->right = NULL;
BTNode* B = (BTNode*)malloc(sizeof(BTNode));
B->data = 'B';
B->left = NULL;
B->right = NULL;
BTNode* C = (BTNode*)malloc(sizeof(BTNode));
C->data = 'C';
C->left = NULL;
C->right = NULL;
BTNode* D = (BTNode*)malloc(sizeof(BTNode));
D->data = 'D';
D->left = NULL;
D->right = NULL;
BTNode* E = (BTNode*)malloc(sizeof(BTNode));
E->data = 'E';
E->left = NULL;
E->right = NULL;
A->left = B;
A->right = C;
B->left = D;
B->right = E;3、2、3 前序遍歷
? 什么是前序遍歷呢？我們先來看一下比較官方的解釋。
? NLR ：前序遍歷(Preorder Traversal 亦稱先序遍歷 )—— 訪問根結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹之前。? ?我在稍微解釋一下前序遍歷的概念：其實(shí)就是遍歷樹時(shí)，先訪問根，再訪問左子樹，最后訪問右子樹。這里要注意的是，當(dāng)我們訪問到左子樹時(shí)，我們把左子樹當(dāng)成一個新樹，同時(shí)也應(yīng)該滿足先訪問根，在訪問左子樹，最后訪問右子樹。我們發(fā)現(xiàn)前序遍歷先訪問了整個樹的跟后，再把整個樹左子樹訪問完后，再從下往上依次訪問整個數(shù)的右子樹。
???其實(shí)我們不難發(fā)現(xiàn)，當(dāng)一個子樹的節(jié)點(diǎn)為空時(shí)，我們就不再往下訪問了，開始從下往上訪問右子樹。這好像與遞歸有點(diǎn)類似哦！其實(shí)就是用遞歸實(shí)現(xiàn)的遍歷。我們結(jié)合著下圖理解一下：
?注：
- 往下的箭頭表示遞歸調(diào)用；
- 往上的箭頭表示返回，也就是歸。
下面我們看代碼的實(shí)現(xiàn)。
void PrevOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
printf("%c ", root->data);
PrevOrder(root->left);
PrevOrder(root->right);
}3、2、4 中序遍歷
? 什么是中序遍歷呢？同樣，我們先來看一下比較官方的解釋。
?? LNR：中序遍歷 (Inorder Traversal)—— 訪問根結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹的中 間。? 通俗來講，其實(shí)就是遍歷樹時(shí)， 先訪問左子樹，再訪問根，最后訪問右子樹。對比前序遍歷，中序遍歷與前序遍歷大同小異，只不過是訪問順序發(fā)生了變化。我們結(jié)合這下圖理解一下：
?注：
- 往下的箭頭表示遞歸調(diào)用；
- 往上的箭頭表示返回，也就是歸。
下面我們看代碼的實(shí)現(xiàn)。
void InOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
InOrder(root->left);
printf("%c ", root->data);
InOrder(root->right);
}3、2、5 后序遍歷
? 當(dāng)我們了解完前序遍歷和中序遍歷后，我們理解后序遍歷接很簡單了。?我們先看比較官方的解釋。
??LRN ：后序遍歷 (Postorder Traversal)—— 訪問根結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹之后。? 通俗來講，其實(shí)就是遍歷樹時(shí)， 先訪問左子樹，再右子樹，最后訪問根。我們直接看圖：
注：
- 往下的箭頭表示遞歸調(diào)用；
- 往上的箭頭表示返回，也就是歸。
下面我們看代碼的實(shí)現(xiàn)。
void PostOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
PostOrder(root->left);
PostOrder(root->right);
printf("%c ", root->data);
}3、2、6 求樹中節(jié)點(diǎn)的個數(shù)
? 我們在統(tǒng)計(jì)樹中節(jié)點(diǎn)的個數(shù)時(shí)，需要遍歷整個樹才行。當(dāng)然，遍歷整個樹也是需要用遞歸的。當(dāng)我們遇到某個節(jié)點(diǎn)為空時(shí)，我們就返回0，不是空時(shí)我們就返回1。我們結(jié)合著代碼一起理解一下。?
int TreeNodeSize(BTNode* root)
{
return root == NULL ? 0 : TreeNodeSize(root->left) + TreeNodeSize(root->right) + 1;
}3、2、7 求樹中葉節(jié)點(diǎn)的個數(shù)
? 我們知道，葉節(jié)點(diǎn)的度為0，也就是葉節(jié)點(diǎn)的左子樹和右子樹均為空。同樣，我們使用遞歸遍歷整個樹，遇到節(jié)點(diǎn)為空時(shí)返回零，遇到節(jié)點(diǎn)的左子樹和右子樹均為空返回1。我們看代碼的實(shí)現(xiàn)。?
int TreeLeafSize(BTNode* root)
{
if (root == 0)
return 0;
if (root->left == NULL && root->right == NULL)
return 1;
return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}3、3 二叉樹的性質(zhì)
? 通過上面對二叉樹的理解，我給大家總結(jié)出了二叉樹的一些性質(zhì)：文章來源：http://www.zghlxwxcb.cn/news/detail-788904.html
? 通過上面的學(xué)習(xí)，我們可以對二叉樹有一個新的認(rèn)識和理解，希望本編文章對您有所幫助，感謝閱讀ovo！?文章來源地址http://www.zghlxwxcb.cn/news/detail-788904.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)與算法之《二叉樹》詳解的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
