ppt第七章總結(jié)

樹(shù)結(jié)構(gòu)中常用的基本術(shù)語(yǔ)

父結(jié)點(diǎn)：若一個(gè)節(jié)點(diǎn)有子樹(shù)，則該結(jié)點(diǎn)為父結(jié)點(diǎn)。孩子結(jié)點(diǎn)：一個(gè)結(jié)點(diǎn)子樹(shù)的根。兄弟結(jié)點(diǎn)：同一個(gè)結(jié)點(diǎn)的孩子。

層次：根結(jié)點(diǎn)的層次為1，其余結(jié)點(diǎn)的層次是其父結(jié)點(diǎn)的層次加1。高度（深度）：樹(shù)中結(jié)點(diǎn)的最大層次數(shù)。度：一個(gè)結(jié)點(diǎn)的孩子數(shù)目是這個(gè)結(jié)點(diǎn)的度。如：圖中A的度為2葉子結(jié)點(diǎn)：度為0的結(jié)點(diǎn)。分支結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)。樹(shù)的度：樹(shù)中結(jié)點(diǎn)的最大的度。

有序樹(shù)/無(wú)序樹(shù)：兄弟結(jié)點(diǎn)之間的排列是否有序。森林：

森林是m(m≥0)棵互不相交的樹(shù)的集合。即：森林是多棵樹(shù)。

EGA

HIDFCB

J樹(shù)的存儲(chǔ):

1雙親表示法2孩子表示法

3孩子兄弟表示法雙親表示法:

實(shí)現(xiàn)：定義結(jié)構(gòu)數(shù)組存放樹(shù)的結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)含兩個(gè)域數(shù)據(jù)域：存放結(jié)點(diǎn)本身信息

雙親域：指示本結(jié)點(diǎn)的雙親結(jié)點(diǎn)在數(shù)組中位置特點(diǎn)：找雙親容易，找孩子難.孩子表示法:實(shí)現(xiàn)：

(1)把每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)排列起來(lái)，構(gòu)成一個(gè)單鏈表，稱為孩子鏈表；n個(gè)結(jié)點(diǎn)共有n個(gè)孩子鏈表（葉子結(jié)點(diǎn)的孩子鏈表為空表）。

(2)n個(gè)結(jié)點(diǎn)的數(shù)據(jù)和n個(gè)孩子鏈表的頭指針組成一個(gè)順序表。孩子兄弟表示法:實(shí)現(xiàn)：

用二叉鏈表作樹(shù)的存儲(chǔ)結(jié)構(gòu)，鏈表中每個(gè)結(jié)點(diǎn)的兩個(gè)指針域分別指向其第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)。特點(diǎn)：

(1)操作容易

(2)破壞了樹(shù)的層次

樹(shù)(森林)與二叉樹(shù)的轉(zhuǎn)換:一、樹(shù)轉(zhuǎn)換為二叉樹(shù)二、森林轉(zhuǎn)換為二叉樹(shù)

三、二叉樹(shù)轉(zhuǎn)換為樹(shù)或森林

一、樹(shù)轉(zhuǎn)換為二叉樹(shù):

將一棵樹(shù)轉(zhuǎn)換為二叉樹(shù)的方法是：

(1)樹(shù)中所有相鄰兄弟之間加一條連線。

(2)對(duì)樹(shù)中的每個(gè)結(jié)點(diǎn)，只保留其與第一個(gè)孩子結(jié)點(diǎn)之間的連線，刪去其與其它孩子結(jié)點(diǎn)之間的連

(3)以樹(shù)的根結(jié)點(diǎn)為軸心，將整棵樹(shù)順時(shí)針旋轉(zhuǎn)一定的角度，使之結(jié)構(gòu)層次分明。

下圖是樹(shù)轉(zhuǎn)換為二叉樹(shù)的結(jié)果示意圖。

二、森林轉(zhuǎn)換為二叉樹(shù):

森林轉(zhuǎn)換為二叉樹(shù)的方法如下：

(1)將森林中的每棵樹(shù)轉(zhuǎn)換成相應(yīng)的二叉樹(shù)。(2)將各二叉樹(shù)的根結(jié)點(diǎn)連在一起。

三、二叉樹(shù)轉(zhuǎn)換為樹(shù)或森林:

二叉樹(shù)轉(zhuǎn)換為樹(shù)或森林，具體方法如下：

(1)若某結(jié)點(diǎn)x是其父結(jié)點(diǎn)y的左孩子，則把該結(jié)點(diǎn)x的右孩子、右孩子的右孩子……都與y用線連起來(lái)。(2)刪掉原二叉樹(shù)中所有父結(jié)點(diǎn)與右孩子結(jié)點(diǎn)的連線。

樹(shù)的遍歷:

遍歷按一定規(guī)律走遍樹(shù)的各個(gè)頂點(diǎn)，且使每一頂點(diǎn)僅被訪問(wèn)一次，即找一個(gè)完整而有規(guī)律的走法，以得到樹(shù)中所有結(jié)點(diǎn)的一個(gè)線性排列。常用方法：

先根（序）遍歷：先訪問(wèn)樹(shù)的根結(jié)點(diǎn)，然后依次先根遍歷根的每棵子樹(shù)；后根（序）遍歷：先依次后根遍歷每棵子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)；

按層次遍歷：先訪問(wèn)第一層上的結(jié)點(diǎn)，然后依次遍歷第二層，……第n層的結(jié)點(diǎn)。

