資源描述：
《《樹的遍歷與生成樹》PPT課件》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。
1、第7章樹Tree不包含簡單回路的連通圖稱為樹，早在1857年英國數(shù)學家亞瑟·凱萊就用樹去計數(shù)某些類型的化合物。隨后樹已經被用來解決各種學科分支里的問題。Chap7樹7.1樹的概念/IntroductionofTrees7.2樹的應用/ApplicationsofTrees7.3樹的遍歷/TreeTraversal7.4生成樹和最小生成樹/SpanningTreesandminimumSpanningTrees有序根樹常常用來保存信息，因此掌握訪問有序根樹的每個頂點以存取數(shù)據信息的算法非常必要系統(tǒng)地訪問有序根樹每個頂點的過程都稱為遍歷算法前序遍歷Preordertraver
2、sal中序遍歷Inordertraversal后序遍歷Postordertraversal7.3樹的遍歷TreeTraversal[定義1]設T是帶根r的有序根樹。若T只包含r，則r是T的前序遍歷。否則T1，T2，…，Tn是T里在r處從左到右的子樹。前序遍歷首先訪問r。接著以前序來遍歷T1，然后以前序來遍歷T2，依此類推，直到以前序遍歷了Tn為止。7.3樹的遍歷TreeTraversal例1前序遍歷是以什么順序訪問圖中有序根樹里的頂點的？7.3樹的遍歷TreeTraversalabejknopfcdglmhi[定義2]設T是帶根r的有序根樹。若T只包含r，則r是T的中序遍
3、歷。否則T1，T2，…，Tn是T里在r處從左到右的子樹。中序遍歷首先以中序來遍歷T1，然后訪問r，接著以中序遍歷T2，以中序遍歷T3，依此類推，直到以中序遍歷了Tn為止。7.3樹的遍歷TreeTraversal例2中序遍歷是以什么順序訪問圖中有序根樹里的頂點的？7.3樹的遍歷TreeTraversaljenkopbfaclgmdhi[定義3]設T是帶根r的有序根樹。若T只包含r，則r是T的后序遍歷。否則T1，T2，…，Tn是T里在r處從左到右的子樹。后序遍歷首先以后序來遍歷T1，以后序遍歷T2，……，然后以后序遍歷Tn，最后訪問r。7.3樹的遍歷TreeTraversal
4、例3后序遍歷是以什么順序訪問圖中有序根樹里的頂點的？7.3樹的遍歷TreeTraversaljnopkefbclmghida7.3樹的遍歷TreeTraversal7.3樹的遍歷TreeTraversal7.3樹的遍歷TreeTraversal以前序、中序、后序來列出有序根樹的頂點的簡易方法：首先從根開始圍繞有序根樹畫一條曲線，沿著邊移動；7.3樹的遍歷TreeTraversal前序：當曲線第一次經過一個頂點時，就列出這個頂點中序：當曲線第一次經過一個樹葉時，就列出這個樹葉，當曲線第二次經過一個內點時就列出這個內點后序：當曲線最后一次經過一個頂點而返回這個頂點的父母時，就
5、列出這個頂點練習：寫出該有序根圖按照前序、中序、后序遍歷訪問的頂點順序7.3樹的遍歷TreeTraversal前序：abdefgc中序：dbfegac后序：dfgebca中綴、前綴、后綴記法(Infix,prefix,postfixnotation)7.3樹的遍歷TreeTraversal可用有序樹來表示復雜的表達式包括算術表達式、復合命題、集合的組合等表示算術表達式時內點表示運算，樹葉表示變量或數(shù)字，每個運算都作用在它的子樹上例4表示表達式((x+y)?2)+((x-4)/3)的有序根樹是什么？中綴、前綴、后綴記法(Infix,prefix,postfixnotatio
6、n)7.3樹的遍歷TreeTraversal對表示一個表達式的有序根樹的中序遍歷，產生原來的表達式中綴、前綴、后綴記法(Infix,prefix,postfixnotation)7.3樹的遍歷TreeTraversal對表示一個表達式的二叉樹的中序遍歷，產生原來的表達式中序遍歷得出的中綴表達式有二義性為避免二義性，中序遍歷時需加括號，這種表達式稱為中綴形式(x+y)/(x+3)(x+(y/x))+3x+(y/(x+3))中序遍歷?x+y/x+3中綴、前綴、后綴記法(Infix,prefix,postfixnotation)7.3樹的遍歷TreeTraversal當以前序來
7、遍歷表達式的二叉樹時，就獲得它的前綴形式，又稱波蘭記法前綴記法下的表達式無二義性前綴形式？+?+xy2/-x43已知前綴形式，如何獲得對應的表達式呢？從右向左地求對應的表達式當遇到一個運算，就對在這個運算右邊緊鄰的兩個運算對象執(zhí)行相應的運算每個運算結果是新的運算對象例5前綴表達式+-*235/?234的值是什么？7.3樹的遍歷TreeTraversal中綴、前綴、后綴記法(Infix,prefix,postfixnotation)7.3樹的遍歷TreeTraversal當以后序來遍歷表達式的二叉樹時，就獲得它的后綴形式，又稱逆
