[求助]如何建一个随机的二叉树?
我是想做一个二叉树的测试系统的,要随机产生一个二叉树枝,结点数也是随机的,但是我自已做的就总是产生一叉的,所以请各位师兄或师姐. 你说的节点数随机， 是指总结点数吗？还有，既是二叉树， 那么按定义每个Node都有两个后代了， 你的随机的意思是不是，每个Node可能是2,1 个后代或无后代（叶）？
如果是的话， 用一个随机函数（ｒａｎｄ），来决定每个Ｎｏｄｅ可以有几个后代就行了
比如说， 决定要不要左Ｃｈｉｌｄ时， 产生个随即数（０～１），与０．５ 比较大小（因为是５０％的机会） 结点数是随机的可以是0个结点,1个或多个,
结点的性质也是随机的,结点是可以(有左孩子或有右孩子或左右均有或为空) 可能是你的随机函数的问题，用时间做种子试试 恩， 那就好象对了。。。
我想应该有两个Step：
1 －先确定整个树的大小 ， 即总节点个数 （可以随机产生， 也可以User Input:)）， 当后面算法里随机Create的节点数达到了这个数 就停
2－ 用一个标准的递归( Depth-first 或 Width-first 都行）来创节点
For Example(Depth-first) :
2.1 create 根节点
2.2 [决定是否创左Child] - if yes
--create 左Child 节点
-- 递归进左Child........
2.3 [决定是否创右Child] -ifyes
-- create右Child
--递归进右child ........
当然， 终止条件就是达到总节点数 :-)
一般在[决定是否创XChild] 那一步， 就用我前面说的那个Rand来决定Yes/No。
这样生成的应该是个比较均匀的了把。。。。。。。
＝＝＝＝＝＝＝＝＝＝
还有个更均匀点的方法， 即认为 【无后代】【只有左child】【只有右Child】【左右都有】出现的几率都相等 （ 即25%）， 那么就先随机决定当前Node 是哪种情况， 然后再创Child(或不用创)， 再递归。。 Status CreateRandBiTree(BiTree &t)
{
TElemType e;
BiTree tmp;
srand(time(0)) ;//初始化随机种子。
int m=rand()%(100);
if(m<50&&k<26)
{
srand(time(0)) ;//初始化随机种子
e=(char)(k+96);
if(!(tmp=(BiTNode *)malloc(sizeof(BiTNode)))) exit(OVERFLOW);
tmp->data=e;
t=tmp;
printf("t=[%X] ",t);
printf("t->data=%c \n",t->data);
CreateRandBiTree(t->lchild);
t->lchild=NULL;
k++;
CreateRandBiTree(t->rchild);
t->rchild=NULL;
}
else
t=NULL;
return OK;
}
以上就是我创建的方法啊,可是每次的m值都是一样的,如果是30,接下来的所有m都是30啊,所以只能创建一条链下去啊
页:
[1]