一道数据结构及算法设计题，请高手们进来讨论一下？
对于一个树的集合，给出一种数据结构，通过这种结构可以使查询（给定一棵树，从树的集合中找完全匹配的树）操作的执行速度最快，请说明如下内容：
1）给出结构的说明；
2）构造算法和查询算法的说明和代码；
3）查询算法的复杂性分析。
树的结点的数据类型为：
typedef struct tree_node{
int data;
struct treenode *lchild, *rchild;
}treenode;
问题点数：100、回复次数：15Top
1 楼g20044111（虚心向学）回复于 2005-12-31 12:00:35 得分 5
二叉树中还有类似模式匹配的东东啊```
关注````学习`````Top
2 楼Zephyrzzz（）回复于 2005-12-31 15:37:11 得分 10
将这棵树用最小表示法（或别的方法）转换成一个字符串再进行匹配。Top
3 楼txj_killer（流浪的天行）回复于 2006-01-02 17:18:08 得分 20
对整棵树做一次hash就行了,hash函数可以根据每个节点的值,节点高度等数据进行计算,尽量保证一致性,这样建立hash表或者用指向root的链表存储树和hash值都可以实现很高效的查找,唯一缺点是insert操作复杂度为O(n)--设插入的树节点数为n.Top
4 楼ggyz（小虫）回复于 2006-01-03 21:00:04 得分 0
郁闷，这几天网络故障。
txj_killer，是在树的集合中查找树，不是在树里查找结点。Top
5 楼txj_killer（流浪的天行）回复于 2006-01-03 22:46:25 得分 5
当然是查找树，对整个树建立hash难道能查找节点么。。。Top
6 楼ggyz（小虫）回复于 2006-01-03 23:54:28 得分 0
稍等，我研究一下，明天再向你请教^_^Top
7 楼ggyz（小虫）回复于 2006-01-05 19:17:31 得分 0
从题目来看，“通过这种结构可以使查询操作的执行速度最快”，好象是要用散列表。不过有个问题，当找到之后进行确认的代价似乎也不小吧。txj_killer能否给出个供参考的散列函数？
我的想法是这样，构造函数把树同时前序和中序周游一下，由这两个序列作为关键码，计算出一个散列值。但这个关键码似乎比较复杂。Top
8 楼boblaile（爱在13月32）回复于 2006-01-05 19:42:02 得分 5
完全匹配的树
是不是看遍历的结果呢1Top
9 楼txj_killer（流浪的天行）回复于 2006-01-07 16:54:51 得分 20
最简单的散列函数就是对每个节点的高度和节点值算出一个数，然后通过遍历对每个算出的值异或。
因为要反映整棵树的信息，遍历是必须的，这将造成insert操作复杂度增加，但是查找时却有非常大的效率提升。通过溢出链表处理碰撞的话，如果hash值只对应一棵树，查找时甚至不用遍历，复杂度为O(1)，而且只要hash函数适当，通常每个hash值对应节点不会超过两个，这样整个查找操作的分摊复杂度可以降到非常低的水平。Top
10 楼wvins（逸岚）回复于 2006-01-07 17:33:37 得分 5
mark
Top
11 楼daipeanut（满天星I'mwaitingforyourcoming with a sincere heart）回复于 2006-01-12 10:05:58 得分 5
UPTop
12 楼jack1219（jack）回复于 2006-01-14 00:46:45 得分 5
upTop
13 楼huang_ball（黄求）回复于 2006-01-14 08:22:41 得分 5
UP
Top
14 楼iamltd（妖）回复于 2006-01-19 14:16:28 得分 10
觉得ggyz(小虫)的办法比较好
毕竟前序和总序序列已经可以确定整个树了,以这两个序列来构建hash,应该能达到要求.Top
15 楼programfanny（）回复于 2006-01-20 19:55:15 得分 5
关注````Top
