亚洲乱码中文字幕综合,中国熟女仑乱hd,亚洲精品乱拍国产一区二区三区,一本大道卡一卡二卡三乱码全集资源,又粗又黄又硬又爽的免费视频

C語(yǔ)言?超詳細(xì)總結(jié)講解二叉樹(shù)的概念與使用

 更新時(shí)間:2022年04月08日 18:53:56   作者:拼命阿紫  
二叉樹(shù)可以簡(jiǎn)單理解為對(duì)于一個(gè)節(jié)點(diǎn)來(lái)說(shuō),最多擁有一個(gè)上級(jí)節(jié)點(diǎn),同時(shí)最多具備左右兩個(gè)下級(jí)節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)。本文將詳細(xì)介紹一下C++中二叉樹(shù)的概念和結(jié)構(gòu),需要的可以參考一下

1.二叉樹(shù)的概念及結(jié)構(gòu) 

①概念:一棵二叉樹(shù)是結(jié)點(diǎn)的一個(gè)有限集合,該集合或者為空,或者是由一個(gè)根節(jié)點(diǎn)加上兩棵別稱(chēng)為左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。

②二叉樹(shù)的特點(diǎn):

  • 每個(gè)結(jié)點(diǎn)最多有兩棵子樹(shù),即二叉樹(shù)不存在度大于2的結(jié)點(diǎn)。(度最多為2)
  • 二叉樹(shù)的子樹(shù)有左右之分,其子樹(shù)的次序不能顛倒。

③現(xiàn)實(shí)中的二叉樹(shù):

當(dāng)一名普通的人看到這樣一顆樹(shù),可能會(huì)想:好標(biāo)準(zhǔn)的一棵樹(shù)

當(dāng)一個(gè)程序猿看到這樣一棵樹(shù),可能會(huì)想:好像數(shù)據(jù)結(jié)構(gòu)中的二叉樹(shù),并且還是顆滿(mǎn)二叉樹(shù)

④數(shù)據(jù)結(jié)構(gòu)中的二叉樹(shù):

注:二叉樹(shù)最多有兩個(gè)度 

⑤特殊的二叉樹(shù): 

  • 滿(mǎn)二叉樹(shù):一個(gè)二叉樹(shù),如果每一個(gè)層的結(jié)點(diǎn)數(shù)都達(dá)到最大值,則這個(gè)二叉樹(shù)就是滿(mǎn)二叉 樹(shù)。也就是說(shuō),如果一個(gè)二叉樹(shù)的層數(shù)為K,且結(jié)點(diǎn)總數(shù)是(2^k) -1 ,則它就是滿(mǎn)二叉樹(shù)。
  • 完全二叉樹(shù):完全二叉樹(shù)是效率很高的數(shù)據(jù)結(jié)構(gòu),完全二叉樹(shù)是由滿(mǎn)二叉樹(shù)而引出來(lái)的。對(duì) 于深度為K的,有n個(gè)結(jié)點(diǎn)的二叉樹(shù),當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為K的滿(mǎn)二叉樹(shù)中編號(hào) 從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)稱(chēng)之為完全二叉樹(shù)。 要注意的是滿(mǎn)二叉樹(shù)是一種特殊的完全二叉 樹(shù)。 

⑥二叉樹(shù)的存儲(chǔ)結(jié)構(gòu): 二叉樹(shù)一般可以使用兩種結(jié)構(gòu)存儲(chǔ),一種順序結(jié)構(gòu),一種鏈?zhǔn)浇Y(jié)構(gòu)。

