国产成人精品三级麻豆,色综合天天综合高清网,亚洲精品夜夜夜,国产成人综合在线女婷五月99播放,色婷婷色综合激情国产日韩

一、簡(jiǎn)介

世界上的樹(shù)有千萬(wàn)種，我們這里來(lái)學(xué)習(xí)我們數(shù)據(jù)結(jié)構(gòu)中的樹(shù)，它是我們現(xiàn)實(shí)生活中倒置的樹(shù)。之前，我們學(xué)習(xí)的順序表，鏈表，棧、和隊(duì)列�？梢哉f(shuō)都是我們的線性結(jié)構(gòu)，也就是我們所謂的一對(duì)一的結(jié)構(gòu)，可是現(xiàn)實(shí)生活中，我們經(jīng)常碰到是我們一對(duì)多的情況。今天，我們就來(lái)研究一下這種一對(duì)多的數(shù)據(jù)結(jié)構(gòu)體-----“樹(shù)”。那么，什么叫做樹(shù)呢？

二、樹(shù)的基本概念簡(jiǎn)介

<1>樹(shù)的定義

專(zhuān)業(yè)定義：(1)有且只有一個(gè)稱(chēng)為根的結(jié)點(diǎn)

(2)有若干不相交的子樹(shù)，這些子樹(shù)本身也是一顆樹(shù)。

通俗講解：

(1)樹(shù)由結(jié)點(diǎn)和邊組成

(2)樹(shù)中除根節(jié)點(diǎn)外，每一個(gè)節(jié)點(diǎn)都有一個(gè)父結(jié)點(diǎn)，但是 可以用多個(gè)子節(jié)點(diǎn)。

(3)根結(jié)點(diǎn)沒(méi)有父結(jié)點(diǎn)

<2>樹(shù)中的專(zhuān)業(yè)術(shù)語(yǔ)

節(jié)點(diǎn) ： 父節(jié)點(diǎn) 子節(jié)點(diǎn)(老子和兒子) 堂兄弟

度： 結(jié)點(diǎn)擁有子樹(shù)的個(gè)數(shù)

葉子節(jié)點(diǎn)：沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)

邊 : 一個(gè)節(jié)點(diǎn)到另一個(gè)節(jié)點(diǎn)的距離

樹(shù)的深度：節(jié)點(diǎn)的層數(shù)， 根節(jié)點(diǎn)默認(rèn)為第一層。

有序 ：樹(shù)的左右位置不能改變。

<3>樹(shù)的分類(lèi)

一般樹(shù) ： 任意一個(gè)結(jié)點(diǎn)的子節(jié)點(diǎn)的個(gè)數(shù)不受限制，則稱(chēng)為一般樹(shù)。(子節(jié)點(diǎn)可以有多個(gè))，如下圖：

二叉樹(shù)(重點(diǎn))：任意一個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)的個(gè)數(shù)多有兩個(gè)，且子節(jié)點(diǎn)的個(gè)數(shù)不能更改。

森林：樹(shù)去掉根結(jié)點(diǎn)就稱(chēng)之為森林。

提問(wèn)：在下圖中：

<1>A,B,H,I的度分別是多少?

A:3 B : 2 H: 1 I: 0

<2>葉子節(jié)點(diǎn)有哪些?

K ,L,F,G,H,I,J

<3>結(jié)點(diǎn)F和I在樹(shù)中的第幾層?

F在第3層。

M在第4層

<4>樹(shù)的深度是多少?

4

三、二叉樹(shù)的特性講解

<1>二叉樹(shù)的性質(zhì)講解

如下圖是一顆二叉樹(shù)，它有一些特性：

思考：第一層多有多少個(gè)? 1個(gè)

第二層多有多少個(gè)? 2 個(gè)

第三層多有多少個(gè)? 4 ?

規(guī)律：第i層結(jié)點(diǎn)后有2的n - 1次方個(gè)。

性質(zhì)1:二叉樹(shù)的第i層上的結(jié)點(diǎn)多有2的i - 1次方個(gè)節(jié)點(diǎn)。

思考：深度為1的二叉樹(shù)(遍歷第一層)一共有多少個(gè)節(jié)點(diǎn)? 1個(gè)

深度為2的二叉樹(shù)(遍歷到第二層)一共有多少個(gè)節(jié)點(diǎn)? 3個(gè)

深度為3的二叉樹(shù)(遍歷到第三層)一共有多少個(gè)節(jié)點(diǎn)? 7個(gè)

規(guī)律：深度為k的而出書(shū)，多有2的k次方 - 1個(gè)節(jié)點(diǎn)。

性質(zhì)2：深度為k的二叉樹(shù)多有2的k次方-1個(gè)結(jié)點(diǎn)。

性質(zhì)3：在任意一棵二叉樹(shù)中，樹(shù)葉的數(shù)目比度數(shù)為2的結(jié)點(diǎn)的數(shù)目多1.

(推導(dǎo)過(guò)程入下圖所示：)

<2>二叉樹(shù)的分類(lèi)

滿二叉樹(shù)：在一顆二叉樹(shù)中，如果所有的分支節(jié)點(diǎn)都存在左子樹(shù)和右子樹(shù)，并且所有的葉子節(jié)點(diǎn)都在同一層上，這樣的二叉樹(shù)，我們稱(chēng)之為滿二叉樹(shù)。

滿二叉樹(shù)的特點(diǎn)：<1>葉子節(jié)點(diǎn)只會(huì)出現(xiàn)在下面一層。

