※ 引述《FATCLOUD (A Cloud)》之銘言： : 聽說教授寫的 BSTreeNode 裡面沒有 _parent 這個成員 : 剛剛在寫我也試著寫不要用 _parent 的 BSTree : 可是在寫到 iterator 的 ++ overloading 時 : 遇到了一個問題 : 那就是在 iterator 這個 class 裡 : 我不能直接呼叫 _root 這種東西 : 因為在一個程式裡 : 我們可以宣告很多個 BSTree : 而通常一個 iterator 指向的 BSTreeNode 並不知道自己屬於那一棵 Tree : 所以如果我沒頭沒腦的就叫程式從 _root 開始尋找某個 Node 的 Parent : 那馬上就會面臨一個問題就是 : 每棵樹都有一個 _root : 不知道要找哪棵樹才對 : 我很好奇老師是怎麼跨越這個問題的 : 或者是有其他的同學不用 _parent 就做出了 iterator ++ 可以代為解說嗎? @@ 簡單的說明一下, 但是我這樣的作法是有點 tricky, 你如果已有你自己的作法, 其實真的可以不用參考我的. 首先, 我的 BSTree::iterator 裡存了一個 trace, 記錄這個 iterator 目前到此為止 走過的 trace, 而所謂的 trace, 就是 (node, left/right)... 的 sequence. 至於細節, 恕不奉告 (也許下次上課 (不是明天) 再跟大家分享). 一些需要考慮的因素: 1. 這個 _trace data member 是個 object, 不是 pointer, 所以每個 iterator 會有自己的 _trace. 2. 當 iterator copy 的時候 (如 lj = li, 或是 li++), trace 也會 copy 過去. destructor 當然也會自動將 trace 清掉 (i.e. call its destructor). 3. 那 trace 的頭是什麼? 就是 iterator(n) 的那個 n, 在我的 implementation 裡, 他只會是 _root (因為其他的 node is not accessible to the users). 4. ++/-- 不只是要 push/pop 一個 trace, 還要考慮 往上走在往下走的情形, 不過有 _trace 的話這個還蠻簡單的, 大家可以想想看. 5. 走到底的話, ++/-- 就不要走了. 大概就這樣. --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.224.43.127 ※ 編輯: ric2k1 來自: 61.224.43.127 (05/21 21:42)