树的同构(树的同构)

一、二叉树怎么判断同构

最优做法是hash+最小表示法，大致思路就是试着把二叉树用hash值表示出来。对整棵树进行后序遍历，将一个节点的左右子树hash值都求出之后，保证左子树的哈希值恒小于右子树，否则就交换左右子树，然后算该子树的hash值。最后比对根节点hash值即可。

该算法的时间复杂度为稳定的O(N)，如果选的hash函数不太慢的话(事实上这题适用的hash可以非常快)。为了严谨性应对hash进行防冲突操作，比如开闭散列，但是仍然不会影响复杂度。额外空间复杂度考虑后序遍历的特性对hash存储进行优化，可以达到O(depth)，但是最坏情况下也是O(N)级别的。

再来说说vczh的答案。他的做法没有错，可以得到正确的解，问题是树较接近满二叉树的时候复杂度会变得很高。在最坏的满二叉树的状况下，每个叶子节点会被访问2的logn次方也就是n次，再加上一共有n/2个叶子节点，那么总复杂度可以达到平方级别。接近满二叉树的大部分情况的复杂度，也是近似如此。也许有人会认为这只是个别极端情况，但是同样只在个别极端情况下会退化的非随机快排，也被认为是不够优秀的，想必没有哪个标准库的快排会在极端条件下退化成平方复杂度吧。

在vczh底下评论的vani是我的大学同学，高中时的全国信息学竞赛银牌，国家集训队，大学时acm区域赛金牌拿到手软，还拿到了world final的金牌第三名。平心而论，若要说算法和数据结构题，全国甚至全世界想要找几个能碾压他的人也不是那么容易的。所以看到很多人试图用"轮子哥你也有资格质疑"的态度还是觉得挺有趣的。

二、求解释非同构根树与非同构树

非同构根树（Nonisomorphic Rooted Trees）和非同构树（Nonisomorphic Trees）是两个不同的概念。

非同构根树是指两个根树（Rooted Trees）之间没有相同的子树结构，即使它们具有相同的节点数和边数。换句话说，非同构根树是指两个根树之间没有相同的子树结构，即使它们看起来非常相似。

非同构树是指两个树之间没有相同的子树结构，即使它们具有相同的节点数和边数。换句话说，非同构树是指两个树之间没有相同的子树结构，即使它们看起来非常相似。

因此，非同构根树是非同构树的一种特殊情况，即两个根树之间没有相同的子树结构。

三、树的同构问题(树的最小表示法)

所谓的同构数就是一个数是它的平方的右侧。例如5的平方25，25的平方625，诸如此类，所以5、25都是同构数。比如问1-10000里有多少个同构数。我给你看两个相对简单好理解的代码~~~#include<stdio.h>

#include<stdlib.h>

int Test(int a, int b)

{

while(a!= 0)

{

if(a%10!= b%10)

return 0;

a/= 10;

b/= 10;

}

return 1;

}

void main(void)

{

int i;

for(i= 0; i< 10000;++i)

{

if(Test(i, i*i))

printf("%d-%d\n", i, i*i);

}

system("pause");

}算法原理是

将个位取出来比较如果不等那肯定不是

如果相等了则除以10那么百位就变成个位了

重复上述步骤知道小的数位0那么比较就完成了#include<stdio.h>

int check(int org, int sqr)

{

int tmp, rhs, fac;

tmp= org;

rhs= 0;

fac= 1;

while(tmp> 0){

rhs+= sqr% 10* fac;

fac*= 10;

tmp/= 10;

sqr/= 10;

}

return rhs== org;

}

int main()

{

int i, c;

for(c= 0, i= 1; i<= 10000;++i){

if(check(i, i*i))

printf("No.%d%d->%d\n",++c, i, i*i);

}

return 0;

}献丑啦~~~你自己先看起吧~~~~