<2>非葉子節(jié)點(diǎn)的節(jié)點(diǎn)，擁有子樹(shù)的個(gè)數(shù)一定為2.

<3>在同樣深度的二叉樹(shù)中，滿二叉樹(shù)的節(jié)點(diǎn)個(gè)數(shù)多。

完全二叉樹(shù)：對(duì)一顆具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)按層進(jìn)行編號(hào)，如果編號(hào)為i

(1 <= i <= n)的結(jié)點(diǎn)與同樣深度的滿二叉樹(shù)節(jié)點(diǎn)編號(hào)為i的結(jié)點(diǎn)

在二叉樹(shù)中的位置完全相同，則這顆樹(shù)，我們稱(chēng)之為完全二叉樹(shù)。

如下圖所示。

提問(wèn)：下面這些樹(shù)，是完全二叉樹(shù)嗎? 不是

總結(jié)：滿二叉樹(shù)一定是完全二叉樹(shù)，完全二叉樹(shù)不一定是滿二叉樹(shù)。

四、二叉樹(shù)的存儲(chǔ)

(1)順序存儲(chǔ)[完全二叉樹(shù)]

(順序存儲(chǔ)的話，若不是完全二叉樹(shù)存儲(chǔ)沒(méi)有意義。)

假設(shè)下面有一顆樹(shù)，我們?nèi)绾伟阉�存到�?shù)組中呢?

思路：先把轉(zhuǎn)換成完全二叉樹(shù)，然后再編號(hào)。

這樣存儲(chǔ)就看似沒(méi)有什么問(wèn)題。我們可以按照編號(hào)把數(shù)據(jù)存儲(chǔ)到數(shù)組中，我們按照編號(hào)(1,2,3,4,5)的順序存儲(chǔ)就可以了啊!這個(gè)時(shí)候，我就要問(wèn)了，假說(shuō)說(shuō)，我們的m的編號(hào)，你怎么知道我們的3好位置是在下面，而不是在我們的m編號(hào)的位置呢?我們的連續(xù)存儲(chǔ)無(wú)法識(shí)別。(這種方法，我們無(wú)法推斷樹(shù)的結(jié)構(gòu))。

因此，我們順序存儲(chǔ)規(guī)定：

無(wú)論是何種樹(shù)，我們都會(huì)轉(zhuǎn)換成完全二叉樹(shù)。然后一層一層的從左給我們的二叉樹(shù)進(jìn)行編號(hào)，然后存儲(chǔ)在數(shù)組中。及如下圖。

那么我們以上的存儲(chǔ)有什么規(guī)律呢?假設(shè)某個(gè)節(jié)點(diǎn)為i的話，我們來(lái)觀察一下。

是不是所有的左孩子都是偶數(shù)，所有的右孩子都是奇數(shù)啊！

完全二叉樹(shù)的特點(diǎn)：

對(duì)于編號(hào)為i(i>=1)的結(jié)點(diǎn)：

(1)左孩子存在：2 * i <= n(節(jié)點(diǎn)的個(gè)數(shù))，左孩子編號(hào)

(2)右孩子存儲(chǔ)：2 * i + 1 <= n,右孩子編號(hào) 2 * i + 1

(2)鏈?zhǔn)酱鎯?chǔ)[完全二叉樹(shù)]

鏈?zhǔn)酱鎯?chǔ)：定義結(jié)點(diǎn)保存左孩子和右孩子的地址。

思考：上述過(guò)程，我們的二叉樹(shù)應(yīng)該定義什么樣的數(shù)據(jù)類(lèi)型來(lái)保存結(jié)點(diǎn)呢？

<4>二叉樹(shù)的遍歷

(1)層次遍歷:從上到下一層一層的遍歷

(2)前序遍歷:根 、左(左子樹(shù))、右(右子樹(shù))

(3)中序遍歷:左(左子樹(shù)) 、根 、右(右子樹(shù))

(4)后序遍歷:左(左子樹(shù))、右(右子樹(shù))、根

規(guī)則：遇到根結(jié)點(diǎn)則輸出，否則遍歷。

層次遍歷：ABCDEFGHI

先序遍歷：ABDGHCEIF

中序遍歷：GDHBAEICF

后序遍歷：GHDBIEFCA

完全二叉樹(shù)的遞歸創(chuàng)建思路：

1.首先，寫(xiě)一個(gè)創(chuàng)建單個(gè)節(jié)點(diǎn)的函數(shù)malloc_bnode，左孩子和右孩子都為空并且填充，我們需要的數(shù)據(jù)

2.然后寫(xiě)一個(gè)創(chuàng)建二叉樹(shù)的函數(shù)create_binarytree()函數(shù)。調(diào)用malloc_bond

函數(shù)創(chuàng)建節(jié)點(diǎn)，然后判斷結(jié)點(diǎn)有沒(méi)有左孩子和右孩子。

2 *num <= n ，左孩子存在 (num為我們的結(jié)點(diǎn)編號(hào)，n為我們的結(jié)點(diǎn)個(gè)數(shù))

再次，調(diào)用create_binarytree()創(chuàng)建該編號(hào)的孩子。

2 *num + 1 <=n,右孩子存儲(chǔ)。

再次，調(diào)用create_binarytree()創(chuàng)建該編號(hào)的孩子，后返回根節(jié)點(diǎn)。

 

二叉樹(shù)相關(guān)文章：

二叉樹(shù)的一個(gè)典型應(yīng)用-哈夫曼樹(shù)一