樹的遍歷與生成樹ppt課件-展示頁
2025-01-23 22:10本頁面
【正文】 ? 任選圖中一個(gè)頂點(diǎn)作為根，通過相繼添加邊來形成從這個(gè)頂點(diǎn)開始的通路，其中每條新邊都與通路上的最后一個(gè)頂點(diǎn)以及還不在通路上的一個(gè)頂點(diǎn)關(guān)聯(lián)。 注：移去邊時(shí)可隨意 ， 故生成樹不唯一 。 充分性 ：若 G是連通的 , 1) 若 G無回路，則 G本身是樹，即生成樹。?E 例 1 找出下面簡單圖的生成樹。 T=(V, E39。 8,11(a) Chap 7 樹 ? 樹的概念 /Introduction of Trees ? 樹的應(yīng)用 /Applications of Trees ? 樹的遍歷 /Tree Traversal ? 生成樹和最小生成樹 / Spanning Trees and minimum Spanning Trees 生成樹和最小生成樹 Spanning Trees and minimum Spanning Trees 緬因州的道路系統(tǒng)圖 確保任兩個(gè)鄉(xiāng)鎮(zhèn)都有通路，且不能有多余的邊。 樹的遍歷 Tree Traversal 例 3 后序遍歷是以什么順序訪問圖中有序根樹里的頂點(diǎn)的？ 樹的遍歷 Tree Traversal j n o p k e f b c l m g h i d a 樹的遍歷 Tree Traversal 樹的遍歷 Tree Traversal 樹的遍歷 Tree Traversal ? 以前序、中序、后序來列出有序根樹的頂點(diǎn)的簡易方法： ? 首先從根開始圍繞有序根樹畫一條曲線，沿著邊移動(dòng) ； 樹的遍歷 Tree Traversal ? 前序 ：當(dāng)曲線第一次經(jīng)過一個(gè)頂點(diǎn)時(shí)，就列出這個(gè)頂點(diǎn) ? 中序 ：當(dāng)曲線第一次經(jīng)過一個(gè)樹葉時(shí)，就列出這個(gè)樹葉，當(dāng)曲線第二次經(jīng)過一個(gè)內(nèi)點(diǎn)時(shí)就列出這個(gè)內(nèi)點(diǎn) ? 后序 ：當(dāng)曲線最后一次經(jīng)過一個(gè)頂點(diǎn)而返回這個(gè)頂點(diǎn)的父母時(shí)，就列出這個(gè)頂點(diǎn) 練習(xí) ： 寫出該有序根圖按照前序、中序、后序遍歷訪問的頂點(diǎn)順序 樹的遍歷 Tree Traversal 前序： abdefgc 中序： dbfegac 后序： dfgebca ?中綴、前綴、后綴記法 (Infix, prefix, postfix notation) 樹的遍歷 Tree Traversal ?可用有序樹來表示復(fù)雜的表達(dá)式 ? 包括算術(shù)表達(dá)式、復(fù)合命題、集合的組合等 ? 表示算術(shù)表達(dá)式時(shí)內(nèi)點(diǎn)表示運(yùn)算，樹葉表示變量或數(shù)字，每個(gè)運(yùn)算都作用在它的子樹上 例 4 表示表達(dá)式 ((x+y)?2)+((x4)/3) 的 有序根樹是什么？ ? 中綴、前綴、后綴記法 (Infix, prefix, postfix notation) 樹的遍歷 Tree Traversal ?對(duì)表示一個(gè)表達(dá)式的有序根樹的中序遍歷，產(chǎn)生原來的表達(dá)式 ? 中綴、前綴、后綴記法 (Infix, prefix, postfix notation) 樹的遍歷 Tree Traversal ?對(duì)表示一個(gè)表達(dá)式的二叉樹的中序遍歷，產(chǎn)生原來的表達(dá)式 ?中序遍歷得出的中綴表達(dá)式有二義性 ?為避免二義性，中序遍歷時(shí)需加括號(hào)，這種表達(dá)式稱為 中綴形式 (x+y)/(x+3) (x+(y/x))+3 x+(y/(x+3)) 中序遍歷 ? ? 中綴、前綴、后綴記法 (Infix, prefix, postfix notation)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1