前言：
在上一篇博客中，我們已經(jīng)詳解學(xué)習(xí)了堆的基本知識(shí)，今天帶大家進(jìn)入的是二叉樹的另外一種存儲(chǔ)方式----“鏈?zhǔn)蕉鏄洹钡膶W(xué)習(xí)，主要用到的就是“遞歸思想”??！
前情回顧：
再看二叉樹基本操作前，再回顧下二叉樹的概念，二叉樹是：
- 空樹
- 非空：根節(jié)點(diǎn)，根節(jié)點(diǎn)的左子樹、根節(jié)點(diǎn)的右子樹組成的。
1.鏈?zhǔn)蕉鏄涞膶?shí)現(xiàn)
1.1前置說明
在學(xué)習(xí)二叉樹的基本操作前，需先要?jiǎng)?chuàng)建一棵二叉樹，然后才能學(xué)習(xí)其相關(guān)的基本操作。由于現(xiàn)在大家對(duì)二叉樹結(jié)構(gòu)掌握還不夠深入，為了降低大家學(xué)習(xí)成本，此處手動(dòng)快速創(chuàng)建一棵簡單的二叉樹，快速進(jìn)入二叉樹操作學(xué)習(xí)，等二叉樹結(jié)構(gòu)了解的差不多時(shí)，我們反過頭再來研究二叉樹真正的創(chuàng)建方式，代碼如下：
typedef int BTDataType;
typedef struct BinaryTreeNode
{
BTDataType _data;
struct BinaryTreeNode* _left;
struct BinaryTreeNode* _right;
}BTNode;
BTNode* CreatBinaryTree()
{
BTNode* node1 = BuyNode(1);
BTNode* node2 = BuyNode(2);
BTNode* node3 = BuyNode(3);
BTNode* node4 = BuyNode(4);
BTNode* node5 = BuyNode(5);
BTNode* node6 = BuyNode(6);
node1->_left = node2;
node1->_right = node4;
node2->_left = node3;
node4->_left = node5;
node4->_right = node6;
return node1;
}
注意：
上述代碼并不是創(chuàng)建二叉樹的方式，真正創(chuàng)建二叉樹方式后序詳解重點(diǎn)講解。
1.2結(jié)構(gòu)體以及聲明
跟我們之前學(xué)習(xí)的數(shù)據(jù)結(jié)構(gòu)一樣，我們?yōu)榱朔奖愦鎯?chǔ)各種數(shù)據(jù)類型，我們會(huì)先對(duì)堆存儲(chǔ)的數(shù)據(jù)類型進(jìn)行重定義，具體如下：
typedef int BTDataType;
在這里我們實(shí)現(xiàn)的是二叉樹鏈?zhǔn)酱鎯?chǔ)的存儲(chǔ)結(jié)構(gòu)。還是跟之前一樣，結(jié)構(gòu)體中有三個(gè)成員，一個(gè)指向當(dāng)前結(jié)點(diǎn)的值，還有兩個(gè)是指向當(dāng)前結(jié)點(diǎn)左孩子結(jié)點(diǎn)的指針以及指向右孩子結(jié)點(diǎn)的指針，具體如下：
typedef struct BinaryTreeNode
{
BTDataType data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;
具體如下圖：
2.遍歷二叉樹
2.1算法描述
遍歷二叉樹（ traversing binary tree ）是指按某條搜索路徑巡訪樹中每個(gè)結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被訪問一次，而且僅被訪問一次。
訪問的含義很廣，可以是對(duì)結(jié)點(diǎn)做各種處理，包括輸出結(jié)點(diǎn)的信息，對(duì)結(jié)點(diǎn)進(jìn)行運(yùn)算和修改等。遍歷二叉樹是二叉樹最基本的操作，也是二叉樹其他各種操作的基礎(chǔ)，遍歷的實(shí)質(zhì)是對(duì)二叉樹進(jìn)行線性化的過程，即遍歷的結(jié)果是將非線性結(jié)構(gòu)的樹中結(jié)點(diǎn)排成一個(gè)線性序列。由于二叉樹的每個(gè)結(jié)點(diǎn)都可能有兩棵子樹，因而需要尋找一種規(guī)律，以便使二叉樹的結(jié)點(diǎn)能排列在一個(gè)線性隊(duì)列上，從而便于遍歷
回顧二叉樹的遞歸定義可知，二叉樹是由3個(gè)基本單元組成：根結(jié)點(diǎn)、左子樹和右子樹。依次遍歷這三部分，便是遍歷了整個(gè)二叉樹。假如從 L 、 D 、 R 分別表示遍歷左子樹和遍歷右子樹，則可有 DLR 、 LDR 、 LRD 、 DRL 、 RDL 、 RLD 這6種遍歷二叉樹的方左后右，則只有前3種情況，分別稱之為先（根）序遍歷、中（根）序遍歷和后（根）遍歷?；诙鏄涞倪f歸定義，可得下述遍歷二叉樹的遞歸算法定義，我們一個(gè)一個(gè)認(rèn)識(shí)。
2.2先序遍歷
定義：
前序遍歷(Preorder Traversal 亦稱先序遍歷)——訪問根結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹之前。
思想：
若二叉樹為空，則空操作；否則
（1）訪問根結(jié)點(diǎn)
（2）先序遍歷左子樹
（3）先序遍歷右子樹
即考察到一個(gè)節(jié)點(diǎn)后，即刻輸出該節(jié)點(diǎn)的值，并繼續(xù)遍歷其左右子樹。(根左右)
舉例：
因?yàn)檫@是第一次認(rèn)識(shí)，我們舉個(gè)具體的例子來帶大家深入理解，我們以下圖為例來具體分析先序遍歷的步奏：
如圖所示，采用先序遍歷訪問這顆二叉樹的詳細(xì)過程為：
??1.訪問該二叉樹的根節(jié)點(diǎn)，找到 1；
??2.訪問節(jié)點(diǎn) 1 的左子樹，找到節(jié)點(diǎn) 2；
??3.訪問節(jié)點(diǎn) 2 的左子樹，找到節(jié)點(diǎn) 4；
??4.由于訪問節(jié)點(diǎn) 4 左子樹失敗，且也沒有右子樹，因此以節(jié)點(diǎn) 4 為根節(jié)點(diǎn)的子樹遍歷完成。但節(jié)點(diǎn) 2 還沒有遍歷其右子樹，因此現(xiàn)在開始遍歷，即訪問節(jié)點(diǎn) 5；
??5.由于節(jié)點(diǎn) 5 無左右子樹，因此節(jié)點(diǎn) 5 遍歷完成，并且由此以節(jié)點(diǎn) 2 為根節(jié)點(diǎn)的子樹也遍歷完成。現(xiàn)在回到節(jié)點(diǎn) 1 ，并開始遍歷該節(jié)點(diǎn)的右子樹，即訪問節(jié)點(diǎn) 3；
??6.訪問節(jié)點(diǎn) 3 左子樹，找到節(jié)點(diǎn) 6；
??7.由于節(jié)點(diǎn) 6 無左右子樹，因此節(jié)點(diǎn) 6 遍歷完成，回到節(jié)點(diǎn) 3 并遍歷其右子樹，找到節(jié)點(diǎn) 7；
??8.節(jié)點(diǎn) 7 無左右子樹，因此以節(jié)點(diǎn) 3 為根節(jié)點(diǎn)的子樹遍歷完成，同時(shí)回歸節(jié)點(diǎn) 1。由于節(jié)點(diǎn) 1 的左右子樹全部遍歷完成，因此整個(gè)二叉樹遍歷完成；
??因此，圖 中二叉樹采用先序遍歷得到的序列為：1 2 4 5 3 6 7
我們在通過另外一個(gè)例子圖解解遞歸算法:
代碼如下：
void PrevOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
printf("%d ", root->data);
PrevOrder(root->left);
PrevOrder(root->right);
}
2.3中序遍歷
定義：
中序遍歷(Inorder Traversal)——訪問根結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹之中（間）
思想：
若二叉樹為空，則空操作；否則
（1）中序遍歷左子樹
（2）訪問根結(jié)點(diǎn)
（3）中序遍歷右子樹
即考察到一個(gè)節(jié)點(diǎn)后，將其暫存，遍歷完左子樹后，再輸出該節(jié)點(diǎn)的值，然后遍歷右子樹。(左根右)
舉例：
以上圖為例，采用中序遍歷的思想遍歷該二叉樹的過程為：
??1.訪問該二叉樹的根節(jié)點(diǎn)，找到 1；
??2.遍歷節(jié)點(diǎn) 1 的左子樹，找到節(jié)點(diǎn) 2；
??3.遍歷節(jié)點(diǎn) 2 的左子樹，找到節(jié)點(diǎn) 4；
??4.由于節(jié)點(diǎn) 4 無左孩子，因此找到節(jié)點(diǎn) 4，并遍歷節(jié)點(diǎn) 4 的右子樹；
??5.由于節(jié)點(diǎn) 4 無右子樹，因此節(jié)點(diǎn) 2 的左子樹遍歷完成，訪問節(jié)點(diǎn) 2；
??6.遍歷節(jié)點(diǎn) 2 的右子樹，找到節(jié)點(diǎn) 5；
??7.由于節(jié)點(diǎn) 5 無左子樹，因此訪問節(jié)點(diǎn) 5 ，又因?yàn)楣?jié)點(diǎn) 5 沒有右子樹，因此節(jié)點(diǎn) 1 的左子樹遍歷完成，訪問節(jié)點(diǎn) 1 ，并遍歷節(jié)點(diǎn) 1 的右子樹，找到節(jié)點(diǎn) 3；
??8.遍歷節(jié)點(diǎn) 3 的左子樹，找到節(jié)點(diǎn) 6；
??9.由于節(jié)點(diǎn) 6 無左子樹，因此訪問節(jié)點(diǎn) 6，又因?yàn)樵摴?jié)點(diǎn)無右子樹，因此節(jié)點(diǎn) 3 的左子樹遍歷完成，開始訪問節(jié)點(diǎn) 3 ，并遍歷節(jié)點(diǎn) 3 的右子樹，找到節(jié)點(diǎn) 7；
??10.由于節(jié)點(diǎn) 7 無左子樹，因此訪問節(jié)點(diǎn) 7，又因?yàn)樵摴?jié)點(diǎn)無右子樹，因此節(jié)點(diǎn) 1 的右子樹遍歷完成，即整棵樹遍歷完成；
??因此，上圖中二叉樹采用中序遍歷得到的序列為：4 2 5 1 6 3 7
代碼如下：
void InOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
InOrder(root->left);
printf("%d ", root->data);
InOrder(root->right);
}
2.4后序遍歷
定義：
后序遍歷(Postorder Traversal)——訪問根結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹之后。
思想：
若二叉樹為空，則空操作；否則
（1）后序遍歷左子樹
（2）后序遍歷右子樹
（3）訪問根結(jié)點(diǎn)
即考察到一個(gè)節(jié)點(diǎn)后，將其暫存，遍歷完左右子樹后，再輸出該節(jié)點(diǎn)的值。(左右根)
舉例：
我們還是以之前的圖為例：
如上圖中，對(duì)此二叉樹進(jìn)行后序遍歷的操作過程為：
??從根節(jié)點(diǎn) 1 開始，遍歷該節(jié)點(diǎn)的左子樹（以節(jié)點(diǎn) 2 為根節(jié)點(diǎn)）；
??1.遍歷節(jié)點(diǎn) 2 的左子樹（以節(jié)點(diǎn) 4 為根節(jié)點(diǎn)）；
??2.由于節(jié)點(diǎn) 4 既沒有左子樹，也沒有右子樹，此時(shí)訪問該節(jié)點(diǎn)中的元素 4，并回退到節(jié)點(diǎn) 2 ，遍歷節(jié)點(diǎn) 2 的右子樹（以 5 為根節(jié)點(diǎn)）；
??3.由于節(jié)點(diǎn) 5 無左右子樹，因此可以訪問節(jié)點(diǎn) 5 ，并且此時(shí)節(jié)點(diǎn) 2 的左右子樹也遍歷完成，因此也可以訪問節(jié)點(diǎn) 2；
??4.此時(shí)回退到節(jié)點(diǎn) 1 ，開始遍歷節(jié)點(diǎn) 1 的右子樹（以節(jié)點(diǎn) 3 為根節(jié)點(diǎn)）；
??5.遍歷節(jié)點(diǎn) 3 的左子樹（以節(jié)點(diǎn) 6 為根節(jié)點(diǎn)）；
??6.由于節(jié)點(diǎn) 6 無左右子樹，因此訪問節(jié)點(diǎn) 6，并回退到節(jié)點(diǎn) 3，開始遍歷節(jié)點(diǎn) 3 的右子樹（以節(jié)點(diǎn) 7 為根節(jié)點(diǎn)）；
??7.由于節(jié)點(diǎn) 7 無左右子樹，因此訪問節(jié)點(diǎn) 7，并且節(jié)點(diǎn) 3 的左右子樹也遍歷完成，可以訪問節(jié)點(diǎn) 3；節(jié)點(diǎn) 1 的左右子樹也遍歷完成，可以訪問節(jié)點(diǎn) 1；
??
??由此，對(duì)上圖 中二叉樹進(jìn)行后序遍歷的結(jié)果為：4 5 2 6 7 3 1
代碼如下：
void PostOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
PostOrder(root->left);
PostOrder(root->right);
printf("%d ", root->data);
}
2.5層序遍歷
定義：
層序遍歷：除了先序遍歷、中序遍歷、后序遍歷外，還可以對(duì)二叉樹進(jìn)行層序遍歷。設(shè)二叉樹的根節(jié)點(diǎn)所在層數(shù)為1，層序遍歷就是從所在二叉樹的根節(jié)點(diǎn)出發(fā)，首先訪問第一層的樹根節(jié)點(diǎn)，然后從左到右訪問第2層上的節(jié)點(diǎn)，接著是第三層的節(jié)點(diǎn)，以此類推，自上而下，自左至右逐層訪問樹的結(jié)點(diǎn)的過程就是層序遍歷。
舉例：
解析：
層次遍歷如上圖中的二叉樹：
??1.根結(jié)點(diǎn) 1 入隊(duì)；
??2.根結(jié)點(diǎn) 1 出隊(duì)，出隊(duì)的同時(shí)，將左孩子 2 和右孩子 3 分別入隊(duì)；
??3.隊(duì)頭結(jié)點(diǎn) 2 出隊(duì)，出隊(duì)的同時(shí)，將結(jié)點(diǎn) 2 的左孩子 4 和右孩子 5 依次入隊(duì)；
??4.隊(duì)頭結(jié)點(diǎn) 3 出隊(duì)，出隊(duì)的同時(shí)，將結(jié)點(diǎn) 3 的左孩子 6 和右孩子 7 依次入隊(duì)；
??5.不斷地循環(huán)，直至隊(duì)列內(nèi)為空。
??由此，對(duì)上圖 中二叉樹進(jìn)行層序遍歷的結(jié)果為：1 2 3 4 5 6 7
層序遍歷不是一個(gè)遞歸過程，層序遍歷的實(shí)現(xiàn)可以借助隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)來進(jìn)行實(shí)現(xiàn)，具體如下：
void LevelOrder(BTNode* root)
{
Queue q;
QueueInit(&q);
if (root)
QueuePush(&q, root);
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
printf("%d ", front->data);
QueuePop(&q);
if (front->left)
{
QueuePush(&q, front->left);
}
if (front->right)
{
QueuePush(&q, front->right);
}
}
printf("\n");
QueueDestroy(&q);
}
2.6算法分析
無論是遞歸還是非遞歸遍歷二叉樹，因?yàn)槊總€(gè)結(jié)點(diǎn)被訪問一次，則不論按哪一種次序進(jìn)行遍歷，對(duì)于含有n個(gè)結(jié)點(diǎn)的二叉樹，其時(shí)間復(fù)雜度均為O(n)。所需輔助空間為遍歷過程中隊(duì)列的最大容量，即樹的深度，最壞情況下為n，則空間復(fù)雜度為O(n).
3.接口功能的實(shí)現(xiàn)
// 二叉樹節(jié)點(diǎn)個(gè)數(shù)
int BinaryTreeSize(BTNode* root);
// 二叉樹葉子節(jié)點(diǎn)個(gè)數(shù)
int BinaryTreeLeafSize(BTNode* root);
// 二叉樹第k層節(jié)點(diǎn)個(gè)數(shù)
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉樹查找值為x的節(jié)點(diǎn)
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
//二叉樹的高度
int TreeHeight(BTNode* root)
3.1二叉樹節(jié)點(diǎn)個(gè)數(shù)
思想：
這里需要用到遞歸的思想去進(jìn)行解決，進(jìn)行一個(gè)分塊求解然后再加起來就可以了。單次邏輯是只要求出左子樹結(jié)點(diǎn)個(gè)數(shù)，再加上右子樹節(jié)點(diǎn)個(gè)數(shù)，最后再加1就得到二叉樹的總結(jié)點(diǎn)個(gè)數(shù)了。
int TreeSize2(BTNode* root)
{
return root == NULL ? 0 :
TreeSize2(root->left) + TreeSize2(root->right) + 1;
}
3.2二叉樹葉子節(jié)點(diǎn)個(gè)數(shù)
思想：
整體思想就是不斷向下遞歸找葉子結(jié)點(diǎn)，然后把左右子樹的葉子結(jié)點(diǎn)總個(gè)數(shù)加起來，然后在遞歸進(jìn)行展開。
程序的結(jié)束條件有兩個(gè)：
1.一個(gè)是遇到了葉子結(jié)點(diǎn)；
2.另一個(gè)是遇到NULL結(jié)點(diǎn)，需要返回0.
代碼如下 ：
// 葉子節(jié)點(diǎn)
int TreeLeafSize(BTNode* root)
{
if (root == NULL)
{
return 0;
}
if (root->left == NULL
&& root->right == NULL)
{
return 1;
}
return TreeLeafSize(root->left)
+ TreeLeafSize(root->right);
}
3.3二叉樹第k層節(jié)點(diǎn)個(gè)數(shù)
思想：
整體思路還是很簡單：
首先判斷一個(gè)傳進(jìn)來的根結(jié)點(diǎn)是否為空
當(dāng)k > 1 時(shí)，第k層的結(jié)點(diǎn)個(gè)數(shù)為其左孩子的第k - 1層 + 其右孩子的第k - 1層結(jié)點(diǎn)個(gè)數(shù)
當(dāng)k ==1時(shí)，return 1
代碼如下：
// 求第k層的節(jié)點(diǎn)個(gè)數(shù) k >= 1
int TreeKLevelSize(BTNode* root, int k)
{
if (root == NULL)
return 0;
if (k == 1)
return 1;
// k > 1 子樹的k-1
return TreeKLevelSize(root->left, k - 1)
+ TreeKLevelSize(root->right, k - 1);
}
3.4二叉樹查找值為x的節(jié)點(diǎn)
思想：
整體思路比較明顯，要么遍歷根節(jié)點(diǎn)，如果是則表示找到我們想要的值；要么就是遍歷完整個(gè)二叉樹都沒有找到該結(jié)點(diǎn)，至此遞歸便結(jié)束。具體實(shí)現(xiàn)就是根節(jié)點(diǎn)data和x比較看是否相等，相等我們立馬返回；不相等就拿左子樹根節(jié)點(diǎn)的data和x比較，如果還不相等，我們就拿右子樹根節(jié)點(diǎn)的data和x進(jìn)行比較，如果最后還是沒有找到，則返回NULL
代碼如下：
BTNode* TreeFind(BTNode* root, BTDataType x)
{
if (root == NULL)
return NULL;
if (root->data == x)
return root;
struct BinaryTreeNode* ret1 = TreeFind(root->left, x);
if (ret1)
return ret1;
struct BinaryTreeNode* ret2 = TreeFind(root->right, x);
if (ret2)
return ret2;
return NULL;
}
3.5二叉樹的高度
思想：
整體思想就是先比較出左子樹和右子樹中高度高的那個(gè)，最后在加上根節(jié)點(diǎn)的高度【1】即可！
代碼如下：
int TreeHeight(BTNode* root)
{
if (root == NULL)
{
return 0;
}
int leftHeight = TreeHeight(root->left);
int rightHeight = TreeHeight(root->right);
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
3.6二叉樹的銷毀
思想：
如果開始時(shí)從根節(jié)點(diǎn)開始往下銷毀，現(xiàn)將根節(jié)點(diǎn)銷毀了之后，那左右子樹不是找不到了，不符合我們所需要的。因此我們應(yīng)該先從左右子樹開始，但是這樣又會(huì)遇到一個(gè)問題，對(duì)于左子樹來說它又可以作為一個(gè)根結(jié)點(diǎn)，依舊是需要先去銷毀其左右子樹，右子樹也是一樣，因此這就又成了一個(gè)遞歸的問題。跟我們后序遍歷的思想就不謀而合了！?。?/p>
代碼如下：
void DestroyTree(BTNode* root)
{
if (root == NULL) //if(!root)
return;
DestroyTree(root->lchild);
DestroyTree(root->rchild);
free(root);
}
3.7判斷是否為完全二叉樹
思想：
通過前面的學(xué)習(xí)，我們已經(jīng)對(duì)完全的基本概念有了一定的了解。因此，這里在進(jìn)行判斷是我們可以考慮使用層序遍歷的思想去進(jìn)行解決。
具體：
首先二叉樹元素全部入隊(duì)，如果隊(duì)列中的元素有空結(jié)點(diǎn)，并且空結(jié)點(diǎn)后面有不為空的元素那就說明此二叉樹不是完全二叉樹；
如果后面的元素都是空結(jié)點(diǎn)，那就說明這個(gè)二叉樹是完全二叉樹
具體代碼如下：
```c
bool TreeComplete(BTNode* root)
{
Queue q;
QueueInit(&q);
if (root)
QueuePush(&q, root);
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
if (front == NULL)//遇到NULL，就可以開始判斷是否為完全二叉樹了
{
break;
}
else
{
QueuePush(&q, front->left);
QueuePush(&q, front->right);
}
}
//出到NULL以后，如果后面全是空，則是完全二叉樹，如果有非空結(jié)點(diǎn)，那就不是完全二叉樹
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
if (front != NULL)
{
QueueDestroy(&q);//防止內(nèi)存泄露
return false;
}
}
QueueDestroy(&q);
return true;
}
4.選擇題練習(xí)
1.某完全二叉樹按層次輸出（同一層從左到右）的序列為 ABCDEFGH 。該完全二叉樹的前序序列為（ ）
A ABDHECFG
B ABCDEFGH
C HDBEAFCG
D HDEBFGCA
解答：
標(biāo)記文本選A，根據(jù)層序遍歷的特點(diǎn)以及完全二叉樹的概念，我們可以改二叉樹為下圖：
2.二叉樹的先序遍歷和中序遍歷如下:先序遍歷: EFHIGJK ；中序遍歷: HFIEJKG 該二又樹根的右子樹的根是（）
A E
B F
C G
D H
解答：
選C。考察的是先序（根左右），中序（左根右）來推斷二叉樹的結(jié)構(gòu)。
根據(jù)題干中的先序和中序可以確定二叉樹的結(jié)構(gòu)。先序：確定E為二叉樹的根節(jié)點(diǎn)，中序：HFI為E的左子樹節(jié)點(diǎn)，JKG為E右子樹節(jié)點(diǎn)。
先序：GJK 中序：JKG 根據(jù)先序得出G為右子樹的根節(jié)點(diǎn)
3.設(shè)一棵二叉樹的中序遍歷序列：badce，后序遍歷序列：bdeca，則二叉樹先序遍歷序列為（ ）。
A FEDCBA
B CBAFED
C DEFCBA
D ABCDEF
解答：選A
前序遍歷：根結(jié)點(diǎn) —> 左子樹 —> 右子樹
中序遍歷：左子樹—> 根結(jié)點(diǎn) —> 右子樹
后序遍歷：左子樹 —> 右子樹 —> 根結(jié)點(diǎn)
既然后序遍歷和中序遍歷結(jié)果一樣，那就說明整棵二叉樹都沒有右子樹，所以整棵樹看起來就像是普通的鏈?zhǔn)浇Y(jié)構(gòu)一樣，如下圖：
5.OJ題練習(xí)
5.1 單值二叉樹（LeetCode 965題）
鏈接：單值二叉樹
題目：
如果二叉樹每個(gè)節(jié)點(diǎn)都具有相同的值，那么該二叉樹就是單值二叉樹。
只有給定的樹是單值二叉樹時(shí)，才返回 true；否則返回 false。
思路：
我們判斷一棵樹的所有節(jié)點(diǎn)都有相同的值，當(dāng)且僅當(dāng)對(duì)于樹的孩子結(jié)點(diǎn)都相等時(shí)才滿足相應(yīng)的條件（這樣根據(jù)傳遞性，所有節(jié)點(diǎn)都有相同的值）。 因此每次比較其根節(jié)點(diǎn)和其左右結(jié)點(diǎn)是否相等，若是發(fā)現(xiàn)不相等，立馬返回false，若是相等，則遞歸其左右子樹繼續(xù)比較，直到訪問最后的結(jié)點(diǎn)為NULL時(shí)，則得出此樹為單值二叉樹
代碼如下：
bool isUnivalTree(struct TreeNode* root){
if (!root) {
return true;
}
if (root->left) {
if (root->val != root->left->val || !isUnivalTree(root->left)) {
return false;
}
}
if (root->right) {
if (root->val != root->right->val || !isUnivalTree(root->right)) {
return false;
}
}
return true;
}
5.2檢查兩顆樹是否相同（LeetCode 100題）
鏈接：相同的樹
題目：
給你兩棵二叉樹的根節(jié)點(diǎn) p 和 q ，編寫一個(gè)函數(shù)來檢驗(yàn)這兩棵樹是否相同。
如果兩個(gè)樹在結(jié)構(gòu)上相同，并且節(jié)點(diǎn)具有相同的值，則認(rèn)為它們是相同的。
思路：
總體思想就是要比較兩個(gè)二叉樹相同，當(dāng)且僅當(dāng)兩個(gè)二叉樹的結(jié)構(gòu)完全相同，且所有對(duì)應(yīng)節(jié)點(diǎn)的值相同。如果滿足上述條件則判斷兩顆樹完全相同。
具體過程：
1.如果兩個(gè)二叉樹都為空，則兩個(gè)二叉樹相同。如果兩個(gè)二叉樹中有且只有一個(gè)為空，則兩個(gè)二叉樹一定不相同；
2.如果兩個(gè)二叉樹都不為空，那么首先判斷它們的根節(jié)點(diǎn)的值是否相同，若不相同則兩個(gè)二叉樹一定不同；
3.若相同，再遞歸的去分別判斷兩個(gè)二叉樹的左子樹和右子樹是否相同
代碼如下：
bool isSameTree(struct TreeNode* p, struct TreeNode* q){
if(p == NULL && q == NULL)//若是兩棵均為空樹，則表示相同
return true;
if(p == NULL || q == NULL)
return false;
if(p->val != q->val) //比較值是否相等
return false;
//遞歸左右子樹
return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
}
5.3 對(duì)稱二叉樹（LeetCode 101題）
鏈接：對(duì)稱二叉樹
題目：
給你一個(gè)二叉樹的根節(jié)點(diǎn) root ， 檢查它是否軸對(duì)稱。
思路：
對(duì)稱二叉樹也稱為【鏡像二叉樹】兩個(gè)樹在什么情況下互為鏡像？
1.它們的兩個(gè)根結(jié)點(diǎn)具有相同的值
2.每個(gè)樹的右子樹都與另一個(gè)樹的左子樹鏡像對(duì)稱
基本思想就是以根結(jié)點(diǎn)為對(duì)稱軸，遞歸進(jìn)行左子樹和右子樹中的元素的比較，如果都相同，則判斷是對(duì)稱二叉樹
代碼如下（我們這里復(fù)用了上述相同的樹的代碼思想）：
bool isSameTree(struct TreeNode* LeftTree, struct TreeNode* RightTree)
{
if(LeftTree == NULL && RightTree == NULL)
return true;
if(LeftTree == NULL || RightTree == NULL)
return false;
if(LeftTree->val != RightTree->val)
return false;
return isSameTree(LeftTree->left,RightTree->right)
&& isSameTree (LeftTree->right,RightTree->left);
}
bool isSymmetric(struct TreeNode* root){
if(root == NULL)
return true;
return isSameTree(root->left,root->right);
}
5.4另一顆樹的子樹（LeetCode 572題）
鏈接：另一顆樹的子樹
題目：
給你兩棵二叉樹 root 和 subRoot 。檢驗(yàn) root 中是否包含和 subRoot 具有相同結(jié)構(gòu)和節(jié)點(diǎn)值的子樹。如果存在，返回 true ；否則，返回 false 。
二叉樹 tree 的一棵子樹包括 tree 的某個(gè)節(jié)點(diǎn)和這個(gè)節(jié)點(diǎn)的所有后代節(jié)點(diǎn)。tree 也可以看做它自身的一棵子樹。
思路：
這道題直接暴力挺簡單的，首先判斷一個(gè)樹是否是另一棵樹的子樹，很明顯想到可以用遞歸：
1.先用跟節(jié)點(diǎn)去比較
2.不成功，遞歸用左孩子去比較
3.不成功，遞歸用右孩子去比較
代碼如下：
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
if (p == NULL && q == NULL)
return true;
if (p == NULL || q == NULL)
return false;
if (p->val != q->val)
return false;
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
if(root==NULL)
return false;
if(isSameTree(root,subRoot))
return true;
return isSubtree(root->left,subRoot) ||
isSubtree(root->right,subRoot);
}
大家可以發(fā)現(xiàn)，有了上述【相同的樹】之后，做這兩道題就很簡單！??！
5.5二叉樹的前序遍歷（LeetCode 144題）
鏈接：二叉樹的前序遍歷
題目：
給你二叉樹的根節(jié)點(diǎn) root ，返回它節(jié)點(diǎn)值的 前序 遍歷。
思路：
按照訪問根節(jié)點(diǎn)——左子樹——右子樹的方式遍歷這棵樹，而在訪問左子樹或者右子樹的時(shí)候，我們按照同樣的方式遍歷，直到遍歷完整棵樹。
此題要保存節(jié)點(diǎn)，所以需要先獲取節(jié)點(diǎn)個(gè)數(shù)，然后進(jìn)行前序遍歷，保存每一個(gè)節(jié)點(diǎn)值。
代碼如下：
void preorder(struct TreeNode* root,int* index,int* ret)
// index 當(dāng)做數(shù)組的下標(biāo) ret是數(shù)組名稱
{
if(NULL == root)
return;
else
{
ret[(*index)++] = root->val;
preorder(root->left,index,ret);
preorder(root->right,index,ret);
}
}
int* preorderTraversal(struct TreeNode* root, int* returnSize)
{
int* ret =(int*)malloc(100* sizeof(int));
*returnSize = 0;
preorder(root,returnSize,ret);
return ret;
}
5.6 二叉樹中序遍歷（LeetCode 94題）
鏈接：二叉樹中序遍歷
思路：
當(dāng)我們了解先序遍歷，中序遍歷在這里就直接給出代碼：
void inorder(struct TreeNode* root,int* index,int* ret)// index 當(dāng)做數(shù)組的下標(biāo) ret是數(shù)組名稱
{
if(NULL == root)
return;
else
{
inorder(root->left,index,ret);
ret[(*index)++] = root->val;
inorder(root->right,index,ret);
}
}
int* inorderTraversal(struct TreeNode* root, int* returnSize){
int* ret =(int*)malloc(100* sizeof(int));
*returnSize = 0;
inorder(root,returnSize,ret);
return ret;
}
5.7二叉樹的后序遍歷（LeetCode 145題）
鏈接：二叉樹的后序遍歷
思路：
后序遍歷也是一樣的，我們直接給出代碼：
void postorder(struct TreeNode* root,int* index,int* ret)// index 當(dāng)做數(shù)組的下標(biāo) ret是數(shù)組名稱
{
if(NULL == root)
return;
else
{
postorder(root->left,index,ret);
postorder(root->right,index,ret);
ret[(*index)++] = root->val;
}
}
int* postorderTraversal(struct TreeNode* root, int* returnSize){
int* ret =(int*)malloc(100* sizeof(int));
*returnSize = 0;
postorder(root,returnSize,ret);
return ret;
}
6.總結(jié)
在這里最重要的就是要我們掌握遞歸的基本思想。其實(shí)不管是哪種遍歷方式，我們最終的目的就是訪問所有的樹（子樹）的根節(jié)點(diǎn)，左孩子，右孩子（我們以左孩子節(jié)點(diǎn)為基準(zhǔn)，先序遍歷是在訪問左孩子節(jié)點(diǎn)之前打印節(jié)點(diǎn)，中序遍歷是在左孩子節(jié)點(diǎn)壓棧之后打印節(jié)點(diǎn)，后序遍歷是在訪問完左右孩子節(jié)點(diǎn)之后打印節(jié)點(diǎn)）。當(dāng)大家不懂時(shí)多畫圖理解（會(huì)有意想不到的效果喲?。。。?mark hidden color="red">文章來源：http://www.zghlxwxcb.cn/news/detail-808189.html
好了，本期博文就到這里了。如果覺得有用的話記得三連支持喲！！文章來源地址http://www.zghlxwxcb.cn/news/detail-808189.html
到了這里，關(guān)于【鏈?zhǔn)蕉鏄洹繑?shù)據(jù)結(jié)構(gòu)鏈?zhǔn)蕉鏄涞模ㄈf字詳解）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
