文章目錄
- 二叉樹的構建
- 結點型別的定義
- 構建二叉樹之間的關系
- 深度優先遍歷
- 前序遍歷
- 代碼實作
- 圖解遞回（由于圖片大小問題，建議用手機客戶端查看，以下圖解也是）
- 中序遍歷
- 代碼實作
- 圖解遞回
- 后序遍歷
- 代碼實作
- 圖解遞回
- 廣度優先遍歷
- 層序遍歷
- 代碼實作
二叉樹的構建
為了實作二叉樹的遍歷，我們要先構建一個二叉樹，這里就先簡單構建一個，
結點型別的定義
既然是鏈式二叉樹，那必須得有自己的結點型別，以下是鏈式二叉樹結點型別的定義
typedef char BTDataType;
typedef struct BinaryNode
{
BTDataType x;
struct BinaryNode* left;
struct BinaryNode* right;
}BT;
構建二叉樹之間的關系
BT* BuyNode(BTDataType x)
{
BT* new = (BT*)malloc(sizeof(BT));
if (new == NULL)
{
printf("malloc failed\n");
exit(-1);
}
new->x = x;
new->left = NULL;
new->right = NULL;
return new;
}
void BinaryCreat()
{
BT* n1 = BuyNode('A');
BT* n2 = BuyNode('B');
BT* n3 = BuyNode('C');
BT* n4 = BuyNode('D');
BT* n5 = BuyNode('E');
BT* n6 = BuyNode('F');
n1->left = n2;
n1->right = n3;
n2->left = n4;
n3->left = n5;
n3->right = n6;
}
構建完之后的二叉樹是這個樣子的：
深度優先遍歷
二叉樹的深度優先遍歷有以下三種
前序遍歷
前序遍歷，又叫先根遍歷，
遍歷順序：根 -> 左子樹 -> 右子樹
代碼實作
void BinaryPrev(BT* n1)
{
if (n1==NULL)
{
printf("NULL ");
return ;
}
printf("%c ", n1->x);
BinaryPrev(n1->left);
BinaryPrev(n1->right);
}
很多小伙伴可能會覺得：哇！這么少的代碼就可以解決了嗎？對，就是這么幾行，這也就是遞回遍歷的強大之處，但是這之間的遞回程序是很復雜的，
圖解遞回（由于圖片大小問題，建議用手機客戶端查看，以下圖解也是）
中序遍歷
中序遍歷，又叫中根遍歷，
遍歷順序：左子樹 -> 根 -> 右子樹
代碼實作
void MiddleOrder(BT* n1)
{
if (n1 == NULL)
{
printf("NULL ");
return;
}
MiddleOrder(n1->left);
printf("%c ", n1->x);
MiddleOrder(n1->right);
}
這個也是同樣的簡單，只要按著它的順序寫就行了，但其中的程序很復雜，
圖解遞回
后序遍歷
后序遍歷，又叫后根遍歷，
遍歷順序：左子樹 -> 右子樹 -> 根
代碼實作
void AfterOrder(BT* n1)
{
if (n1 == NULL)
{
printf("NULL ");
return;
}
AfterOrder(n1->left);
AfterOrder(n1->right);
printf("%c ", n1->x);
}
這個同樣也是只要按著順序寫就可以了，遞回起來很復雜，
圖解遞回
廣度優先遍歷
層序遍歷
層序遍歷，自上而下，從左往右逐層訪問樹的結點的程序就是層序遍歷，
思路（借助一個佇列）：
1.先把根入佇列，然后開始從隊頭出資料，
2.出隊頭的資料，把它的左孩子和右孩子依次從隊尾入佇列（NULL不入佇列），
3.重復進行步驟2，直到佇列為空為止，
代碼實作
在實作程序中要用到佇列，具體佇列的實作這兒就不說了，博主之前的博客中有相關的文章，
void BinaryLevelOrder(BT* n1)
{
Queue q;
QueueInit(&q);
if (n1!=NULL)
{
QueuePush(&q, n1);
}
while (!QueueEmpty(&q))
{
BT* front = QueueTop(&q);
QueuePop(&q);
printf("%c ", front->x);
// 不把NULL列印出來
//if (front->left!=NULL)
//{
// QueuePush(&q, front->left);
//}
//if (front->right != NULL)
//{
// QueuePush(&q, front->right);
//}
if (front->left != NULL)
{
QueuePush(&q, front->left);
}
else
{
printf("NULL ");
}
if (front->right != NULL)
{
QueuePush(&q, front->right);
}
else
{
printf("NULL ");
}
}
QueueDestory(&q);
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/297833.html
標籤：其他
上一篇：??一看就懂！保姆級實體詳解 STL list 容器【萬字整理】??
下一篇：【資料結構】二叉樹之堆的實作