樹的遍歷與生成樹ppt課件-在線瀏覽
2025-03-03 22:10本頁面
【正文】 樹的遍歷 Tree Traversal ?當(dāng)以前序來遍歷表達式的二叉樹時，就獲得它的 前綴形式 ，又稱波蘭記法 ?前綴記法下的表達式無二義性 前綴形式？ 已知前綴形式，如何獲得對應(yīng)的表達式呢？ ?從右向左地求對應(yīng)的表達式 ?當(dāng)遇到一個運算，就對在這個運算右邊緊鄰的兩個運算對象執(zhí)行相應(yīng)的運算 ?每個運算結(jié)果是新的運算對象 例 5 前綴表達式 + *2 3 5 / ? 2 3 4的值是什么？ 樹的遍歷 Tree Traversal ? 中綴、前綴、后綴記法 (Infix, prefix, postfix notation) 樹的遍歷 Tree Traversal ?當(dāng)以后序來遍歷表達式的二叉樹時，就獲得它的 后綴形式 ，又稱逆波蘭記法 ?后綴記法下的表達式無二義性 后綴形式？ 已知后綴形式，如何獲得對應(yīng)的表達式呢？ ?從左向右地求對應(yīng)的表達式 ?當(dāng)兩個運算對象后面接著一個運算時，就執(zhí)行這個運算 ?每個運算結(jié)果是新的運算對象 例 6 后綴表達式 7 2 3 * 4 ? 9 3 / + 的值是什么？ 樹的遍歷 Tree Traversal 樹的遍歷 Tree Traversal 例：求復(fù)合命題 的有序根樹，然后基于這個根樹求這個表達式的前綴、中綴、后綴形式。否則 T1， T2， … ， Tn是 T里在 r處從左到右的子樹。 樹的遍歷 Tree Traversal 例 2 中序遍歷是以什么順序訪問圖中有序根樹里的頂點的？ 樹的遍歷 Tree Traversal j e n k o p b f a c l g m d h i [定義 3] 設(shè) T是帶根 r的有序根樹。否則 T1， T2， … ， Tn是 T里在 r處從左到右的子樹。 樹的遍歷 Tree Traversal 例 1 前序遍歷是以什么順序訪問圖中有序根樹里的頂點的？ 樹的遍歷 Tree Traversal a b e j k n o p f c d g l m h i [定義 2] 設(shè) T是帶根 r的有序根樹。前序遍歷 首先訪問 r。若 T只包含 r，則 r是 T的前序遍歷。隨后樹已經(jīng)被用來解決各種學(xué)科分支里的問題。第 7章 樹 Tree 不包含簡單回路的連通圖稱為樹， 早在 1857年英國數(shù)學(xué)家亞瑟 凱萊就用樹去計數(shù)某些類型的化合物。 Chap 7 樹 ? 樹的概念 /Introduction of Trees ? 樹的應(yīng)用 /Applications of Trees ? 樹的遍歷 /Tree Traversal ? 生成樹和最小生成樹 / Spanning Trees and minimum Spanning Trees ? 有序根樹常常用來保存信息，因此掌握訪問有序根樹的每個頂點以存取數(shù)據(jù)信息的算法非常必要 ? 系統(tǒng)地訪問有序根樹每個頂點的過程都稱為遍歷算法 ? 前序遍歷 Preorder traversal ? 中序遍歷 Inorder traversal ? 后序遍歷 Postorder traversal 樹的遍歷 Tree Traversal [定義 1] 設(shè) T是帶根 r的有序根樹。否則 T1， T2， … ， T
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1