ppt第七章總結(jié)

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

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

層次：根結(jié)點(diǎn)的層次為1，其余結(jié)點(diǎn)的層次是其父結(jié)點(diǎn)的層次加1。高度（深度）：樹中結(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)。樹的度：樹中結(jié)點(diǎn)的最大的度。

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

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

EGA

HIDFCB

J樹的存儲(chǔ):

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

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

實(shí)現(xiàn)：定義結(jié)構(gòu)數(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)排列起來，構(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)：

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

(1)操作容易

(2)破壞了樹的層次

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

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

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

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

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

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

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

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

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

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

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

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

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

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

樹的遍歷:

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

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

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

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

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

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

若森林為空，返回；

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

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

結(jié)論：

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

習(xí)題：

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

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

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

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

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

數(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)系樹型邏輯結(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ù)組樹形結(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；試問：表達(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則存在語法錯(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)作。

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

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

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