C++程序設計與數據結構基礎：第10章 非線性結構_第1頁
C++程序設計與數據結構基礎：第10章 非線性結構_第2頁
C++程序設計與數據結構基礎：第10章 非線性結構_第3頁
C++程序設計與數據結構基礎：第10章 非線性結構_第4頁
C++程序設計與數據結構基礎：第10章 非線性結構_第5頁
已閱讀5頁，還剩17頁未讀， 繼續免費閱讀

下載本文檔

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

1、第三部分第三部分 數據結構基礎數據結構基礎本章內容 樹的基本概念 二叉樹的基本概念和性質 二叉樹的存儲結構 二叉樹的遍歷 樹、森林與二叉樹的轉換 2 210.1 樹的基本概念l 樹：是一類非常重要的非線性結構，適合于描述數據元素之間的層次關系。3 3l 樹是n(n0)個數據元素的有限集合T。它滿足以下兩個條件：P2671.有且僅有一個特定的稱為根的元素。 一棵樹中，有且僅有一個根結點。 根是只有后件沒有前件的結點。 除根結點外，其它結點均有且僅有一個前件。 每個結點均可以有任意多個后件，沒有后件的結點稱為葉子結點。 除根結點和葉子結點外，其余稱內結點。2.其余元素分為m（m0）個互不相交的有限

2、集合T1、T2、Tm，其中每個集合又都是一棵樹并稱其為根的子樹。數學上的定義4 4A AB BE EF FK KL LC CG GMMD DHHNNI IJ JA AB BE EL L5 5樹的常用術語l 雙親、子女、兄弟、邊： 若結點y是結點x的一棵子樹的根，則x稱做y的“雙親”(parents)，y稱做x的“子女”(child) 有序對稱做從x到y的“邊”。 具有同一雙親的結點稱為“兄弟”。l 路徑、路徑長度： 若樹中存在著一個結點的序列k1 k2kj，使ki是ki+1（1i0，則ki雙親結點的編號為 (i-1)/2； 若i=0，則ki是根結點。 若2i+1n，則ki左子女結點的編號是2i

3、+1，否則ki無左子女。若2i+2n，則ki右子女結點的編號為2i+2，否則ki無右子女。1616二叉樹的存儲結構 l 順序存儲結構 對完全二叉樹，利用性質5，將其所有結點按編號順序依次存儲在一維數組里。 對一般二叉樹，需要加上一些并不存在的“虛結點”，轉換為完全二叉樹的形式。 1717l 二叉樹的鏈式存儲結構鏈接存儲時結點的結構lchilddatarchildA AB BC C F F D D E EG GHHrootroot存儲結構邏輯結構1818二叉樹的遍歷l 先序遍歷 ：訪問根結點(D)，先序遍歷左子樹(L)，先序遍歷右子樹(R)。 ABDGECFl 中序遍歷：LDR DGBEAFCl 后序遍歷：LRD GDEBFCAl 層次遍歷：按層數由小到大、同一層從左到右順序依次訪問二叉樹的各個結點。 ABCDEFG1919樹、森林與二叉樹的轉換 l 樹到二叉樹的轉換1. 在所有的兄弟之間加一條連線；2. 對每個結點，除了保留與最左邊子女的連線外，去掉與其他子女連線；3. 將保留下來的邊作為左子樹的邊，兄弟間的連線作為右子樹的邊。2020l 森林到二叉樹的轉換1. 先將森林中的每一棵樹變為二叉樹，2. 然后將各二叉樹的根結點看成兄弟，用線把它們連到一起，3. 經整理后可得到相應的二叉樹。2121l 二叉樹到樹、森林的

溫馨提示

  • 1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙，網頁內容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業或盈利用途。
  • 5. 人人文庫網僅提供信息存儲空間，僅對用戶上傳內容的表現方式做保護處理，對用戶上傳分享的文檔內容本身不做任何修改或編輯，并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容，請與我們聯系，我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論