?🔥個人主頁：@草莓熊Lotso
🎬作者簡介：C++研發方向學習者
📖個人專欄：?《C語言》?《數據結構與算法》《C語言刷題集》《Leetcode刷題指南》
??人生格言：生活是默默的堅持，毅力是永久的享受。
前言：在前面我們結束了實現順序結構的二叉樹以及Top-K問題的解決。那么接下來就是實現鏈式結構二叉樹，鏈接結構的二叉樹，沒有完全二叉樹和堆那樣的性質，所以我們后續實現的接口也不會涉及插入刪除等操作，主要是前中后序遍歷以及其它的一些二叉樹常用方式的實現。?
目錄
一.創建鏈式結構二叉樹
二.前中后序遍歷
前序遍歷：
?代碼實現：
?函數遞歸棧棧圖：(標的序號表示打印的順序)
前序遍歷結果(忽略NULL)：
?中序遍歷：
?代碼實現：
?函數棧幀遞歸圖：(標的序號表示打印的順序)
?中序遍歷結果(忽略NULL)：
后序遍歷：?
代碼實現：?
函數遞歸棧幀圖：?(標的序號表示打印的順序)
后序遍歷結果(忽略NULL)：
三.代碼展現?
Tree.h：
Tree.c：
test.c：
一.創建鏈式結構二叉樹
--用鏈表來表示?棵二叉樹，即用鏈來指示元素的邏輯關系。 通常的方法是鏈表中每個結點由三個域組成，數據域和左右指針域，左右指針分別用來給出該結點左孩子和右孩子所在的鏈結點的存儲地址 ，其結構如下：(我們數據類型這次用的char)
typedef char BTDataType;
typedef struct BinaryNode
{BTDataType data;struct BinaryNode* left;//左孩子struct BinaryNode* right;//右孩子
}BTNode;我們為了方便后續的使用，先手動創建一顆鏈式二叉樹：
BTNode* buyNode(char x)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));newnode->data = x;newnode->left = newnode->right = NULL;return newnode;
}
void test1()
{BTNode* nodeA = buyNode('A');BTNode* nodeB = buyNode('B');BTNode* nodeC = buyNode('C');BTNode* nodeD = buyNode('D');BTNode* nodeE = buyNode('E');BTNode* nodeF = buyNode('F');nodeA->left = nodeB;nodeA->right = nodeC;nodeB->left = nodeD;nodeC->left = nodeE;nodeC->right = nodeF;
}?創建出來的樹如圖所示：
二.前中后序遍歷
--二叉樹的操作遍歷是必不可少的，我們先來看看這些遍歷的遍歷規則吧
按照規則，二叉樹的遍歷有：前序/中序/后序的遞歸結構遍歷：
- 前序遍歷(先根遍歷)：先遍歷根節點，再遍歷左子樹，最后遍歷右子樹----根左右
- 中序遍歷：先遍歷左子樹，再遍歷根節點，最后遍歷右子樹----左根右
- 后續遍歷：先遍歷左子樹，再遍歷右子樹，最后遍歷根節點----左右根
就拿我們創建的這個樹為例，那么它的前中后遍歷結果和代碼實現是怎樣的呢，我們一起接著往下看
前序遍歷：
- 訪問順序：根節點，左子樹，右子樹
?代碼實現：
//前序遍歷
void PreOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}//根左右printf("%c ", root->data);PreOrder(root->left);PreOrder(root->right);
}
這份代碼是不是看起來特別簡單，這里就是利用了遞歸的思想，為空就打印NULL并返回。大家一定要去仔細體會一下遞歸的過程，最好把函數遞歸的棧幀圖給畫出來理解。大家可以先看一下我畫的兩個圖。?
?這里紅線統一表示遞歸，另一個表示回退
?函數遞歸棧棧圖：(標的序號表示打印的順序)
前序遍歷結果(忽略NULL)：
- A B D C E F
?中序遍歷：
- 訪問順序：左子樹，根節點，右子樹
?代碼實現：
//中序遍歷
void InOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}//左根右InOrder(root->left);printf("%c ", root->data);InOrder(root->right);
}
這里的中序遍歷代碼也都很簡單，注意順序就好了。我們還是和上面的一樣，通過畫圖理清它的遞歸邏輯?
?
?函數棧幀遞歸圖：(標的序號表示打印的順序)
?中序遍歷結果(忽略NULL)：
- D B A E C F
后序遍歷：?
- 訪問順序：左子樹，右子樹，根節點
代碼實現：?
//后續遍歷
void PostOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}//左右根PostOrder(root->left);PostOrder(root->right);printf("%c ", root->data);
}后序遍歷的代碼也很簡單，和前面兩種一樣還是利用遞歸的思想去實現?，我們繼續通過畫函數遞歸棧幀圖來理清它的邏輯
函數遞歸棧幀圖：?(標的序號表示打印的順序)
后序遍歷結果(忽略NULL)：
- D B E F C A
三.代碼展現?
Tree.h：
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>typedef char BTDataType;
typedef struct BinaryNode
{BTDataType data;struct BinaryNode* left;//左孩子struct BinaryNode* right;//右孩子
}BTNode;//前序遍歷
void PreOrder(BTNode* root);//中序遍歷
void InOrder(BTNode* root);//后序遍歷
void PostOrder(BTNode* root);Tree.c：
#include"Tree.h"//前序遍歷
void PreOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}//根左右printf("%c ", root->data);PreOrder(root->left);PreOrder(root->right);
}//中序遍歷
void InOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}//左根右InOrder(root->left);printf("%c ", root->data);InOrder(root->right);
}//后序遍歷
void PostOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}//左右根PostOrder(root->left);PostOrder(root->right);printf("%c ", root->data);
}test.c：
#include"Tree.h"BTNode* buyNode(char x)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));newnode->data = x;newnode->left = newnode->right = NULL;return newnode;
}
void test1()
{BTNode* nodeA = buyNode('A');BTNode* nodeB = buyNode('B');BTNode* nodeC = buyNode('C');BTNode* nodeD = buyNode('D');BTNode* nodeE = buyNode('E');BTNode* nodeF = buyNode('F');nodeA->left = nodeB;nodeA->right = nodeC;nodeB->left = nodeD;nodeC->left = nodeE;nodeC->right = nodeF;//PreOrder(nodeA);//InOrder(nodeA);PostOrder(nodeA);
}int main()
{test1();return 0;
}?往期回顧：
【數據結構初階】--棧和隊列(二)
【數據結構初階】--樹和二叉樹先導篇
【數據結構初階】--二叉樹(二)
【數據結構初階】--二叉樹(三)
結語：本篇博客中我們實現了二叉樹的前中后序遍歷以及畫出了它們的函數遞歸棧幀圖。大家還是需要多去熟悉一樣，最好是理清它們的遞歸過程，后面我們會經常需要畫函數遞歸棧幀圖的。在下篇博客中我會和大家一起繼續實現鏈式結構二叉樹的其它方法接口，如果文章對你有幫助的話，歡迎評論，點贊，收藏加關注，感謝大家的支持。
