叉树的随机生成及其遍历张 zhaohan 10804XXXXX2010/6/12问题重述利用随机函数产生50个(不大于1 00且各不相同的)随机整数，用这些整数来生成一棵二叉树，分别对二叉树进行先根遍历，中根遍历和后根遍历并输出树中结点元素序列。

程序设计(一) 需求分析：•问题的定义与要求： 1 、产生50个不大于100且各不相同的随机整数 (由系统的随机函数生成并对100取模)；2、先根遍历并输出结果；3、中根遍历并输出结果；4、后根遍历并输出结果；按层次浏览二叉树结5、点；6、退出程序。

•俞入：所需功能，选项为1〜6。

•输出：按照用户功能选择输出结果。

•限制：输入的功能选择在1〜6之间，否则无回应。

•模块功能及要求：RandDif(): 生成50个随机不大于100的整数，每次生成不同随机整数。

CreateBitree(): 给数据结点生成二叉树，使每个结点的左右儿子指针指向左右儿子。

NRPreOrder(): 非递归算法的先根遍历。

inOrderTraverse(): 递归算法的中根遍历。

P ostOrderTraverseO：递归算法的后根遍历。

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为空Return;inOrderTraverse(T->lchild)Printf(T->data) inOrderTraverse(T->rchild)返回后根遍历的递归算法流程图：T为空Return;inOrderTraverse(T->lchild) inOrderTraverse(T->rchild)Printf(T->data)返回遍历输出均按链式存储。

链式存储的特点是借助指示元素存储地址的指针（数组元素之间的逻辑poin ter)表示关系。

按层次查看二叉树元素则按下标顺序直接输出。

同时，生成随机数、生成二叉树均是按顺序存储。

顺序存储的特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。

（三）详细设计程序源代码设计：1）定义结点：struct dataint 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(*(data.rchild));6)中根遍历的递归算法inOrderTraverse(struct data data) if(data.n)inOrderTraverse(*(data.lchild));printf("%-4d",data.n);inOrderTraverse(*(data.rchild));7）后根遍历的递归算法PostOrderTraverse(struct data data)if(data.n)PostOrderTraverse(*(data.lchild)); PostOrderTraverse(*(data.rchild)); printf("%-4d",data.n);（四 ） 测试结果：由于先、中、后根遍历递归算法类似，故此处,选择中根遍历递归算法进行测试：如某次生成的 50个数为： 28 96 97 60 43 65 90 70 11 91 6 4 37 44 94 81 56 63 14 28 73 67 64 1345 75 88 57 77 86 55 69 23 98 31 85 8 12 87 9 51 93 3 40 18 17 72 21 10 58而生成的二叉树为：289669 23 98 31 85 8 12 87 9 51 93 3 40 18 17 72 21图：二叉树中根遍历结果为： 69 81 23 70 98 56 31 60 85 63 8 11 12 14 87 96 9 28 51 91 93 73 3 43 40 67 186 17 64 72 28 21 13 10 4 58 45 65 75 37 88 97 57 44 77 90 86 94 55而程序中根遍历结果为： 69 81 23 70 98 56 31 60 85 63 8 11 12 14 87 96 9 28 51 91 93 73 3 43 4067 18 6 17 64 72 28 21 13 10 4 58 45 65 75 37 88 97 57 44 77 90 86 94 55完全符合，递归算法测试完毕。

验证先根遍历的非归算法：9760 43 65 9070 11 91 37 44 9481 56 63 1428 73 67 64 13 45 75 88 57 77 86 5510 58在main()中加入先根递归算法和非递归算法作结果比较。

由于递归算法已经验证，故此处 只须非递归算法和递归算法结果符合即可。

生成 50个数：1 12 38 79 72 86 13 4 11 7 58 75 88 6 3 82 50 57 61 91 92 14 28 68 46 99 30 25 2024 85 63 5 39 9 49 60 31 90 96 76 36 98 83 27 84 22 56 21 87递归算法的先根遍历结果： 1 12 79 4 82 63 5 50 39 9 11 57 49 60 64 31 90 72 7 91 96 76 92 3698 58 14 83 27 28 84 22 38 86 75 68 56 21 46 87 88 99 30 13 6 25 20 3 24 85非递归算法的先根遍历结果： 1 12 79 4 82 63 5 50 39 9 11 57 49 60 64 31 90 72 7 91 96 76 9236 98 58 14 83 27 28 84 22 38 86 75 68 56 21 46 87 88 99 30 13 6 25 20 3 24 85在生成 50个随机不同整数的过程中遇到了几次问题，如循环条件差一个数，就会导致生成 数中有几个数是相同的，此时就需要修改循环条件；数据要排除 0。

函数的参数传递存在一定误区，有几次传递参数不当，格式不符，导致不能得到结果，在 认清了函数参数传递的要求后问题得以解决。

调试的时候为发现各个细节问题，会在各个模块的容易出问题的过程加输出函数，就便于 发现问题所在。

易知生成随机数的时间复杂度为，生成二叉树的时间复杂度为0(n)，递归遍历的时间复杂度均为0(n),而非递归先根遍历的时间复杂度也为附： 完整程序代码：/* 利用随机函数产生 50个(不大于 100且各不相同的 )随机整数，用这些整数来生成一棵二树，分 别对二叉树进行先根遍历，中根遍历和后根列遍历输出树中结点元素序列。

先根遍历输出要求 采用非递归来实现。

struct data{int n;struct data *lchild; struct data *rchild; }data[N]; /* 定义数组元素 */O(n)。

