[問題] bst的iterator 還有 end()

[bnsblue (想當你的天空)]

   我有兩個問題想請問大家：

   1. 根據題目要求，bst的iterator感覺上應該是要作成in-order的（？）
      那還有需要把post-order和pre-order都implement嗎？

   2. 由於在處理end()的時候遇到一些問題，所以有想到是不是
      要把external node做出來呢？而且要怎麼判斷external node的parent是誰呢？

      (要不然insert()實在是很難做...orz)

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 220.137.69.97
推 HigherKuo:我想問的是，operator ++ --就是找下一個node，除了
→ HigherKuo:traverse整個tree一次之外(應該會慢到不行)，有什麼比較
→ HigherKuo:聰明的方式呢？
→ bnsblue:其實有幾種case 如果有子樹的話可以直接找successor
→ bnsblue:還有一些case可以用記錄"從root走到這個點的過程"
→ bnsblue:但是還有一些case沒想到方法
推 HigherKuo:我想到的是，多用一個pointer指到parents。
→ bnsblue:可是那樣的memory overhead算是不小 尤其是10^5 nodes以上
→ bnsblue:不過我也不知道該選擇速度還是空間比較好
推 HigherKuo:嗯，先做出來卡要緊！ XD
→ bnsblue:說得好XD
推 timrau:如果堅持要省下那個parent又想要快的話 請參考
→ timrau:"Threaded binary tree". 不過要把這東西寫對嘛......
→ timrau:反正已經有code可看了，Wikipedia的第一個reference就是XD
→ bnsblue:也是蠻長的XD
推 timrau:C code都寫好放那邊了，OK的啦 XD
推 Archezoa:可是還要記錄threaded 我覺得可能變快  但不會省得樣子
→ bnsblue:有要多用ptr嗎?不是直接用leaves的左右子樹去指就好?
推 timrau:threaded可以偷用pointer的最後2 bits....
推 Archezoa:哈～  那還真是蠻麻煩的