數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)ppt-展示頁(yè)
2025-08-14 07:40本頁(yè)面
【正文】 I H G F E A C X B A的第 1棵子樹(shù) A的第 3棵子樹(shù) A的第 2棵子樹(shù) 二 . 樹(shù) (邏輯上 )的特點(diǎn) 1. 有且僅有一個(gè)結(jié)點(diǎn)沒(méi)有前驅(qū)結(jié)點(diǎn) ,該結(jié)點(diǎn)為樹(shù)的根結(jié)點(diǎn)。第 6章 樹(shù)與二叉樹(shù) 校長(zhǎng) 一 系 二 系 三 系 六 系 教 務(wù) 處 科 研 處 總 務(wù) 處 601 602 教 務(wù) 科 603 A B C D … … … … 張 三 李 四 王 五 … 例 1 … 工 廠 (根目錄 ) \ f1 f2 f3 fn d1 d2 dm … … … 例 2 f11 f12 f1k d11 d12 … … … … 例 3 1 樹(shù)的基本概念 2 樹(shù)的存儲(chǔ)結(jié)構(gòu) 3 二叉樹(shù) 4 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu) 5 二叉樹(shù)的遍歷 6 線索二叉樹(shù) 樹(shù)的基本概念 樹(shù) 是由 n?0 個(gè)結(jié)點(diǎn)組成的有窮集合 (不妨用 D表示 )以及結(jié)點(diǎn)之間關(guān)系組成的集合構(gòu)成的結(jié)構(gòu)。 當(dāng) n=0 時(shí)，稱該樹(shù)為空樹(shù)； 在任何一棵非空的樹(shù)中，有一個(gè)特殊的結(jié)點(diǎn) t ?D，稱之為該樹(shù)的根結(jié)點(diǎn)；其余結(jié)點(diǎn) D–{t}被分割成 m0個(gè) 不相交的子集 D1, D2, … ,D m,其中每一個(gè)子集 Di又為一棵樹(shù)，分別稱之為 t 的 子樹(shù) 。 2. 除了根結(jié)點(diǎn)外 ,每個(gè)結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)結(jié)點(diǎn)。 J I H G F E A C X B 4. 樹(shù)形表示法 借助自然界中一棵倒置的樹(shù)的形狀來(lái)表示數(shù)據(jù)元素之間層次關(guān)系的方法。 樹(shù)中結(jié)點(diǎn)度的最大值 。 J I H G F E A C X B 深度為 3的樹(shù) 二叉樹(shù)的基本形態(tài)： (空 ) 根 根 左 子 樹(shù) 根 右 子 樹(shù) 根 左 子 樹(shù) 右 子 樹(shù) 二叉樹(shù) 二 . 兩種特殊形態(tài)的二叉樹(shù) 若一棵二叉樹(shù)中的結(jié)點(diǎn) , 或者為葉結(jié)點(diǎn)， 或者具有兩 棵非空子樹(shù) ,并且葉結(jié)點(diǎn)都集 中在二叉樹(shù)的最下面一層 .這 樣的二叉樹(shù)為滿二叉樹(shù) . 1. 滿二叉樹(shù) 若一棵二叉樹(shù)中只有最下 面兩層的結(jié)點(diǎn)的度可以小于 2, 并且最下面一層的結(jié)點(diǎn) (葉結(jié) 點(diǎn) )都依次排列在該層從左至 右的位置上。 三 . 二叉樹(shù)的性質(zhì) 2. 深度為 h 的非空二叉樹(shù)最多有 2h 1個(gè)結(jié)點(diǎn) . 3. 若非空二叉樹(shù)有 n0個(gè)葉結(jié)點(diǎn) ,有 n2個(gè)度為 2的結(jié)點(diǎn) , 則 n0=n2+1 4. 具有 n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度 h=
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1