Question

求大神用c语言写一下数据结构的题

3、以下问题要求统一在一个大程序里解决。
按先序遍历的扩展序列建立二叉树的存储结构
二叉树先序、中序、后序遍历的递归算法
二叉树中序遍历的非递归算法
二叉树层次遍历的非递归算法（要求使用顺序队列，调用顺序队列基本操作实现）
求二叉树的深度(后序遍历)
建立树的存储结构
求树的深度

Answer 1

#include<bits/stdc++.h>
using namespace std;
char val[100005];
string s1,s2;
int num,len,pos1,pos2;
void dfs(int root,int l1,int r1,int l2,int r2)
{
val[root]=s1[l1];
if(l1==r1)
return ;
int ne=l2;
while(s2[ne]!=s1[l1])
ne++;
if(ne!=l2)
dfs(root<<1,l1+1,l1+ne-l2,l2,ne-1);
if(ne!=r2)
dfs(root<<1|1,l1+ne-l2+1,r1,ne+1,r2);
}
void dfs2(int root)
{
if(val[root<<1])
dfs2(root<<1);
if(val[root<<1|1])
dfs2(root<<1|1);
printf("%c",val[root]);
}
int main()
{
while(cin>>s1)
{
memset(val,0,sizeof(val));
cin>>s2;
len=s1.length();
num=1,pos2=pos1=0;
dfs(1,0,len-1,0,len-1);
dfs2(1);
printf("\n");
}
return 0;
}
【请采纳】