二叉树的随机生成及其遍历
张zhaohan 10804XXXXX
2010/6/12
问题重述
利用随机函数产生50个(不大于100且各不相同的)随机整数，用这些整数来生成一棵二叉树，分别对二叉树进行先根遍历，中根遍历和后根遍历并输出树中结点元素序列。
程序设计
(一)需求分析：
●问题的定义与要求：1、产生50个不大于100且各不相同的随机整数（由系统的随机函数生成并对100取模）；2、先根遍历并输出结果；3、中根遍历并输出结果；4、后根遍历并输出结果；5、按层次浏览二叉树结点；6、退出程序。
●输入：所需功能，选项为1～6。
●输出：按照用户功能选择输出结果。
●限制：输入的功能选择在1～6之间，否则无回应。
●模块功能及要求：
RandDif()：生成50个随机不大于100的整数，每次生成不同随机整数。
CreateBitree()：给数据结点生成二叉树，使每个结点的左右儿子指针指向左右儿子。NRPreOrder()：非递归算法的先根遍历。
inOrderTraverse()：递归算法的中根遍历。
PostOrderTraverse()：递归算法的后根遍历。
Welcome()：欢迎窗口。
Menu()：菜单。
Goodbye()：再见窗口。
(二)概要设计：
首先要生成二叉树，由于是对随机生成的50个数生成二叉树，故可以采取顺序存储的方式，对结点的左右儿子进行赋值。生成的二叉树是完全二叉树。
先根遍历的非递归算法：
1、根结点进栈
2、结点出栈，被访问
3、结点的右、左儿子（非空）进栈
4、反复执行2、3 ，至栈空为止。
先根遍历的算法流程图：
根结点进栈（a[0]=T->boot,p=a[0]）
访问结点printf(*p)
右儿子存在则进栈a[i]=(*p).rchild; i++;
左儿子存在则进栈a[i]=(*p).rchild; i++;
栈顶降低top--：i--;p=a[i];
栈非空while(i>-1)
返回
中根遍历的递归算法流程图：
T为空
Y
N
Return;
inOrderTraverse(T->lchild)
Printf(T->data)
inOrderTraverse(T->rchild)
返回
后根遍历的递归算法流程图：
T为空
Y
N
Return;
inOrderTraverse(T->lchild)
inOrderTraverse(T->rchild)
Printf(T->data)
返回
遍历输出均按链式存储。链式存储的特点是借助指示元素存储地址的指针（pointer）表示数组元素之间的逻辑关系。
按层次查看二叉树元素则按下标顺序直接输出。同时，生成随机数、生成二叉树均是按顺序存储。顺序存储的特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。
二叉树中序遍历非递归算法(三)详细设计
程序源代码设计：
（1）定义结点：
struct data
{
int n;
struct data *lchild;
struct data *rchild;
}data[N];
（2）产生随机数
RandDif(struct data data[])
int i,j;
srand((int)time(0));
for(i=0;i<N;i++)
{
data[i].n=rand()%100;
for(j=i-1;j>1;j--)if(data[i].n==data[j].n||data[i].n==0){i--;j=0;} }
}
（3）生成二叉树
CreateBitree(struct data data[])
int i;
for(i=0;i<25;i++)
data[i].lchild=&data[2*i+1];
data[i].rchild=&data[2*i+2];
}
printf("\nSuccessfully create a Binary Tree.\n");
printf("The Binary Tree has 50 different element.");
}
（4）先根遍历的非递归算法
NRPreOrder(struct data data[])
int i=0;
struct data *a[N],*p=&data[0];
while(i>-1)
{
printf("%-4d",(*p).n);
if((*(*p).rchild).n)
a[i]=(*p).rchild;
i++;
}
if((*(*p).lchild).n)
a[i]=(*p).lchild;
i++;
}
i--;p=a[i];/ }}
（5）先根遍历的递归算法PreOrderTraverse(struct data data) if(data.n)
{
printf("%-4d",data.n);
PreOrderTraverse(*(data.lchild));
PreOrderTraverse(*(hild));
}
}
（6）中根遍历的递归算法inOrderTraverse(struct data data) {
if(data.n)
{
inOrderTraverse(*(data.lchild));
printf("%-4d",data.n);
inOrderTraverse(*(hild));
}
}
（7）后根遍历的递归算法
PostOrderTraverse(struct data data)

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。