0. 前言
前文【二叉樹的概念和原理】主要介紹了樹的相關概念和原理，本文主要內容為二叉樹的創建及遍歷的代碼實作，其中包括遞回遍歷和堆疊遍歷，
1. 二叉樹的實作思路
1.0. 順序存盤——陣列實作
前面介紹了滿二叉樹和完全二叉樹，我們對其進行了編號——從 0 到 n 的不中斷順序編號，而恰好，陣列也有一個這樣的編號 —— 陣列下標，只要我們把二者聯合起來，陣列就能存盤二叉樹了，
那么非滿、非完全二叉樹怎么使用陣列存盤呢？
我們可以在二叉樹中補上一些虛構的結點，構造出來一個滿/完全二叉樹來，存盤到陣列中時，虛構的結點對應的陣列元素不存盤資料（# 代表虛構的不存在），如下圖：
這樣存盤的缺點是，陣列中可能會有大量空間未用到，造成浪費，
1.1. 鏈式存盤——鏈表實作
我們畫樹的圖時，采用的都是結點加箭頭的方式，結點表示資料元素，箭頭表示結點之間的關系，清晰明了，如果你對鏈表熟悉，那么肯定能覺察到這是典型的鏈式結構，鏈式結構完美解決了順序結構中可能會浪費空間的缺點，而且也不會有陣列空間限制，
下面來分析一下結點的結構，
樹的結點包括一個資料元素和若干指向其子樹分支，二叉樹的結點相對簡單，包括：
- 資料元素
- 左子樹分支（結點的左孩子）
- 右子樹分支（結點的右孩子）
怎么來實作呢？單鏈表的結點是使用一個指向其后繼結點的指標來表示其關系的，同樣地，我們也可以使用指標來表示結點和其左孩子、右孩子的關系，
分析到這，二叉樹的結點就清晰了：
- 一個存盤資料的變數——
data - 一個指向其左孩子結點的指標——
left_child - 一個指向其右孩子結點的指標——
right_child
用 C 語言的結構體實作二叉樹的結點（為了方便起見，我們的資料全為字符型別）：
/*二叉樹的結點的結構體*/
typedef struct Node {
char data; //資料域
struct Node *left_child; //左孩子指標
struct Node *right_child; //右孩子指標
} TreeNode;
2. 二叉樹的創造
二叉樹的定義是遞回的定義，所以如果你想要創造一個二叉樹，也可以借助遞回去創造，如何遞回創造呢？在現實中，一棵樹先長根、再長枝干、最后長葉子，我們用代碼創造樹時，也遵守這個原則，即先創造根結點，然后左子樹，最后右子樹，整個程序和先序遍歷相似，
我以前寫過的文章中有二叉樹創建程序的動態圖，這里不再贅述，
這里以創造下圖中的樹為例：
說明：當我們看到如左圖的二叉樹時，要立即能腦補出對應的右圖，#結點是什么？
前面我們已經畫出了類似的圖，當時是 NULL 結點，它的作用是標識某個結點沒有孩子，它是我們虛構出來的，在實際使用 C 語言創造二叉樹時，需要使用 #或者什么其他的符號來代替 NULL.
上圖的先序遍歷順序為：ABDEGCF，如果加上 # 結點，則為：ABD##EG###C#F##. 我們按照此順序來創造二叉樹，
代碼如下：
/**
* 創造一個二叉樹
* root: 指向根結點的指標的指標
*/
void create_binary_tree(TreeNode **root)
{
char elem;
scanf("%c", &elem);
if (elem == '#') {
*root = NULL;
} else {
*root = create_tree_node(elem); //創造一個二叉結點
create_binary_tree(&((*root)->left_child));
create_binary_tree(&((*root)->right_child));
}
}
請注意，函式 create_binary_tree 接受的是一個指向根結點的指標的指標，至于為什么要使用指標的指標，理由在介紹單鏈表的初始化時已經解釋了，
3. 二叉樹的遍歷
在文章【二叉樹的概念和原理】中已經介紹了遍歷的原理了，下面使用 C 語言實作它，
3.0. 遍歷實質
二叉樹的定義是遞回的定義，即在二叉樹的定義中又用到了二叉樹的定義，所以無論是在創造二叉樹，還是在遍歷二叉樹，我們要做的只有三件事：訪問根結點、找左子樹、找右子樹，所謂先序、中序、后序遍歷，無非是這三件事的順序罷了，
3.1. 遞回實作
我們如果使用遞回代碼，很容易就能實作遍歷，而且代碼非常簡潔，
【先序遍歷】
/**
* 先序遍歷
* root: 指向根結點的指標
*/
void preorder_traversal(TreeNode *root)
{
if (root == NULL) { //若二叉樹為空，做空操作
return;
}
printf("%c ", root->data); //訪問根結點
preorder_traversal(root->left_child); //遞回遍歷左子樹
preorder_traversal(root->right_child); //遞回遍歷右子樹
}
【中序遍歷】
/**
* 中序遍歷
* root: 指向根結點的指標
*/
void inorder_traversal(TreeNode *root)
{
if (root == NULL) { //若二叉樹為空，做空操作
return;
}
inorder_traversal(root->left_child); //遞回遍歷左子樹
printf("%c ", root->data); //訪問根結點
inorder_traversal(root->right_child); //遞回遍歷右子樹
}
【后序遍歷】
/**
* 后序遍歷
* root: 指向根結點的指標
*/
void postorder_traversal(TreeNode *root)
{
if (root == NULL) { //若二叉樹為空，做空操作
return;
}
postorder_traversal(root->left_child); //遞回遍歷左子樹
postorder_traversal(root->right_child); //遞回遍歷右子樹
printf("%c ", root->data); //訪問根結點
}
事實上，大部分使用遞回做的事，使用堆疊也可以做到，下面介紹遍歷的堆疊實作，
3.2. 堆疊實作
我們利用了堆疊的后進先出的特性，
堆疊實作的代碼較復雜，受篇幅限制，這里只介紹先序遍歷和后序遍歷，詳細代碼請移步至代碼倉庫查看，
【先序遍歷】
我們的樹的結點是要全部都入堆疊的（暫不管順序如何），那么入堆疊的條件是什么？就是該結點可以被看作某棵樹（子樹）的根結點的時候，即，curr 指標指向的結點一定為某顆樹（子樹）的根結點，
在【二叉樹的概念和原理】中，我們已經看到了，遍歷完某個子樹時，一定要回到其雙親結點，這種回溯如何實作？可以利用堆疊的先進后出、后進先出的特點，這個特點能在堆疊中完美保存結點在樹中父子關系，堆疊頂元素即為當前子樹的雙親結點，
/**
* 使用堆疊實作的先序遍歷
*/
void preorder_traversal_by_stack(TreeNode *root)
{
//創造并初始化堆疊
Stack stack;
init_stack(&stack);
TreeNode *curr = root; //輔助指標curr
while (curr != NULL || !stack_is_empty(&stack)) {
while (curr != NULL) {
printf("%c", curr->data); //列印根結點
push(&stack, curr); //根結點入堆疊
curr = curr->left_child; //進入左子樹
}
if (!stack_is_empty(&stack)) {
pop(&stack, &curr); //出堆疊，回到上一個根結點
curr = curr->right_child; //進入右子樹
}
}
}
【后序遍歷】
后序遍歷相較于前序和中序較為麻煩，不像前序和中序遍歷那樣，因為前序和種序的根結點在右子樹之前，所以我們可以在出堆疊的時候同時進行列印根結點和進入右子樹，
后序遍歷的根結點在右子樹之后，這就要求我們再遍歷完左子樹后，先回傳到根結點，然后進入右子樹，遍歷完右子樹之后，再回到根結點，才能列印它，
關鍵之處還在于左子樹、右子樹、根結點的順序，
所以當 curr 指標遍歷完左子樹后，我們不能直接將根結點出堆疊，而是先從堆疊頂讀取到根結點，然后 curr 指標回傳到根結點，然后 curr 指標進入右子樹進行遍歷，當右子樹遍歷完成后，將根結點出堆疊，才能列印根結點，
這樣一來，后序遍歷就有兩次回到根結點的動作，且這兩次的后續動作不一樣，第一次通過讀取堆疊頂回到根結點，然后進入右子樹；第二次通過出堆疊回到根結點，然后列印根結點，
這樣看似解決了后序遍歷的順序問題，但其實又得到了一個新的問題，即，我們如何知道右子樹被遍歷完了？
我們有兩次回到根結點的動作，對于寫代碼的人來說，我們知道兩次回到根結點之后該干什么，知道右子樹是否被遍歷完了，但是對于 curr 指標來說，它不知道，兩次回到根結點，它都不知道右子樹是否被遍歷完成了，
此時，對于curr 指標來說，就像有兩條路擺在它面前讓它選擇其中一條，它難以抉擇，如果當其中一條有過它的腳印，那么它就很容易選擇那條沒走過的路了，
所以我們現在還需要一個“腳印”指標——prev，prev指標用來記錄 curr訪問過的結點，
當 curr 指標第二次回到根結點的時候，一看，哦！我的腳印留在那呢！（prev 指標指在右子樹那里）curr 指標就直接放心列印根結點了，
/**
* 使用堆疊實作的后序遍歷
*/
void postorder_traversal_by_stack(TreeNode *root)
{
Stack stack;
init_stack(&stack);
TreeNode *curr = root; //輔助指標curr，記錄當前訪問結點
TreeNode *prev = NULL; //腳印指標prev，記錄上一個訪問過的結點
while (curr != NULL || !stack_is_empty(&stack)) {
if (curr != NULL) {
push(&stack, curr); //根結點入堆疊
curr = curr->left_child; //進入左子樹
} else {
get_top(&stack, &curr); //讀堆疊頂元素，不是出堆疊
//右子樹不為空，且右子樹沒被遍歷
if (curr->right_child != NULL && curr->right_child != prev) {
curr = curr->right_child; //進入右子樹
push(&stack, curr); //根結點入堆疊
curr = curr->left_child; //進入左子樹
} else { //右子樹已被遍歷或者右子樹為空，可以列印根結點了
pop(&stack, &curr); //根結點出堆疊
printf("%c", curr->data); //列印根結點
prev = curr; //記錄
curr = NULL; //置空，進入下一輪回圈
}
}
}
}
以上代碼中的堆疊的相關函式這里不再給出，詳細代碼請移步至代碼倉庫（文末獲取），
4. 總結
遞回的代碼雖然簡潔，但是對新手來說卻有點難以理解，這是因為接觸的太少，堆疊的代碼相對來說容易理解一些，但代碼比較復雜，特別是后序遍歷的代碼，
不過當你真正理解了二叉樹的定義、概念、原理之后，代碼相關的問題就不再是問題了，最終只落在六個字上——無他，惟手熟爾，
以上就是二叉樹的創建和遍歷的實作，
完整代碼請移步至 GitHub | Gitee 獲取，
如有錯誤，還請指正，
如果覺得寫的不錯，可以點個贊和關注，后續會有更多資料結構和演算法相關文章，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/277987.html
標籤：其他