树水平输出.docVIP

数据结构课程 Project 5 树的水平输出 Type：Individual Programmer: Tester: Report Writer: Date of completion:2010/12/24 第一章: 绪论 问题背景描述： 对于给定二叉树，请以水平方向输出二叉树。每个节点包含一个整数值，并且节点数最大255。 节点数据的输出方向为从左到右，从上到下，同一水平高度的节点输出完成后，再输出下一水平高度。 例如，对于如下二叉树： 输出应为5,4,8,11,6,13,9,7,2,12,14,16,18,17,1 节点信息由序列对（n,s）描述，其中整形n表示节点上的整数值，字符串s则表示该节点相对于根节点的位置。例如，上图中整数值为13的节点由序列对（13,RL）描述，整数值为2的节点由序列对（2，LLR）描述。当字符串s为空时，则表示根节点，例如（5，）。当且仅当二叉树上所有节点有唯一的值，称树是完全的（complete）。 基本算法： int main(void) 主函数，调用各子函数 打开输入文件 打开输出文件 构造二叉树 关闭文件 void create_tree() 构造二叉树，构造完毕后送判断函数 void judge_tree() 判断函数，判断二叉树是否有空节点，是否是满二叉树，节点是否有重复值 判断完成后将所有判断标志及二叉树节点数置零，为下一个测试样例做初始化准备 void print_tree() 层序输出二叉树 void destroy() 关闭输入输出文件 第二章: 算法详述 对各数据结构的描述 int BiTree[255] 数组存储二叉树，按层序存储二叉树各节点的数值； char inbuff[bufflen] 字符数组，存储一个节点除‘（’‘）’以外的信息； void create_tree() while(!feof(fp_in)) 当输入文件未结束时继续构造二叉树； while((fgetc(fp_in)!=()!feof(fp_in)){ ; }读入节点信息的‘（’不作处理； if(feof(fp_in)) break 如果文件此时结束则停止构造二叉树； i=1，node=0，pos=0 将各标志和节点数值初始化，为读入节点信息做准备； while(tempin!=)) 将一个节点‘）’之前的信息读入并存储在字符串数组inbuff[bufflen]中， comma=‘，’； if(i1)遇到结束节点‘（）’之前，处理节点信息； inlen=节点信息字符串长度； if(comma==1) if‘，’前无信息，则此节点值为空 then nullnode=1； if(j==1inbuff[1]==- 如果数值为负数，则节点值置为负数； else for(j=comma-1;j0;j--)处理‘，’之前的节点值信息； if(inbuff[j]=0inbuff[j]=9) 将每一位数字字符转换为数值并乘以权重系数，最终得到节点的数值，存储在node中； if(inlen==comma) 逗号后无信息，表明这是根节点，将根节点标志headflag置1，将数值赋给BiTree[0]； else for(j=inlen;jcomma;j--) 根据‘L’‘R’改变pos的值，找到按层序排列时节点的位置，然后将数值赋给BiTree[pos]； if(posTreelen) 用Treelen存储二叉树位置最大的节点的位置； 输入‘（）’时，一个测试样例输入完毕，送判断函数； void judge_tree() if(Treelen==countheadflag!nullnode) 判断节点数是否为0，是否有根节点，是否有空节点； for(i=1;i9;i++)节点数最大255； if(Treelen==(pow(2,i)-2))判断是否为满二叉树； for(j=1;j=Treelen;j++) for(k=0;kj;k++) 判断是否有节点值相等，若有则置same为1，输出“not complete”，若没有则层序输出二叉树，置full为1； 如果二叉树不是满二叉树，则输出“not complete”； 其他情况，都输出“not complete”； 第三章: 测试结果 输入 样例1 样例2 样例3 (11,LL) (7,LLL) (8,R) (5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) () (3,L) (4,R) () (-11,LL) (7,LLL) (8,R) (6,LR)