一道数据结构及算法设计题，请高手们进来讨论一下？

对于一个树的集合，给出一种数据结构，通过这种结构可以使查询（给定一棵树，从树的集合中找完全匹配的树）操作的执行速度最快，请说明如下内容：
1）给出结构的说明；
2）构造算法和查询算法的说明和代码；
3）查询算法的复杂性分析。
树的结点的数据类型为：
typedef struct tree_node{
int data;
struct treenode *lchild, *rchild;
}treenode;

15 个解决方案

#1

二叉树中还有类似模式匹配的东东啊```
关注````学习`````

#2

将这棵树用最小表示法（或别的方法）转换成一个字符串再进行匹配。

#3

对整棵树做一次hash就行了,hash函数可以根据每个节点的值,节点高度等数据进行计算,尽量保证一致性,这样建立hash表或者用指向root的链表存储树和hash值都可以实现很高效的查找,唯一缺点是insert操作复杂度为O(n)--设插入的树节点数为n.

#4

郁闷，这几天网络故障。
txj_killer，是在树的集合中查找树，不是在树里查找结点。

#5

当然是查找树，对整个树建立hash难道能查找节点么。。。

#6

稍等，我研究一下，明天再向你请教^_^

#7

从题目来看，“通过这种结构可以使查询操作的执行速度最快”，好象是要用散列表。不过有个问题，当找到之后进行确认的代价似乎也不小吧。txj_killer能否给出个供参考的散列函数？

我的想法是这样，构造函数把树同时前序和中序周游一下，由这两个序列作为关键码，计算出一个散列值。但这个关键码似乎比较复杂。

#8

完全匹配的树
是不是看遍历的结果呢1

#9

最简单的散列函数就是对每个节点的高度和节点值算出一个数，然后通过遍历对每个算出的值异或。

因为要反映整棵树的信息，遍历是必须的，这将造成insert操作复杂度增加，但是查找时却有非常大的效率提升。通过溢出链表处理碰撞的话，如果hash值只对应一棵树，查找时甚至不用遍历，复杂度为O(1)，而且只要hash函数适当，通常每个hash值对应节点不会超过两个，这样整个查找操作的分摊复杂度可以降到非常低的水平。

#10

mark

#11

#12

#13

#14

觉得ggyz(小虫)的办法比较好
毕竟前序和总序序列已经可以确定整个树了,以这两个序列来构建hash,应该能达到要求.

#15

关注````

#1