[求助]随机生成n个结点二叉树的算法

[复制链接]

淡淡的烟草味

电梯直达

1^#

发表于 2009-11-3 01:25:15 | 只看该作者回帖奖励

|倒序浏览 |阅读模式

片段如下：
struct BiTNode
{
int data;
BiTNode *left;
BiTNode *right;
};
BiTNode *Tree; //根指针
cin<<i;
srand(i); //指定随机数种子，相同的种子将产生相同的数据序列
rand();
BiTNode *Generate(int n) //n为树的结点数
{
if (n==0)
return NULL;
BiTNode *P = new BiTNode;
P->data = rand() % 999 + 1 ;//为什么要加1 ？
int nl=rand() % (n);
P->left = Generate(nl);
P->right = Generate(n-1-nl);
return P;
}
搞不懂递归何时退出？关键是Generate(n-1-nl)是什么意思……死活不懂，望高手灌顶！

收藏0

使用道具举报

isly‖

2^#

发表于 2009-11-3 01:25:18 | 只看该作者

P->data = rand() % 999 + 1 ;//为什么要加1 ？
保证生成的数在1-999之间.这个可能是题目的要求.
int nl=rand() % (n); //保证左子树个数不会超过总结点数.
P->left = Generate(nl);//左子树的结点个数
P->right = Generate(n-1-nl);//右子树结点个数当然是n-n1-1(其中1是根嘛)

递归退出就是在
if (n==0)
return NULL;