资源描述：
《题目 树的历与建立.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、题目:树的遍历与建立院系:计算机学院专业:信息安全学生姓名:王新文学号:22班号:10403201任课教师:李秀坤指导教师报告日期06.4.19计算机科学与技术学院一.需求分析:1.输入形式和输入值的范围以字符串的形式输入(实际是以字符读的).如果用户要输入树:根据先根遍历应该输入ABCD##JK###E#FM###GH##IL###来表示此树.这时程序会递归的调用建立函数,来建立树.对于错误的表示的结果自然不是用户想要的.2.输出的形式通过各种遍历,只按其遍历的顺序打印其内容(看成树的惟一标识),而对最近公共
2、祖先的也打印出共内容.3.程序所能达到的功能树的建立,树的先根递归,中根递归,后根递归,先根非递归,中根非递归,后根非递归,以及层次遍历.求两个结点的最近祖先,,树的删除.4.测试数据以程序提示中的输入为例:输入:ABCD##JK###E#FM###GH##IL####输入1,则得到的结果如图示,正确,同样如选择7.对照,可知,层次遍历正确.如选择8找最近的公共祖先.同样对照可知,K和M的最近公共祖先为B.如果选择9.又回到建树的菜单页面.,如选择0,自然,程序退出一.概要设计typedefcharDataTy
3、pe;//结点属性值类型这里简单起见,只以char为其类型structBTREE//二叉树结点的类型{DataTypedata;BTREE*lchild;BTREE*rchild;};voidCreateBT(BTREE**t);//建树,先根递归voidPreorder(BTREE*t);//先根递归遍历voidPreorder_S(BTREE*t);//先根非递归遍历,堆栈STACKvoidInorder(BTREE*t);//中根,递归遍历voidInorder_S(BTREE*t);//中根非递归遍历,
4、堆栈STACKvoidPostorder(BTREE*t);//后根,递归遍历voidPostorder_S(BTREE*t);//后根非递归遍历,堆栈STACKvoidLevelordor_Q(BTREE*t);//层次遍历,队列QueueBTREE*Find(DataTypedata,BTREE*t);//找到树t中元素为data的结点BTREE*FindNearestParent(DataTypedata1,DataTypedata2,BTREE*t);//找最近的公共祖先,结出两个结点的内容,和树根vo
5、idDelTree(BTREE*tree);//递归实现树的删除建树时,要改变结构指针的内容,因此这里传入了指向结构指针的指针.FindNearestParent(DataTypedata1,DataTypedata2,BTREE*t)函数中调用了,Find()来找到内容为data在树中的位置.DelTree()则是通过递归来实现对树的删除的.主程序的流程:建立树选择操作１，２…，９，０l具体操作，１，２…９，０对应的操作，如，先根递归遍历，…，树的删除和重新建立，退出等。输入为０，退出，一.详细设计 树的
6、遍历，和教材上基本一样。层次遍历用队列实现。刚开始时根结点进入队列： EnQueue(node,tmp);while(IsEmpty(tmp)==false){tree=tmp.front->next->bt;if(tree==NULL){DeQueue(tmp);continue;}if(flag==0)//左儿子没有入队列,入列{node.bt=tree->lchild;node.next=NULL;EnQueue(node,tmp);flag++;//标记,左儿子已经在队列里}elseif(flag==1
7、)//左儿子在队列里,右儿子还没入队列{node.bt=tree->rchild;node.next=NULL;EnQueue(node,tmp);flag++;//右儿子已经在队列里,标记}else{cout<next->bt->data<<"";DeQueue(tmp);flag=0;//左右儿子都在队列里时,父亲出队列,并标记左儿子没有在队列,(下一个)}}}FindNearestParent();找最近的公共祖先：while(1){if(flag==0)//看左儿子是不是公共祖先
8、{tree1=Find(data1,tmp->lchild);tree2=Find(data2,tmp->lchild);if((tree1==NULL)
9、
10、(tree2==NULL))flag=1;//左儿子不是,进右儿子,flag标记else{pubparent=tmp->lchild;tmp=tmp->lchild;//找到了,再看其左儿子是不是}}else//右儿子是不是分公共
