ppt第七章總結

樹結構中常用的基本術語

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

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

有序樹/無序樹：兄弟結點之間的排列是否有序。森林：

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

EGA

HIDFCB

J樹的存儲:

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

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

實現(xiàn)：定義結構數(shù)組存放樹的結點，每個結點含兩個域數(shù)據域：存放結點本身信息

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

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

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

用二叉鏈表作樹的存儲結構，鏈表中每個結點的兩個指針域分別指向其第一個孩子結點和下一個兄弟結點。特點：

(1)操作容易

(2)破壞了樹的層次

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

三、二叉樹轉換為樹或森林

一、樹轉換為二叉樹:

將一棵樹轉換為二叉樹的方法是：

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

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

(3)以樹的根結點為軸心，將整棵樹順時針旋轉一定的角度，使之結構層次分明。

下圖是樹轉換為二叉樹的結果示意圖。

二、森林轉換為二叉樹:

森林轉換為二叉樹的方法如下：

(1)將森林中的每棵樹轉換成相應的二叉樹。(2)將各二叉樹的根結點連在一起。

三、二叉樹轉換為樹或森林:

二叉樹轉換為樹或森林，具體方法如下：

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

樹的遍歷:

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

先根（序）遍歷：先訪問樹的根結點，然后依次先根遍歷根的每棵子樹；后根（序）遍歷：先依次后根遍歷每棵子樹，然后訪問根結點；

按層次遍歷：先訪問第一層上的結點，然后依次遍歷第二層，……第n層的結點。

森林的遍歷:先序遍歷：若森林為空，返回；訪問森林中第一棵樹的根結點；

先序遍歷第一棵樹中根結點的子樹森林；

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

若森林為空，返回；

中序遍歷森林中第一棵樹的根結點的子樹森林；訪問第一棵樹的根結點；

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

結論：

當以二叉鏈表做樹的存儲結構時，樹的先根序列和后根序列可借用二叉樹的先序遍歷和后序遍歷的算法實現(xiàn)之；對于森林也一樣。

習題：

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

3、將上圖的森林轉換為對應的二叉樹。

擴展閱讀：ppt第一章總結

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

數(shù)據類型可分為兩類：簡單數(shù)據類型、結構數(shù)據類型

數(shù)據結構包含3個內容：數(shù)據的邏輯結構、數(shù)據的存儲結構和數(shù)據的運算集合。數(shù)據的邏輯結構：

線性邏輯結構：元素之間一對一關系樹型邏輯結構：元素之間一對多關系圖型邏輯結構：元素之間多對多關系集合邏輯結構

數(shù)據的存儲結構存儲方式有四種：

順序存儲：邏輯上相鄰的結點存儲在物理位置相鄰的存儲單元中鏈接存儲：邏輯上相鄰的結點不一定存儲在物理位置相鄰的存儲單元

索引存儲：在存儲結點信息的同時，建立附加的索引表。散列存儲：應用一個函數(shù)，將每一個結點的關鍵字作為該函數(shù)的自變量，得到相應的函數(shù)值作為該結點的存儲地址。順序表線性結構棧隊列數(shù)據的邏輯結構串及數(shù)組樹形結構非線性結構數(shù)據結構圖形結構散列結構順序存儲鏈式存儲數(shù)據的存儲結構索引存儲散列存儲

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

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

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

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

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

來源：網絡整理 免責聲明：本文僅限學習分享，如產生版權問題，請聯(lián)系我們及時刪除。

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

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