#include <stdio.h> #include <stdlib.h> #include <time.h> #include <conio.h> #define N 50 #define NULL 0i++;void RandDif( struct data data[]) {/* 生成个互不相同的随机整数 */ int i,j;srand(( int )time(0)); /* 每次生成不同的随机数 */ for (i=0;i<N;i++) data[i].n=rand()%100; if (data[i].n==data[j].n||data[i].n==0){i--;j=0;}void 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." });void 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;for (j=i-1;j>-1;j--){/*void PreOrderTraverse( struct {/* 先根遍历输出，递归算法*/ data data)if(data.n)printf( "%-4d" ,data.n);PreOrderTraverse(*(data.lchild)) ; /* 先根遍历右子树*/PreOrderTraverse(*(data.rchild)) ; /* 先根遍历左子树*/void inOrderTraverse( struct {/* 中跟遍历输出，递归算法*/ data data)if (data.n)inOrderTraverse(*(data.lchild) ); /* 中跟遍历左子树*/printf( "%-4d" ,data.n);inOrderTraverse(*(data.rchild) ); /* 中跟遍历右子树*/void PostOrderTraverse( struct {/* 后根遍历输出，递归算法*/ data data)if (data.n)PostOrderTraverse(*(data.lchild)) ; /* 后根遍历左子树*/PostOrderTraverse(*(data.rchild)) ; /* 后根遍历右子树*/printf( "%-4d" ,data.n);void Welcome(){/* 欢迎窗口*/ printf( "\n\n Welcome use Traverse Binary Tree\n\n" );printf ( "\n\n\n\n" );printf ( "\n" );printf ( Specialty:Information and Computational Science Program\n" );printf ( Class:2 Grade:2 No.:200530760214 Name:Lin Weiyang\n" );printf ( Press any key tocontinue...\n");getch(); void Menu() {/* 菜单 */printf( ***************************************************************\n" ); printf ( ** Please select the function you need: **\n" ); printf ( ** 1.Create another tree. **\n" ); printf ( ** 2.Preorder traverse the Binary Tree. **\n" ); printf ( ** 3.Inorder traverse the Binary Tree. **\n" ); printf ( ** 4.Postorder traverse the Binary Tree. **\n" ); printf ( ** 5.Display the Binary Tree. **\n" ); printf ( ** 6.Exit . **\n " ); printf ( ***************************************************************\n" );void Goodbye(){/* 再见窗口*/printf( "\n" ); printf( "\n" );printf( II TTT TTT TT TT TT TT TT TT TT TTT T \n" printf( II TT TT TT TTTT TT TT TT TT TT TT \n" printf( II TT TT TT TT TT TTT TT TT TT TT \n" printf( II TT TT TT TT TT TTTT TT TT TT TT \n"printf( II TT TTTTTT TT TT TT TTTT TTTT TT \n printf( II TT TT TT TTTTTT TT TTT TT TT TT \n" printf( II TT TT TT TT TT TT TT TT TT TT \n" printf( II TT TT TT TT TT TT TT TT TT TT TT \n" printf( II TT TT TT TT TT TT TT TT TT TTTT \n"printf( "\n" );printf( "\n" );printf( II Copyright 2010 ZhangZhaohan\n"printf( IIPress any key to exit...\n"getch();} } );void main() int i; Welcome(); Loop: ); ); ); ); );); );); ); );clrscr();Menu();switch (getchO)getch(); goto Loop; break ;case '6' :; break;default : goto Loop;} clrscr();Goodbye();可执行文件: 程序运行截图: s« l#c ( 1_屛 f unc< 111 It ytkii next :1 .CrRntn nnntlmp tnta . ** Z.Frconlci' trauerse the Sin^rv Time. ** 3. Inoirdep tp-avei*se thnBinary Trsa “4.Pbctdhriai* tlw Binary 1 .** the Ri'Trrn , P PASE dou key ta cont iniie...运行窗口: 先根遍历case '1' :RandDif(data);CreateBitree(data); printf( "\n\nP ress any key to continue...'"' ); getch(); goto Loop; break;case '2' :p rintf( "The Preorder traverse of the Binary Tree is:\n" );NRP reOrder(data); printf( "\n\ nP ress any key to continue...\n" );getch(); goto Loop; break ;case 3 :printf( "The Inorder traverse of the Binary Tree is:\n" );inOrderTraverse(data[0]) ;p rintf( "\n\nP ress any key to continue...\n" );getch(); goto Loop; break ;case '4' :printf( "The Postorder traverse of the Binary Tree is:\n" );PostOrderTraverse(data[0]) ;p rintf( "\n\nP ress any key to continue...\n" ); getch(); goto Loop; break ;case '5' :printf( "The element of the Binary Tree are:\n" );for (i=0;iv50;i++)printf( "%-4d" ,data[i].n);printf( "\n\nP ress any key to continue...\n" ); h4 9 1 IhpLS FmoMie> ti'dive^t 39 24 37? 41 G1 44 马韶 9U 3 SH Hi 5b $V ira C9 u 1 tv? F Binaryin： 2a 32 ~~G9 53 75 51 79 ZG 艸 归 5S日3 砧 a4. 9 t。