欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C語言之二叉樹的遍歷

 更新時間:2023年03月31日 16:44:24   作者:花想云  
這篇文章主要介紹了C語言中二叉樹的遍歷:前序、中序、后序,認(rèn)識二叉樹結(jié)構(gòu)最簡單的方式就是遍歷二叉樹,感興趣的小伙伴可以參考閱讀本文

0.寫在前面

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

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

1.前序遍歷:先訪問根節(jié)點,再遍歷左右子樹;

2.中序遍歷:先遍歷左子樹,再訪問根節(jié)點,再遍歷右子樹;

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

簡單記憶:前(根,左,右)、中(左,根,右)、后(左,右,根)。

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

typedef int BTDataType;
 
//二叉樹節(jié)點的結(jié)構(gòu)
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ī)則,接下來展示一下詳細(xì)步驟。

步驟詳解

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é)果應(yīng)該是(空節(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);
}

運行程序,看結(jié)果是否與之前推理的結(jié)果一致:

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);//后序在后
}

 到此這篇關(guān)于C語言之二叉樹的遍歷的文章就介紹到這了,更多相關(guān)二叉樹的遍歷內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • c++ 判斷是64位還是32位系統(tǒng)的實例

    c++ 判斷是64位還是32位系統(tǒng)的實例

    這篇文章主要介紹了c++ 判斷是64位還是32位系統(tǒng)的實例,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2020-12-12
  • c語言中聯(lián)合體和枚舉用法詳解

    c語言中聯(lián)合體和枚舉用法詳解

    結(jié)構(gòu)體、聯(lián)合體是C語言中的構(gòu)造類型,結(jié)構(gòu)體我們平時應(yīng)該都用得很多,下面這篇文章主要給大家介紹了關(guān)于c語言中聯(lián)合體和枚舉用法的相關(guān)資料,文中通過代碼介紹的非常詳細(xì),需要的朋友可以參考下
    2023-12-12
  • C++實現(xiàn)簡單FTP客戶端軟件開發(fā)

    C++實現(xiàn)簡單FTP客戶端軟件開發(fā)

    這篇文章主要為大家詳細(xì)介紹了C++實現(xiàn)簡單FTP客戶端軟件開發(fā),文中示例代碼介紹的非常詳細(xì),具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2022-08-08
  • C++ 遞歸遍歷文件并計算MD5的實例代碼

    C++ 遞歸遍歷文件并計算MD5的實例代碼

    在本篇文章里小編給大家整理的是一篇關(guān)于C++ 遞歸遍歷文件并計算MD5的實例代碼,有興趣的朋友們可以學(xué)習(xí)參考下。
    2021-07-07
  • C++回溯算法中子集問題分析探討

    C++回溯算法中子集問題分析探討

    回溯法是一種選優(yōu)搜索法,按選優(yōu)條件向前搜索,以達到目標(biāo)。但當(dāng)探索到某一步時,發(fā)現(xiàn)原先選擇并不優(yōu)或達不到目標(biāo),就退回一步重新選擇,這種走不通就退回再走的技術(shù)為回溯法,而滿足回溯條件的某個狀態(tài)的點稱為回溯點
    2023-03-03
  • 利用C語言實現(xiàn)2048小游戲的方法

    利用C語言實現(xiàn)2048小游戲的方法

    2048是比較流行的一款數(shù)字游戲,相信對大家來說都不陌生,這篇文章給大家分享了利用C語言實現(xiàn)2048小游戲的方法,對大家學(xué)習(xí)理解C語言具有一定的參考借鑒價值,有需要的朋友們下面來一起看看吧。
    2016-10-10
  • C++?測試框架GoogleTest入門介紹

    C++?測試框架GoogleTest入門介紹

    這篇文章主要為大家介紹了C++測試框架GoogleTest入門基礎(chǔ),有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪
    2023-04-04
  • 一文教你快速了解C語言中的作用域和常量

    一文教你快速了解C語言中的作用域和常量

    作用域(scope)是程序設(shè)計概念,通常來說一段程序代碼中所用到的名字并不總是有效/可用,下面這篇文章主要給大家介紹了關(guān)于如何快速了解C語言中的作用域和常量的相關(guān)資料,需要的朋友可以參考下
    2023-06-06
  • 數(shù)據(jù)結(jié)構(gòu)之伸展樹詳解

    數(shù)據(jù)結(jié)構(gòu)之伸展樹詳解

    這篇文章主要介紹了數(shù)據(jù)結(jié)構(gòu)之伸展樹詳解,本文對伸展樹(Splay Tree)的單旋轉(zhuǎn)操作、一字型旋轉(zhuǎn)、之字形旋轉(zhuǎn)區(qū)間操作等理論知識做了講解,并給出實現(xiàn)代碼,需要的朋友可以參考下
    2014-08-08
  • 一起來看看C語言的預(yù)處理注意點

    一起來看看C語言的預(yù)處理注意點

    這篇文章主要為大家詳細(xì)介紹了C語言的預(yù)處理,文中示例代碼介紹的非常詳細(xì),具有一定的參考價值,感興趣的小伙伴們可以參考一下,希望能夠給你帶來幫助
    2022-03-03

最新評論