ppt第七章總結(jié)

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

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

層次：根結(jié)點(diǎn)的層次為1，其余結(jié)點(diǎn)的層次是其父結(jié)點(diǎn)的層次加1。高度（深度）：樹中結(jié)點(diǎn)的最大層次數(shù)。度：一個結(jié)點(diǎn)的孩子數(shù)目是這個結(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樹的存儲:

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

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

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

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

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

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

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

(1)操作容易

(2)破壞了樹的層次

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

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

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

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

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

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

(3)以樹的根結(jié)點(diǎn)為軸心，將整棵樹順時針旋轉(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ī)律走遍樹的各個頂點(diǎn)，且使每一頂點(diǎn)僅被訪問一次，即找一個完整而有規(guī)律的走法，以得到樹中所有結(jié)點(diǎn)的一個線性排列。常用方法：

先根（序）遍歷：先訪問樹的根結(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)以二叉鏈表做樹的存儲結(jié)構(gòu)時，樹的先根序列和后根序列可借用二叉樹的先序遍歷和后序遍歷的算法實(shí)現(xiàn)之；對于森林也一樣。

習(xí)題：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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