主题：[讨论]怎么比较两个二叉搜索树是否相等？
realcrane
[专家分：190] 发布于 2006-10-16 16:50:00
如题
回复列表 （共7个回复）
沙发
argentmoon [专家分：13260] 发布于 2006-10-16 21:18:00
前序遍历相等，中序遍历也相等。
同构的话就得考虑镜像同构了。
板凳
realcrane [专家分：190] 发布于 2006-10-17 11:21:00
这样的话就要首先弄清楚两个树的前序和中序。如果输入是两组数量相同的任意数组，请问有没有办法在不构造树的情况下判别？
3 楼
xieyong456 [专家分：2620] 发布于 2006-10-17 14:39:00
我觉得对两棵树都线索化,然后直接都找各自的后继,如果都相同就相同了啊
/*数组吗，其实都触类旁通类
数组吗，先排序然后一一比较,不过效率低了点*/
哦,可能我没能理解你所说的数组的含义,感念太模糊了，不理解~
还有线索化的话,当然要同一个顺序线索化，否则再一个很凑巧的情况下也会相同
没有用代码证实过，也只是一个想法而已
4 楼
realcrane [专家分：190] 发布于 2006-10-17 14:47:00
是我说的不够清楚。就是如果给你两个数的序列，每个序列拥有相同的元素。那么在不构建树的情况下，能不能判断两个序列的数分别构成的二叉搜索树是否相同？例如：
/*要求输入随机的两个数组，它们拥有相同个数的元素
当两个数组分别构成的二叉搜索树相同，返回true；否则，返回false*/
bool TreeEqual(int a[], int b[], int size)
{
}
就是问这个函数在不对a和b两个数组构建树的前提下，能不能判断如果把他们分别构建成一个二叉搜索树的话，这两颗树是否相同？（说的有点绕口，其实就是没有树的时候能不能判断如果有树的话，两颗树是否相同。。。郁闷了。。。）
5 楼
xieyong456 [专家分：2620] 发布于 2006-10-17 14:59:00
恩，我想我已经理解了你的意思
不构造树的情况下判别两棵树是否相同
你难道没觉得你这句话已经矛盾了吗?
请问没有构造树那里来的树相等
其实你只是觉得麻烦，所以想入非非..."懒"人有"懒"法
但是我觉得树是一个形态
不管是先序,中序还是后序都会造成树的变化,所以还是要构造一棵数才能来判断
比如你要判断一组数是否相同,有必要申请一个数组,再来一一比较如此而已
6 楼
realcrane [专家分：190] 发布于 2006-10-17 15:04:00
呵呵。我也觉得这个东西本身就是有矛盾的。别人给我这个题的时候，我也是用上述的方法作的。后来他就说你找前序中序的，就等于已经构建了树。能不能有一种方法在不构建的情况下“预判”。所以我想，是不是有什么深层的数学方法可以“预判”，而我不知道。
7 楼
xieyong456 [专家分：2620] 发布于 2006-10-17 15:08:00
恩，你说的也不是没有道理
再你预知一棵树的先序,后序的前提的下,再用数学方法来解决也不是为一个“懒”
的好方法,应该可以实现,其实过程并不是死的，只要结果一样都是方法
呵呵，那我想 这个不就是直接判断了啊,你是不是也再为如何给出这个问题所困惑啊~
可能我是一直从要遍历的角度去考虑这个问题了，所以思想被定格了~
[em19]
我来回复
您所在位置：