Re: 樹的走法

[mantour (朱子)]

※ 引述《sansia (sansia)》之銘言：
: 有一棵二元樹（binary tree）的後序追蹤（postorder traversal）順序為DAGCIHBEF
: 且其中序追蹤（inorder traversal）順序為DGAFCHIEB，請畫出這棵二元樹。
: 請問這題有什麼好的解法
: 還是只能像白老鼠一樣 by trial and error?

post-order的最後一個(F)為最上層的root

inorder中F左邊的(DGAF)是left subtree, 右邊的(CHIEB)是right subtree

因此可以得知root和左右subtree的post及in-order traversal 順序

再用遞迴的方式把左右的subtree解出來

        DAGCIHBEF (post)
        DGAFCHIEB (in)
           ||
           F
         /   \
       DAG     CIHBE    (post)
       DGA     CHIEB    (in)
        ||        ||
        G          E
       / \        / \
      D   A     CIH  B
                CHI
                 ||
                 H
                / \
                C  I



--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.125.84
推 mqazz1      :我畫出來的好像和大大不同...H和I交換是我的結果....
推 sansia      :大大畫錯了 :P
→ sansia      :請問這種題目是不是在補習班講義裡有啊?
感謝更正

推 mqazz1      :了解遞迴的概念就差不多了....一般資料結構的書都有
※ 編輯: mantour         來自: 61.57.65.181         (08/20 10:39)