※ 引述《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)