数据结构实验树5非递归后序先序遍 [复制链接]

这一篇用来补充一些作业中的代码。

Ⅰ先序和后序遍历二叉树的非递归（栈）算法

先序遍历二叉树的栈算法

intPreOrderTraverse(BiTNode*T){initstack(s);//初始化一个栈spush(s,T);visit(T);BiTNode*p=T;while(!stackempty(s)){while(gettop(s,p)p){visit(p);push(s,p-lchild);}//先序走到底，注意，先序访问时visit应该在该循环中pop(s,p);//弹出最后的空指针if(!stackempty(s)){pop(s,p);//说明两次访问完毕，该指针需要被弹出push(s,p-rchild);//向右走一步}}}

与中序算法不同的地方仅在于：visit函数的位置不同

后序遍历二叉树的栈算法

typedefstruct{BTNode*ptr;enum{0,1,2}mark;}PMType;//有mark域的结点指针类型voidPostOrder_Stack(BiTreeT)//后序遍历二叉树的非递归算法,用栈{PMTypea;InitStack(S);//S的元素为PMType类型Push(S,{T,0});//根结点入栈while(!StackEmpty(S)){Pop(S,a);switch(a.mark){case0ush(S,{a.ptr,1});//修改mark域if(a.ptr-lchild)Push(S,{a.ptr-lchild,0});//访问左子树break;case1ush(S,{a.ptr,2});//修改mark域if(a.ptr-rchild)Push(S,{a.ptr-rchild,0});//访问右子树break;case2:visit(a.ptr);//访问结点,返回//未push仅pop，所以会减少stacksize}}//while}//PostOrder_Stack

这个代码我确实想不出来，以上为参考答案，通过switch判断mark标志域，在以左孩子访问时，记标志为1，再次访问到1时说明应该访问右孩子。在开始访问右孩子时，记标志为2，再次访问到2时意味着对该结点的访问已经结束，应该visit。

Ⅱ由后序中序序列求先序层序的递归算法

题目：

7-2树的遍历

给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。

输入第一行给出一个正整数N（≤0），是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。

在一行中输出该树的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。

输入样例：

7

输出样例：

解题思路：

采用递归的思路进行解题，我们很容易观察到该题存在递归结构：

如输入样例，由于后序最后一个输出为根结点，依据这个性质，我们可以将中序再分为左右子树（新的中序：12，后序：21），新的子树又可以找到新的根结点，比较神奇的是，按照先左后右的顺序依次探访，依次保存得到的序列即为先序，为了得到层序，我采用了结构体数组，保存层的信息，有了层的信息，我们可以直接通过排序（可以直接使用STL：sort）就可以得到层序序列。

代码实现

#includeiostream#includealgorithmusingnamespacestd;typedefstructNode{intlevel;//用于保存层的信息intdata;//用于保存数据booloperator(constNoden)const{if(this-leveln.level)returntrue;returnfalse;}//结构体内重载小于运算符，方便sort直接操作}Node;intnumat=0;//指向num数组当前的位置，num数组用于存放结果voidOperate(int*in,intinst,intined,int*post,intpostst,intposted,Node*num,intlevel)//定义操作函数{//这个函数参数的含义：从中序in列表第inst个到第ined个，后序列表post第postst个到第posted个，存放于num中，此时位于level层if(inst==ined)//开始与结尾重合，到达递归终点，退出{num[numat].data=*(in+inst);num[numat].level=level;return;}//直接把该结点放入结果中intsym=*(post+posted);//读取最后一个后序intcount=0;//count的作用是后面方便确定下次递归的起点和终点inti;for(i=inst;*(in+i)!=sym;i++)//i从起点开始，到标志结束count++;num[numat].data=sym;num[numat].level=level;//将根节点放入if(i!=inst){numat++;Operate(in,inst,i-1,post,postst,postst+count-1,num,level+1);}//左边如果有，递归左子树elseif(i==insti!=ined){numat++;Operate(in,i+1,ined,post,postst,posted-1,num,level+1);}//左边没有，递归右子树（count为0右子树公式会出现错误）if(i!=insti!=ined)//两边都有，递归右子树{numat++;Operate(in,i+1,ined,post,posted-count,posted-1,num,level+1);}}intmain(){intn;cinn;intin[n];intpost[n];for(inti=0;in;i++)cinpost;for(inti=0;in;i++)cinin;Nodenum[n];Operate(in,0,n-1,post,0,n-1,num,0);//进行操作sort(num,num+n);//不进行排序则输出先序//或者使用冒泡排序//for(inti=0;in-1;i++)//for(intj=0;jn-1;j++)//if(num[j].levelnum[j+1].level)//{//Nodetmp=num[j];//num[j]=num[j+1];//num[j+1]=tmp;//}for(inti=0;in-1;i++)coutnum.data";coutnum[n-1].data;//输出结果}

该程序存在的一个小瑕疵：

6组测试数据，最后一组报段错误，始终找不出......