快捷導(dǎo)航

C語(yǔ)言之二叉樹(shù)的遍歷

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

這篇文章主要介紹了C語(yǔ)言中二叉樹(shù)的遍歷：前序、中序、后序，認(rèn)識(shí)二叉樹(shù)結(jié)構(gòu)最簡(jiǎn)單的方式就是遍歷二叉樹(shù)，感興趣的小伙伴可以參考閱讀本文

0.寫(xiě)在前面

認(rèn)識(shí)二叉樹(shù)結(jié)構(gòu)最簡(jiǎn)單的方式就是遍歷二叉樹(shù)。所謂遍歷二叉樹(shù)就是按照某種特定的規(guī)則，對(duì)二叉樹(shù)的每一個(gè)節(jié)點(diǎn)進(jìn)行訪(fǎng)問(wèn)，且每個(gè)節(jié)點(diǎn)只訪(fǎng)問(wèn)一次。

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

1.前序遍歷：先訪(fǎng)問(wèn)根節(jié)點(diǎn)，再遍歷左右子樹(shù)；

2.中序遍歷：先遍歷左子樹(shù)，再訪(fǎng)問(wèn)根節(jié)點(diǎn)，再遍歷右子樹(shù)；

3.后序遍歷：先遍歷左子樹(shù)，再遍歷右子樹(shù)，再訪(fǎng)問(wèn)根節(jié)點(diǎn)。

簡(jiǎn)單記憶：前（根，左，右）、中（左，根，右）、后（左，右，根）。

在遍歷二叉樹(shù)之前，首先得擁有一棵二叉樹(shù)。因?yàn)槟壳斑€沒(méi)有學(xué)習(xí)如何構(gòu)建二叉樹(shù)，所以此處我們用最原始的辦法——申請(qǐng)N個(gè)節(jié)點(diǎn)，將它們手動(dòng)拼接為二叉樹(shù)。

typedef int BTDataType;
 
//二叉樹(shù)節(jié)點(diǎn)的結(jié)構(gòu)
typedef struct BTNode
{
	BTDataType data;
	struct BTNode* left;
	struct BTNode* right;
}BTNode;
 
//定義一個(gè)申請(qǐng)新節(jié)點(diǎn)的函數(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()
{
	//手動(dòng)申請(qǐng)節(jié)點(diǎn)加連接
	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.前序遍歷

前序遍歷：先訪(fǎng)問(wèn)根節(jié)點(diǎn)，再訪(fǎng)問(wèn)左子樹(shù)，再訪(fǎng)問(wèn)右子樹(shù)；

void PrevOrder (BTNode* root)

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

步驟詳解

1.先訪(fǎng)問(wèn)根節(jié)點(diǎn) （data = 1），再訪(fǎng)問(wèn)左子樹(shù)；

2.再訪(fǎng)問(wèn)左子樹(shù)的根節(jié)點(diǎn)（data = 2），再訪(fǎng)問(wèn)左子樹(shù)的左子樹(shù)；

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

4.因?yàn)?n2 節(jié)點(diǎn)的右子樹(shù)為 NULL，所以繼續(xù)返回上一層；訪(fǎng)問(wèn)上一層的右子樹(shù)；

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

至此每個(gè)節(jié)點(diǎn)都訪(fǎng)問(wèn)完畢，總體的訪(fǎng)問(wèn)順序是這樣的：

按照訪(fǎng)問(wèn)順序打印的結(jié)果應(yīng)該是（空節(jié)點(diǎn)用 NULL 表示）：

代碼實(shí)現(xiàn)

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

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

運(yùn)行程序，看結(jié)果是否與之前推理的結(jié)果一致：

int main()
{
	//手動(dòng)申請(qǐng)節(jié)點(diǎn)加連接
	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.中序遍歷

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

void InOrder(BTNode* root)

步驟詳解

代碼實(shí)現(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。

代碼實(shí)現(xiàn)

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