???? 前言

hello hello~ ，這里是大耳朵土土垚~???? ，歡迎大家點贊????關注????收藏??????

??個人主頁：大耳朵土土垚的博客
?? 所屬專欄：數(shù)據(jù)結構學習筆記 、C語言系列函數(shù)實現(xiàn)
??對于數(shù)據(jù)結構順序表、鏈表、堆有疑問的都可以在上面數(shù)據(jù)結構的專欄進行學習哦~ 有問題可以寫在評論區(qū)或者私信我哦~

復習鞏固：????

在學習二叉樹基本操作前，再回顧下二叉樹的概念，二叉樹是：

1. 空樹
2. 非空：根節(jié)點，根節(jié)點的左子樹、根節(jié)點的右子樹組成的。
   
   從概念中可以看出，二叉樹定義是遞歸式的，因此后序基本操作中基本都是按照該概念實現(xiàn)的。

一、手動創(chuàng)建一個簡單二叉樹????

在學習二叉樹的基本操作前，需先要創(chuàng)建一棵二叉樹，然后才能學習其相關的基本操作。由于現(xiàn)在大家對二叉樹結構掌握還不夠深入，為了降低大家學習成本，此處手動快速創(chuàng)建一棵簡單的二叉樹，快速進入二叉樹操作學習，等二叉樹結構了解的差不多時，我們反過頭再來研究二叉樹真正的創(chuàng)建方式。

手動創(chuàng)建簡單二叉樹代碼如下：

typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;
BTNode* BuyNode(BTDataType x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	newnode->right = NULL;
	newnode->data = x;
	newnode->left = NULL;
	return newnode;
}
BTNode* CreatBinaryTree()
{
	BTNode* node1 = BuyNode(1);
	BTNode* node2 = BuyNode(2);
	BTNode* node3 = BuyNode(3);
	BTNode* node4 = BuyNode(4);
	BTNode* node5 = BuyNode(5);
	BTNode* node6 = BuyNode(6);

	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;
	return node1;
}

創(chuàng)建的二叉樹邏輯結構如下圖：

????注意：上述代碼并不是創(chuàng)建二叉樹的方式，真正創(chuàng)建二叉樹方式后序詳解重點講解。

二、二叉樹的三種遍歷??

學習二叉樹結構，最簡單的方式就是遍歷。
所謂二叉樹遍歷(Traversal)是按照某種特定的規(guī)則，依次對二叉樹中的節(jié)點進行相應的操作，并且每個節(jié)點只操作一次。訪問結點所做的操作依賴于具體的應用問題。
遍歷是二叉樹上最重要的運算之一，也是二叉樹上進行其它運算的基礎。

1.前序

前序遍歷(Preorder Traversal 亦稱先序遍歷)——訪問根結點的操作發(fā)生在遍歷其左右子樹之前。
也就是先訪問根結點在訪問左子樹右子樹，左子樹也是先訪問根結點再訪問左子樹右子樹…直到結束出現(xiàn)NULL；

前序遍歷遞歸圖解：

????這里要注意訪問葉子結點時要將它左右也就是NULL訪問，這樣才不會出差錯。不能說它沒有左右子樹，而是它的孩子結點為NULL。

代碼如下：

// 二叉樹前序遍歷
void PreOrder(BTNode* root)
{
	if (root)//如果root為NULL就不需要進入if語句直接退出函數(shù)
	{
		printf("%d\n", root->data);
		PreOrder(root->left);
		PreOrder(root->right);
	}
}

遞歸圖解如下：

結果如下：

2.中序

中序遍歷(Inorder Traversal)——訪問根結點的操作發(fā)生在遍歷其左右子樹之中（間）。
也就是先訪問左子樹再訪問根結點最后訪問右子樹，先訪問的左子樹也是先訪問其左子樹再訪問根結點最后訪問右子樹…直到遍歷完全部結點。

代碼如下：

// 二叉樹中序遍歷
void InOrder(BTNode* root)
{
	if (root)
	{
		InOrder(root->left);
		printf("%d\n", root->data);
		InOrder(root->right);
	}
}

結果如下：

3.后序

后序遍歷(Postorder Traversal)——訪問根結點的操作發(fā)生在遍歷其左右子樹之后。
也就是先訪問左子樹再訪問右子樹最后訪問根結點，再訪問左子樹時也是按照左子樹——右子樹——根結點的順序訪問…直到遍歷整個二叉樹。

代碼如下：

// 二叉樹后序遍歷
void PostOrder(BTNode* root)
{
	if (root)
	{
		PostOrder(root->left);
		PostOrder(root->right);
		printf("%d\n", root->data);

	}
}

結果如下：

三、小練習????

解答：

四、結語????

??由于被訪問的結點必是某子樹的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解釋為根、根的左子樹和根的右子樹。NLR、LNR和LRN分別又稱為先根遍歷、中根遍歷和后根遍歷。

以上就是二叉樹前中后序的遍歷啦~學習它對我們后續(xù)學習二叉樹的操作有很大作用同時也幫我們復習和了解遞歸的使用，可謂一舉兩得，大家都get到了嗎， 完結撒花 ~??????????

我的博客即將同步至騰訊云開發(fā)者社區(qū)，邀請大家一同入駐：https://cloud.tencent.com/developer/support-plan?invite_code=2rx6jz7eu90kg文章來源地址http://www.zghlxwxcb.cn/news/detail-840336.html

到了這里，關于數(shù)據(jù)結構——二叉樹的遍歷【前序、中序、后序】的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！