一、二叉樹的創(chuàng)建(偽)
在學習二叉樹的基本操作前，需先要創(chuàng)建一棵二叉樹，然后才能學習其相關的基本操作。由于現(xiàn)在大家對二叉樹結構掌握還不夠深入，且為了方便后面的介紹，此處手動快速創(chuàng)建一棵簡單的二叉樹，快速進入二叉樹操作學習，等二叉樹結構了解的差不多時，我們反過頭再來研究二叉樹真正的創(chuàng)建方式。
基于二叉樹的鏈式結構，于是可以先malloc動態(tài)開辟出二叉樹的每個節(jié)點并初始化，然后通過節(jié)點中的指針struct BinaryTreeNode* left（指向左樹）和struct BinaryTreeNode* right（指向右樹），將各個節(jié)點連接起來，最后大致模擬出了一棵二叉樹，代碼如下：
typedef int BTDataType;
typedef struct BinaryTreeNode
{
BTDataType data;
struct BinaryTreeNode* left; //左樹
struct BinaryTreeNode* right; //右樹
}BTNode;
BTNode* CreatBinaryTree()
{
//動態(tài)開辟節(jié)點
BTNode* node1 = BuyNode(1);
BTNode* node2 = BuyNode(2);
BTNode* node3 = BuyNode(3);
BTNode* node4 = BuyNode(4);
BTNode* node5 = BuyNode(5);
BTNode* node6 = BuyNode(6);
//鏈接節(jié)點
node1->left = node2;
node1->right = node4;
node2->left = node3;
node4->left = node5;
node4->right = node6;
return node1;
}
在實現(xiàn)二叉樹基本操作前，再回顧下二叉樹的概念，一棵二叉樹是結點的一個有限集合，該集合:
- 或者為空
- 由一個根節(jié)點加上兩棵分別稱為左子樹和右子樹的二叉樹組成
二叉樹滿足的條件：
- 二叉樹不存在度大于2的結點；
- 二叉樹的子樹有左右之分，次序不能顛倒，因此二叉樹是有序樹。
其余二叉樹的概念還請回顧：【數(shù)據(jù)結構和算法】—二叉樹（1）–樹概念及結構
從概念中可以看出，二叉樹定義是遞歸式的，因此后序基本操作中基本都是按照該概念實現(xiàn)的。
注意： 上述代碼并不是創(chuàng)建二叉樹的方式，真正創(chuàng)建二叉樹方式將在后面介紹。
二、二叉樹的遍歷
學習二叉樹結構，最簡單的方式就是遍歷。所謂二叉樹遍歷(Traversal)是按照某種特定的規(guī)則，依次對二叉樹中的節(jié)點進行相應的操作，并且每個節(jié)點只操作一次。 訪問結點所做的操作依賴于具體的應用問題。 遍歷是二叉樹上最重要的運算之一，也是二叉樹上進行其它運算的基礎。下圖可以理解為是二叉樹的前序遍歷：
按照規(guī)則，二叉樹的遍歷有：前序/中序/后序的遞歸結構遍歷：
- 前序遍歷(Preorder Traversal 亦稱先序遍歷)——訪問根結點的操作發(fā)生在遍歷其左右子樹之前。
- 中序遍歷(Inorder Traversal)——訪問根結點的操作發(fā)生在遍歷其左右子樹之中（間）。
- 后序遍歷(Postorder Traversal)——訪問根結點的操作發(fā)生在遍歷其左右子樹之后。
由于被訪問的結點必是某子樹的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解釋為根、根的左子樹和根的右子樹。 NLR、LNR和LRN分別又稱為先根遍歷、中根遍歷和后根遍歷。
2.1 前序遍歷
前序遍歷(Preorder Traversal 亦稱先序遍歷)——訪問根結點的操作發(fā)生在遍歷其左右子樹之前。 依據(jù)此規(guī)律我們便可如下遍歷二叉樹，為了方便觀察，每次遍歷到根節(jié)點都輸出一下：
// 二叉樹前序遍歷
void BinaryTreePrevOrder(BTNode* root)
{
if (root == NULL)
{
putchar('N');
return;
}
putchar(root->val); //訪問根節(jié)點
BinaryTreePrevOrder(root->left); //訪問左子樹
BinaryTreePrevOrder(root->right); //訪問右子樹
}
前序遍歷代碼，邏輯結構大致如下圖，可以參考一下：
在這利用遞歸思想來解決前序遍歷的問題，因為是前序遍歷（訪問順序依次是根節(jié)點，左子樹，右子樹），所以在進入下層遞歸前可以先輸出根節(jié)點。當進入左/右子樹時，會更新根節(jié)點（原為上層根節(jié)點的左/右孩子節(jié)點） 。二叉樹的葉子節(jié)點的左右孩子都為NULL，那么便可將遞歸的結束條件定為NULL。這便是前序遍歷的遞歸邏輯。
2.2 中序遍歷
中序遍歷(Inorder Traversal)——訪問根結點的操作發(fā)生在遍歷其左右子樹之中（間）。 與前序遍歷相似，只是訪問順序不同（依次是左子樹，根節(jié)點，右子樹），那么調整一下代碼順序即可，將輸出根節(jié)點值的操作(putchar(root->val);)，放在訪問左子樹之后。那么遞歸每次都會先進入左子樹，且最先打印的為葉子節(jié)點。代碼如下：
// 二叉樹中序遍歷
void BinaryTreeInOrder(BTNode* root)
{
if (root == NULL)
{
putchar('N');
return;
}
BinaryTreeInOrder(root->left); //訪問左子樹
putchar(root->val); //輸出根節(jié)點
BinaryTreeInOrder(root->right); //訪問右子樹
}
2.3 后序遍歷
后序遍歷(Postorder Traversal)——訪問根結點的操作發(fā)生在遍歷其左右子樹之后。 同樣與前序遍歷相似，訪問順序不同（依次是左子樹，右子樹，根節(jié)點），依此特性所以我們只需將輸出操作(putchar(root->val))放到最后，其余代碼不變。實現(xiàn)思想-遞歸完左子樹和右子樹后再輸出根節(jié)點。 代碼如下：
// 二叉樹后序遍歷
void BinaryTreePostOrder(BTNode* root)
{
if (root == NULL)
{
putchar('N');
return;
}
BinaryTreePostOrder(root->left); //訪問左子樹
BinaryTreePostOrder(root->right); //訪問右子樹
putchar(root->val); //輸出根節(jié)點
}
三種遍歷最后輸出的結果（圖中N表示遞歸時遇到了NULL）：
- 前序遍歷結果：1 2 3 4 5 6
- 中序遍歷結果：3 2 1 5 4 6
- 后序遍歷結果：3 2 5 6 4 1
- 設一課二叉樹的中序遍歷序列：badce，后序遍歷序列：bdeca，則二叉樹前序遍歷序列為 ( D )。
A adbce
B decab
C debac
D abcde解： 解題思想（給定兩種遍歷序列，求出另外一種）：我們可以根據(jù)各種遍歷方法的特性來求解。( 1 ) 根據(jù)后續(xù)遍歷序列找出根節(jié)點，因為后續(xù)遍歷最后才會輸出根，那么在序列的最后一個即為根節(jié)點
a；( 2 ) 接著在中序遍歷序列中找出根節(jié)點，然后劃分左子樹和右子樹；( 3 ) 然后再到后序遍歷序列中去除左子樹和根節(jié)點，那么得到的便是右子樹，并將其看為獨立的樹；( 4 ) 重復上述三步操作，直到排出完整的樹。
圖解如下：
解決此類問題最重要的還是要弄懂代碼的遞歸思想。
三、二叉樹節(jié)點個數(shù)及高度
3.1 二叉樹節(jié)點個數(shù)
求二叉樹的節(jié)點個數(shù)，利用的還是遞歸思想。我們可以將問題轉化為----根節(jié)點(1)，左子樹的節(jié)點個數(shù)(root->left)和右子樹的節(jié)點個數(shù)(root->right)的總結點個數(shù)。我們可以將根節(jié)點為空(root == NULL)作為遞歸結束的條件，并返回0(return 0)。 這種方法通常被稱為遞歸分治。
// 二叉樹節(jié)點個數(shù)
int BinaryTreeSize(BTNode* root)
{
if (root == NULL)
return 0;
return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}
代碼圖解：
3.2 二叉樹葉子節(jié)點個數(shù)
葉子節(jié)點概念：含有的子樹個數(shù)為0的節(jié)點。 如本次創(chuàng)建的二叉樹的節(jié)點3，節(jié)點5，節(jié)點6。
基于葉子節(jié)點的特性，同樣可以利用遞歸分治的方法，將問題同化為----左子樹的葉子節(jié)點個數(shù)和右子樹的葉子節(jié)點個數(shù)之和。
函數(shù)返回的條件：
-
當前節(jié)點(
root)的左子樹(root->left)和右子樹(root->right)都為空時(即!(root->left && root->right))，那么此節(jié)點為葉子節(jié)點，并返回1； -
當前節(jié)點為空節(jié)點(即
(root == NULL))，返回0； - 函數(shù)執(zhí)行到最后，返回當前樹的葉子節(jié)點數(shù)。
// 二叉樹葉子節(jié)點個數(shù)
int BinaryTreeLeafSize(BTNode* root)
{
if (root == NULL)
return 0;
if (!(root->left && root->right))
return 1;
return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}
代碼圖解：
3.3二叉樹第k層節(jié)點個數(shù)
既然是求第k層的節(jié)點個數(shù)，那我們便可以定義一個變量k，記錄當前函數(shù)所要遞歸的層數(shù)。既然k的值是變化的，那么可以將他作為函數(shù)的參數(shù)，每遞歸一層便讓他減一k - 1，那么當k的值到1時，便是我們所要求的二叉樹的第k層。
依據(jù)上述關系，便可以得出 函數(shù)返回的條件：
- 當遇到空節(jié)點時(
root == NULL)，返回0； -
當
k == 1時（說明到了二叉樹的第k層），且當前節(jié)點不為空(root != NULL)，那么便可返回1； - 函數(shù)執(zhí)行到了最后，返回統(tǒng)計到的符合條件的節(jié)點個數(shù)。
// 二叉樹第k層節(jié)點個數(shù)
int BinaryTreeLevelKSize(BTNode* root, int k)
{
if (root == NULL)
return 0;
if (k == 1 && root != NULL)
return 1;
return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}
根據(jù)函數(shù)返回條件不難發(fā)現(xiàn)，當k == 1時遞歸便不會繼續(xù)往下層執(zhí)行，這是因為此時函數(shù)必定會滿足兩個if條件中的一個，這也避免了遞歸到二叉樹的第k + 1層。
代碼圖解：
3.4 二叉樹查找值為x的節(jié)點
查找值為x的節(jié)點，可以將遞歸分治為----判斷當前節(jié)點，判斷左子樹，判斷右子樹。 那么當遇到空節(jié)點(root == NULL)就返回return NULL；如果遇到所要查找的值(root->val == x)就返回當前地址(return root)；那么如果都不滿足就繼續(xù)搜尋左子樹，然后右子樹；直到最后搜尋完整棵二叉樹，都沒有找到x，那么便返回NULL。
還需要注意的一個問題是，如果在遞歸過程中找到了目標值x，返回了當前地址root，但是現(xiàn)在只是回到了上一層遞歸的地方，返回值并不會被接收，而是繼續(xù)執(zhí)行下一個邏輯。 那么我們便可以用BTNode* ret1來接受函數(shù)的返回值，并判斷，當返回值(ret1)不為NULL時（即說明上一次遞歸時，找到了x）直接返回此值return ret1。
// 二叉樹查找值為x的節(jié)點
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
//空節(jié)點
if (root == NULL)
return NULL;
//值為x的節(jié)點
if (root->val == x)
return root;
//左子樹遞歸，ret接收返回值，并判斷
BTNode* ret1 = BinaryTreeFind(root->left, x);
if (ret1 != NULL)
return ret1;
//方法一：易于理解
//BTNode* ret2 = BinaryTreeFind(root->right, x);
//if (ret2 != NULL)
// return ret2;
return BinaryTreeFind(root->right, x);
return NULL;
}
代碼圖解：
四、二叉樹的創(chuàng)建(真)
通過上面對各種遍歷方法和遞歸思想的講解，相信使用遞歸來真正創(chuàng)建二叉樹也不難了，如下：
// 通過前序遍歷的數(shù)組"ABD##E#H##CF##G##"構建二叉樹
BTNode* BinaryTreeCreate(BTDataType* a, int* pi)
{
//判斷是否為空，即當a[*pi] == '#'時
if (a[*pi] == '#')
{
(*pi)++;
return NULL;
}
//動態(tài)開辟節(jié)點
BTNode* node = (BTNode*)malloc(sizeof(BTNode));
if (node == NULL)
{
perror("malloc()::fail");
exit(-1);
}//賦值并連接（遞歸）
node->val = a[*pi];
(*pi)++;
node->left = BinaryTreeCreate(a, pi);
node->right = BinaryTreeCreate(a, pi);
retur
上面介紹的二叉樹的一些函數(shù)的執(zhí)行結果如下：文章來源：http://www.zghlxwxcb.cn/news/detail-822371.html
另外還有一些較為復雜的函數(shù)將在下一篇文章中介紹。文章來源地址http://www.zghlxwxcb.cn/news/detail-822371.html
到了這里，關于【數(shù)據(jù)結構和算法】--- 二叉樹（3）--二叉樹鏈式結構的實現(xiàn)（1）的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
