目錄

• 一、二叉樹的創(chuàng)建(偽)
• 二、二叉樹的遍歷
• • 2.1 前序遍歷
  • 2.2 中序遍歷
  • 2.3 后序遍歷
• 三、二叉樹節(jié)點個數(shù)及高度
• • 3.1 二叉樹節(jié)點個數(shù)
  • 3.2 二叉樹葉子節(jié)點個數(shù)
  • 3.3二叉樹第k層節(jié)點個數(shù)
  • 3.4 二叉樹查找值為x的節(jié)點
• 四、二叉樹的創(chuàng)建(真)

一、二叉樹的創(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ī)則，二叉樹的遍歷有：前序/中序/后序的遞歸結構遍歷：

1. 前序遍歷(Preorder Traversal 亦稱先序遍歷)——訪問根結點的操作發(fā)生在遍歷其左右子樹之前。
2. 中序遍歷(Inorder Traversal)——訪問根結點的操作發(fā)生在遍歷其左右子樹之中（間）。
3. 后序遍歷(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

---

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í)行結果如下：

另外還有一些較為復雜的函數(shù)將在下一篇文章中介紹。