森林的遍歷:先序遍歷：若森林為空，返回；訪問(wèn)森林中第一棵樹(shù)的根結(jié)點(diǎn)；

先序遍歷第一棵樹(shù)中根結(jié)點(diǎn)的子樹(shù)森林；

先序遍歷除去第一棵樹(shù)之后剩余的樹(shù)構(gòu)成的森林。中序遍歷：

若森林為空，返回；

中序遍歷森林中第一棵樹(shù)的根結(jié)點(diǎn)的子樹(shù)森林；訪問(wèn)第一棵樹(shù)的根結(jié)點(diǎn)；

中序遍歷除去第一棵樹(shù)之后剩余的樹(shù)構(gòu)成的森林。

結(jié)論：

當(dāng)以二叉鏈表做樹(shù)的存儲(chǔ)結(jié)構(gòu)時(shí)，樹(shù)的先根序列和后根序列可借用二叉樹(shù)的先序遍歷和后序遍歷的算法實(shí)現(xiàn)之；對(duì)于森林也一樣。

習(xí)題：

1、已知一棵度為m的樹(shù)中有n1個(gè)度為1的結(jié)點(diǎn)，n2個(gè)度為2的結(jié)點(diǎn)，……，nm個(gè)度為m的結(jié)點(diǎn)，問(wèn)該樹(shù)中有多少片葉子？2、分別畫(huà)出下圖所示的森林的雙親表示形式、孩子鏈表表示形式和二叉鏈表表示形式。

3、將上圖的森林轉(zhuǎn)換為對(duì)應(yīng)的二叉樹(shù)。

擴(kuò)展閱讀：ppt第一章總結(jié)

數(shù)據(jù)是信息的載體數(shù)據(jù)元素是數(shù)據(jù)的基本單位數(shù)據(jù)項(xiàng)具有獨(dú)立含義的最小標(biāo)識(shí)單位

數(shù)據(jù)類(lèi)型可分為兩類(lèi)：簡(jiǎn)單數(shù)據(jù)類(lèi)型、結(jié)構(gòu)數(shù)據(jù)類(lèi)型

數(shù)據(jù)結(jié)構(gòu)包含3個(gè)內(nèi)容：數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算集合。數(shù)據(jù)的邏輯結(jié)構(gòu)：

線性邏輯結(jié)構(gòu)：元素之間一對(duì)一關(guān)系樹(shù)型邏輯結(jié)構(gòu)：元素之間一對(duì)多關(guān)系圖型邏輯結(jié)構(gòu)：元素之間多對(duì)多關(guān)系集合邏輯結(jié)構(gòu)

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)存儲(chǔ)方式有四種：

順序存儲(chǔ)：邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置相鄰的存儲(chǔ)單元中鏈接存儲(chǔ)：邏輯上相鄰的結(jié)點(diǎn)不一定存儲(chǔ)在物理位置相鄰的存儲(chǔ)單元

索引存儲(chǔ)：在存儲(chǔ)結(jié)點(diǎn)信息的同時(shí)，建立附加的索引表。散列存儲(chǔ)：應(yīng)用一個(gè)函數(shù)，將每一個(gè)結(jié)點(diǎn)的關(guān)鍵字作為該函數(shù)的自變量，得到相應(yīng)的函數(shù)值作為該結(jié)點(diǎn)的存儲(chǔ)地址。順序表線性結(jié)構(gòu)棧隊(duì)列數(shù)據(jù)的邏輯結(jié)構(gòu)串及數(shù)組樹(shù)形結(jié)構(gòu)非線性結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)圖形結(jié)構(gòu)散列結(jié)構(gòu)順序存儲(chǔ)鏈?zhǔn)酱鎯?chǔ)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)索引存儲(chǔ)散列存儲(chǔ)

數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改例題：已知定義：intx，*k=&x；試問(wèn)：表達(dá)式*k，&x，*&x，&*k，&*x和*&k各表示什么？答：對(duì)于*k，表示變量x。

對(duì)于&x，&是地址運(yùn)算符，&x表示變量x的地址。對(duì)于*&x，表示*k，即變量x。

對(duì)于&*k，*k表示變量x，&*k即表示變量x的地址(&x)。對(duì)于*&k，表示變量k。而&*x則存在語(yǔ)法錯(cuò)誤。

等等算法性能分析：1、算法的時(shí)間性能分析2、算法的空間性能分析【例】for(i=1;i習(xí)題4、計(jì)算下列各程序段的時(shí)間復(fù)雜度(1)for(i=0；i

友情提示：本文中關(guān)于《ppt第七章總結(jié)》給出的范例僅供您參考拓展思維使用，ppt第七章總結(jié)：該篇文章建議您自主創(chuàng)作。

來(lái)源：網(wǎng)絡(luò)整理 免責(zé)聲明：本文僅限學(xué)習(xí)分享，如產(chǎn)生版權(quán)問(wèn)題，請(qǐng)聯(lián)系我們及時(shí)刪除。

《ppt第七章總結(jié)》由互聯(lián)網(wǎng)用戶整理提供,轉(zhuǎn)載分享請(qǐng)保留原作者信息,謝謝!
鏈接地址：http://m.7334dd.com/gongwen/736996.html

• 上一篇：食品安全總結(jié)
• 下一篇：八月份工作總結(jié)