⑦二叉樹(shù)的性質(zhì):

  • 若規(guī)定根節(jié)點(diǎn)的層數(shù)為1,則一棵非空二叉樹(shù)的第i層上最多有2^(i-1) 個(gè)結(jié)點(diǎn).
  • 若規(guī)定根節(jié)點(diǎn)的層數(shù)為1,則深度為h的二叉樹(shù)的最大結(jié)點(diǎn)數(shù)是2^h- 1.
  • 對(duì)任何一棵二叉樹(shù), 如果度為0其葉結(jié)點(diǎn)個(gè)數(shù)為 n0, 度為2的分支結(jié)點(diǎn)個(gè)數(shù)為 n2,則有n0=n2 +1
  • 若規(guī)定根節(jié)點(diǎn)的層數(shù)為1,具有n個(gè)結(jié)點(diǎn)的滿(mǎn)二叉樹(shù)的深度,h=log?n+1

⑧練習(xí)題  

2.二叉樹(shù)鏈?zhǔn)浇Y(jié)構(gòu)的實(shí)現(xiàn)

①二叉樹(shù)鏈?zhǔn)浇Y(jié)構(gòu)的遍歷 :

所謂遍歷(Traversal)是指沿著某條搜索路線(xiàn),依次對(duì)樹(shù)中每個(gè)結(jié)點(diǎn)均做一次且僅做一次訪(fǎng)問(wèn)。訪(fǎng) 問(wèn)結(jié)點(diǎn)所做的操作依賴(lài)于具體的應(yīng)用問(wèn) 題。 遍歷是二叉樹(shù)上最重要的運(yùn)算之一,是二叉樹(shù)上進(jìn)行 其它運(yùn)算之基礎(chǔ)。

前序/中序/后序的遞歸結(jié)構(gòu)遍歷:是根據(jù)訪(fǎng)問(wèn)結(jié)點(diǎn)操作發(fā)生位置命名

  • 前序(先根):先訪(fǎng)問(wèn)根節(jié)點(diǎn),然后訪(fǎng)問(wèn)左子樹(shù),最后訪(fǎng)問(wèn)右子樹(shù)
  • 中序(中根):先訪(fǎng)問(wèn)左節(jié)點(diǎn),然后訪(fǎng)問(wèn)根節(jié)點(diǎn),最后訪(fǎng)問(wèn)右子樹(shù) 
  • 后序(后根):先訪(fǎng)問(wèn)左節(jié)點(diǎn),然后訪(fǎng)問(wèn)右子樹(shù),最后訪(fǎng)問(wèn)根節(jié)點(diǎn)

 先定一個(gè)結(jié)構(gòu)體類(lèi)型:

typedef char BTDataType;
typedef struct BinarytreeNode
{
	BTDataType data;
	struct BinarytreeNode* left;
	struct BinarytreeNode* right;
}BTNode;

 前序:

