[求助]如何建一个随机的二叉树?

bobows

我是想做一个二叉树的测试系统的,要随机产生一个二叉树枝,结点数也是随机的,但是我自已做的就总是产生一叉的,所以请各位师兄或师姐.

chosenone

你说的节点数随机， 是指总结点数吗？

还有，既是二叉树， 那么按定义每个Node都有两个后代了， 你的随机的意思是不是，  每个Node可能是2,1 个后代或无后代（叶）？　

如果是的话，　用一个随机函数（ｒａｎｄ），来决定每个Ｎｏｄｅ可以有几个后代就行了　

比如说，　决定要不要左Ｃｈｉｌｄ时，　产生个随即数（０～１），与０．５　比较大小（因为是５０％的机会）

bobows

结点数是随机的可以是0个结点,1个或多个,
结点的性质也是随机的,结点是可以(有左孩子或有右孩子或左右均有或为空)

hjack

可能是你的随机函数的问题，用时间做种子试试

chosenone

恩， 那就好象对了。。。

我想应该有两个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] -  if  yes
                                                   --   create  右Child
                                                    --  递归进右child ........

当然， 终止条件就是达到总节点数 :-)

一般在[决定是否创XChild] 那一步， 就用我前面说的那个Rand来决定Yes/No。

这样生成的应该是个比较均匀的了把。。。。。。。
＝＝＝＝＝＝＝＝＝＝

还有个更均匀点的方法， 即认为   【无后代】【只有左child】【只有右Child】【左右都有】  出现的几率都相等 （ 即25%）， 那么就先随机决定当前Node 是哪种情况， 然后再创Child(或不用创)， 再递归。。

bobows

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啊,所以只能创建一条链下去啊