|
以文本方式查看主题 - 中文XML论坛 - 专业的XML技术讨论区 (http://bbs.xml.org.cn/index.asp) -- 『 计算机考研交流 』 (http://bbs.xml.org.cn/list.asp?boardid=67) ---- [讨论]树的变换。 (http://bbs.xml.org.cn/dispbbs.asp?boardid=67&rootid=&id=37436) |
|
-- 作者：DavidPotter -- 发布时间：8/30/2006 5:39:00 PM -- [讨论]树的变换。 我们知道对于一棵树来说，对于任何一个节点可以把它拎起来当成新的树根。 那么对于一棵树来说，给一个节点，用一个算法来得到以这个节点为根的新树。并讨论其复杂性。 树以链式储存。
|
|
-- 作者：DavidPotter -- 发布时间：8/30/2006 5:43:00 PM -- 。。。
|
|
-- 作者：Supremgoooo -- 发布时间：8/30/2006 9:08:00 PM -- 这个不难，就是从根到它的点，即它的直系祖先，变成它的儿子就可以了，其余节点不变。 算法请参考找某个节点祖先的算法（就是后序stack中的了），时间复杂度同后序周游。如果采用父指针表示法，就更简单了。 算法利用的性质是：后序周游stack中保存祖先路径。
|
|
-- 作者：DavidPotter -- 发布时间：8/31/2006 9:51:00 AM -- 对，只是不要用书上那个找父亲的算法就行了。 其实书上那个找父亲的算法可以稍微修改一下找上一个兄弟的算法即可（只要改几行代码），而不要那么复杂了。 |
|
-- 作者：carroty -- 发布时间：8/31/2006 12:45:00 PM -- 我觉得就是从根到所考虑接点的路径都逆转就可以了. 用栈,和回溯? maybe ~ :)
|
|
-- 作者：DavidPotter -- 发布时间：9/1/2006 10:18:00 AM -- 逆转是肯定的，关键问题是如何找到根节点到该节点的路径。 当然可以一步一步的找父节点，直到根。 我觉得按书上那样找父节点肯定太慢了。可以根据其找presibling的模式来找。但是这样好象复杂度也不少。 但是不是太明白 Supremgoooo所说的后序周游。我觉得树的后序周游其实是对应二叉树的中序周游，这时保存的是对应2叉树的根到该节点的路径。而不是树到该节点的路径。 不过我觉得可以这样：如果压栈的时候能够加一个标志位，记录下一步是否是向左走（调用leftMostChild）.那么有标志位的应该是其父节点。还有需要把祖先路径节点的presibling指向它的指针给删除。 |
|
W 3 C h i n a ( since 2003 ) 旗 下 站 点 苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》 |
58.594ms |