void Preamble(BTNode* p)//前序
{
	if (p == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%c ", p->data);
	Preamble(p->left);
	Preamble(p->right);
}

 中序:

void Morder(BTNode* p)//中序
{
	if (p == NULL)
	{
		printf("NULL ");
		return;
	}
	Morder(p->left);
	printf("%c ", p->data);
	Morder(p->right);
}

后序:

void Porder(BTNode* p)//后序
{
	if (p == NULL)
	{
		printf("NULL ");
		return;
	}
	Porder(p->left);
	Porder(p->right);
	printf("%c ", p->data);
}

 求二叉樹(shù)結(jié)點(diǎn)的個(gè)數(shù):

int treeSize(BTNode* p)//結(jié)點(diǎn)個(gè)數(shù)
{
	return p == NULL ? 0 : treeSize(p->left) + treeSize(p->right)+1;
}

求葉子結(jié)點(diǎn)的個(gè)數(shù):

int treeLeafSize(BTNode* p)//葉子結(jié)點(diǎn)個(gè)數(shù)
{
	if (p == NULL)
	{
		return 0;
	}
	if (p->left == NULL&&p->right == NULL)
	{
		return 1;
	}
 
	return treeLeafSize(p->left) + treeLeafSize(p->right);
}

到此這篇關(guān)于C語(yǔ)言 超詳細(xì)總結(jié)講解二叉樹(shù)的概念與使用的文章就介紹到這了,更多相關(guān)C語(yǔ)言 二叉樹(shù)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • 一篇文章了解c++中的new和delete

    一篇文章了解c++中的new和delete

    C語(yǔ)言提供了malloc和free兩個(gè)系統(tǒng)函數(shù),完成對(duì)堆內(nèi)存的申請(qǐng)和釋放,而C++則提供了兩個(gè)關(guān)鍵字new和delete,下面這篇文章主要給大家介紹了如何通過(guò)一篇文章了解c++中new和delete的相關(guān)資料,需要的朋友可以參考下
    2021-12-12
  • C++使用VLD檢測(cè)內(nèi)存泄漏

    C++使用VLD檢測(cè)內(nèi)存泄漏

    本文主要介紹了C++使用VLD檢測(cè)內(nèi)存泄漏,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
    2023-06-06
  • C語(yǔ)言數(shù)據(jù)結(jié)構(gòu) link 鏈表反轉(zhuǎn)的實(shí)現(xiàn)

    C語(yǔ)言數(shù)據(jù)結(jié)構(gòu) link 鏈表反轉(zhuǎn)的實(shí)現(xiàn)

    這篇文章主要介紹了C語(yǔ)言數(shù)據(jù)結(jié)構(gòu) link 鏈表反轉(zhuǎn)的實(shí)現(xiàn)的相關(guān)資料,希望通過(guò)本文能幫助到大家,需要的朋友可以參考下
    2017-09-09
  • C語(yǔ)言輸入一個(gè)字符串的方法有哪些

    C語(yǔ)言輸入一個(gè)字符串的方法有哪些

    字符串輸入是C語(yǔ)言編程中非常重要的部分,其中scanf函數(shù)是一種廣泛使用的輸入字符串的方法,下面這篇文章主要給大家介紹了關(guān)于C語(yǔ)言輸入一個(gè)字符串的方法有哪些的相關(guān)資料,需要的朋友可以參考下
    2023-06-06
  • c++11可變參數(shù)使用示例

    c++11可變參數(shù)使用示例

    這篇文章主要介紹了c++11可變參數(shù)使用示例,需要的朋友可以參考下
    2014-03-03
  • C++利用eigen庫(kù)實(shí)現(xiàn)求歐拉角

    C++利用eigen庫(kù)實(shí)現(xiàn)求歐拉角

    這篇文章主要為大家詳細(xì)介紹了C++如何利用eigen庫(kù)自帶的matrix.eulerAngles()函數(shù)實(shí)現(xiàn)求歐拉角,文中的示例代碼講解詳細(xì),有需要的小伙伴可以參考下
    2023-11-11
  • C語(yǔ)言實(shí)現(xiàn)車(chē)輛出租管理系統(tǒng)

    C語(yǔ)言實(shí)現(xiàn)車(chē)輛出租管理系統(tǒng)

    這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)車(chē)輛出租管理系統(tǒng),文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2019-01-01
  • C語(yǔ)言鏈表完整操作演示

    C語(yǔ)言鏈表完整操作演示

    這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言鏈表的完整操作演示,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2018-05-05
  • 深入了解C語(yǔ)言中的字符串和內(nèi)存函數(shù)

    深入了解C語(yǔ)言中的字符串和內(nèi)存函數(shù)

    本文主要帶大家來(lái)學(xué)習(xí)一些常用的庫(kù)函數(shù)。有了這些庫(kù)函數(shù),我們可以更加方便地操作字符串和內(nèi)存,從而提升我們的編碼效率。話(huà)不多說(shuō),我們開(kāi)始吧
    2022-11-11
  • C/C++ 中實(shí)現(xiàn)讓控制臺(tái)暫停的方法

    C/C++ 中實(shí)現(xiàn)讓控制臺(tái)暫停的方法

    這篇文章主要介紹了C/C++ 中實(shí)現(xiàn)讓控制臺(tái)暫停的方法,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2022-07-07

最新評(píng)論