Question

高分悬赏！！数据结构问题。判定二叉树等。

要算法及简要的算法思想，把答案发我邮箱里，否则不给悬赏分。
1.判定一棵二叉树是否是Huffmann树
2.判断一个有向图是否是强联通的。
3.两路归并排序可以在原地完成吗？(这题只要设计思想)
邮箱330806931@qq.com

回答好的再追加100分！！！

Answer 1

1. 对这个树遍历的同时进行两项检查
a. 每个结点有0个或2个子结点
b. 如果有2个子节点 则子结点的值之和等于该结点的值

2. 可以考虑BFS算法的变种应用 从某结点开始 应用BFS算法 只是这次不再对每个结点进行“以访问”标记 而是在每个结点里记录该结点的祖先信息（就是父结点 爷爷结点等等） 访问下一个结点的时候不访问除了根以外的祖先结点

例如 访问A结点 （A结点可以到达B结点） 然后访问B结点 （B结点可以到达A C 结点） 由于A结点是B结点的祖先结点 所以只访问C结点
但是如果A结点是根的话 B结点就要访问 A C结点
依次类推
每个分支一直发展到没有结点可以访问或者访问到根结点 结束

寻找所有从根结点到根结点的分支 如果这些分支中所含的结点的并集等于图的所有结点 那么这个图就是强联通图

说的有些乱 不知道你能不能看明白

3. 这个原地完成我也没太明白
原来是 A + B = C
现在给改成 A + B = A 就是了
也就是依次把B插入A中对应的位置就是了 比较还是跟原来的归并一样

Answer 2

1. 不清楚这个怎么定义huffman树， 也许可以用所有叶节点自己做个huffman树， 比较一下是不是每一层的节点分别相同（顺序可以不同）

2. 判断强联通一般就是找一个包含所有节点的环。 从一个点出发找路径， 如果出现环（未必是到出发点的，也许是在中间有一段环）， 就把环里的所有顶点归并成一个点， 整理一下路径表，然后继续找， 直到所有顶点归并成一个为止。如果部分顶点归并到没出度了那就是非强联通了

3. 想不到什么办法可以原地归并。 除非是这东西本身很大的话， 用链表归并当然就可以原地了。 不过如果排序的东西本身就是个int之类的， 多个指针就等于多一倍空间开销，这个原地就比较无聊了