C語言之二叉樹的遍歷

更新時間：2023年03月31日 16:44:24 作者：花想云

這篇文章主要介紹了C語言中二叉樹的遍歷：前序、中序、后序，認識二叉樹結構最簡單的方式就是遍歷二叉樹，感興趣的小伙伴可以參考閱讀本文

0.寫在前面

認識二叉樹結構最簡單的方式就是遍歷二叉樹。所謂遍歷二叉樹就是按照某種特定的規(guī)則，對二叉樹的每一個節(jié)點進行訪問，且每個節(jié)點只訪問一次。

二叉樹遍歷的規(guī)則一般有四種：前序遍歷、中序遍歷、后序遍歷和層序遍歷。其中，前三種較為簡單且實現(xiàn)方式大同小異。

1.前序遍歷：先訪問根節(jié)點，再遍歷左右子樹；

2.中序遍歷：先遍歷左子樹，再訪問根節(jié)點，再遍歷右子樹；

3.后序遍歷：先遍歷左子樹，再遍歷右子樹，再訪問根節(jié)點。

簡單記憶：前（根，左，右）、中（左，根，右）、后（左，右，根）。

在遍歷二叉樹之前，首先得擁有一棵二叉樹。因為目前還沒有學習如何構建二叉樹，所以此處我們用最原始的辦法——申請N個節(jié)點，將它們手動拼接為二叉樹。

typedef int BTDataType;
 
//二叉樹節(jié)點的結構
typedef struct BTNode
{
	BTDataType data;
	struct BTNode* left;
	struct BTNode* right;
}BTNode;
 
//定義一個申請新節(jié)點的函數(shù)
BTNode* BuyBTNode(BTDataType data)
{
	BTNode* newNode = (BTNode*)malloc(sizeof(BTNode));
	if (newNode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
 
	newNode->data = data;
	newNode->left = NULL;
	newNode->right = NULL;
 
	return newNode;
 }
 
int main()
{
	//手動申請節(jié)點加連接
	BTNode* n1 = BuyBTNode(1);
	BTNode* n2 = BuyBTNode(2);
	BTNode* n3 = BuyBTNode(3);
	BTNode* n4 = BuyBTNode(4);
	BTNode* n5 = BuyBTNode(5);
	BTNode* n6 = BuyBTNode(6);
 
	n1->left = n2;
	n1->right = n4;
	n2->left = n3;
	n4->left = n5;
	n4->right = n6;
	return 0;
}

1.前序遍歷

前序遍歷：先訪問根節(jié)點，再訪問左子樹，再訪問右子樹；

void PrevOrder (BTNode* root)

為了更好的理解前序遍歷的規(guī)則，接下來展示一下詳細步驟。

步驟詳解

1.先訪問根節(jié)點（data = 1），再訪問左子樹；

2.再訪問左子樹的根節(jié)點（data = 2），再訪問左子樹的左子樹；

3.依舊先訪問根節(jié)點（data = 3），此時 n3 節(jié)點的左右子樹都為 NULL ，則不再往下遞歸，回到上一層；接著訪問上一層的右子樹；

4.因為 n2 節(jié)點的右子樹為 NULL，所以繼續(xù)返回上一層；訪問上一層的右子樹；

5.訪問右子樹的根節(jié)點（data = 4），再訪問右子樹的左子樹；先左子樹的根節(jié)點（data = 5），n5 節(jié)點的左右子樹都為 NULL，返回上一層訪問右子樹（data = 6），同樣 n6 節(jié)點的左右子樹都為 NULL，返回上一層。

至此每個節(jié)點都訪問完畢，總體的訪問順序是這樣的：

按照訪問順序打印的結果應該是（空節(jié)點用 NULL 表示）：

代碼實現(xiàn)

按照前序遍歷的邏輯，前序遍歷的實現(xiàn)肯定是離不開遞歸。

void PrevOrder(BTNode* root)
{
	if (root == NULL)
	{ 
		printf("NULL ");//空節(jié)點用 NULL 表示
		return; 
	}
 
	printf("%d ", root->data);//前序在前
	PrevOrder(root->left);
	PrevOrder(root->right);
}

運行程序，看結果是否與之前推理的結果一致：

int main()
{
	//手動申請節(jié)點加連接
	BTNode* n1 = BuyBTNode(1);
	BTNode* n2 = BuyBTNode(2);
	BTNode* n3 = BuyBTNode(3);
	BTNode* n4 = BuyBTNode(4);
	BTNode* n5 = BuyBTNode(5);
	BTNode* n6 = BuyBTNode(6);
 
	n1->left = n2;
	n1->right = n4;
	n2->left = n3;
	n4->left = n5;
	n4->right = n6;
 
	PrevOrder(n1);
	return 0;
}

2.中序遍歷

前中后序三種遍歷大同小異，實現(xiàn)代碼也幾乎相同。

void InOrder(BTNode* root)

步驟詳解

代碼實現(xiàn)

void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
 
	PrevOrder(root->left);
	printf("%d ", root->data);//中序在中
	PrevOrder(root->right);
}

3.后序遍歷

步驟詳解

參考1、2。

代碼實現(xiàn)

void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
 
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->data);//后序在后
}