Re: [問題] 二元樹建立問題

[cismjmgoshr (--？？？--)]

※ 引述《darkcookies (D-GRAY MAN)》之銘言：
: 開發平台(Platform): GCC
: 額外使用到的函數庫(Library Used):
: 問題(Question)：請問我有一個輸入是
: 5 1 1 4 1 0 8 1 1 11 1 1 13 0 0 4 0 1 7 0 0 2 0 0 1 0 0
: 樹長成
:                  5
:                 / \
:                4   8
:               /   / \
:              11  13  4
:             / \       \
:            7   2       1

T代表現在的二元樹，Q代表現在佇列的狀態
佇列的第一個元素代表下一個節點要接的位置(例如5L表示要接在5這個節點的左邊)
每次加入一個節點之後，就把它的子樹位置加到佇列的最後面

輸入:(每3個數字代表一個節點)
5 1 1 4 1 0 8 1 1 11 1 1 13 0 0 4 0 1 7 0 0 2 0 0 1 0 0

Step 1:
5 1 1 ,根節點. 加入5L,5R至佇列
T:
      5

Q: 5L 5R

--

Step 2:
4 1 0 ,加在5的左邊. 加入4L至佇列
T:
      5
     /
    4

Q: 5R 4L

--

Step 3:
8 1 1 ,加在5的右邊. 加入8L,8R至佇列
T:
      5
     / \
    4   8

Q: 4L 8L 8R

--

Step 4:
11 1 1 ,加在4的左邊. 加入11L,11R至佇列
T:
      5
     / \
    4   8
   /
  11

Q: 8L 8R 11L 11R

--

Step 5:
13 0 0 ,加在8的左邊
T:
      5
     / \
    4   8
   /   /
  11  13

Q: 8R 11L 11R

--

Step 6:
4 0 1 ,加在8的右邊. 加入4R至佇列
T:
      5
     / \
    4   8
   /   / \
  11  13  4

Q: 11L 11R 4R

--

Step 7:
7 0 0 ,加在11的左邊
T:
      5
     / \
    4   8
   /   / \
  11  13  4
 /
7

Q: 11R 4R

--

Step 8:
2 0 0 ,加在11的右邊
T:
      5
     / \
    4   8
   /   / \
  11  13  4
 /  \
7    2

Q: 4R

--

Step 9:
1 0 0 ,加在4的右邊
T:
      5
     / \
    4   8
   /   / \
  11  13  4
 / \       \
7   2       1

Q: (NULL)

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 220.135.134.15
推 darkcookies:請問我要使用queue.push(某個節點的left指標)，我要
→ darkcookies:我要怎麼宣告queue<型態> 變數;
→ firejox:queue.push(&某個節點的left指標)
→ firejox:宣告queue的型態用雙重指標...
→ firejox:要用指標也可以 只是作法有點不同
→ darkcookies:我最後要算出全部路徑的和，大大覺得怎麼寫比較好?
→ diabloevagto:DFS?
→ firejox:路徑和?從根出發的?
→ darkcookies:從根出發到葉，以上面例子就是顯示四個和
→ diabloevagto:那樣就是dfs就ok摟
→ firejox:dfs bfs都可以...
推 darkcookies:謝謝F大以及D大提供的意見，對小弟有很大的幫助^^