前序中序求后序
程序员文章站
2022-05-19 21:21:59
...
Test:
FDXEAG
XDEFAG
/*
涉及到二叉树的问题最好不用动态申请,对内存的管理很麻烦
采用预分配的静态数组
*/
//本题目由前序和中序得到后序,方法:先构造二叉树,再进行
#include<stdio.h>
#include<string.h>
struct Node{
Node *lchild;
Node* rchild;
char data;
}Tree[50];
char str1[50],str2[50];//分别存放前序和中序
int loc;//指向下一个尚未分配到的位置
Node *creat(){//申请一个空节点
Tree[loc].lchild=Tree[loc].rchild=NULL;
return &Tree[loc++];
}
void PostOrder(Node *T){
if(T->lchild) PostOrder(T->lchild);
if(T->rchild) PostOrder(T->rchild);
printf("%c",T->data);
}
/*
先序的第一个是根,确定其在中序下的位置即可划分左右子树
*/
Node *build(int s1,int e1,int s2,int e2){
Node *ret=creat();
ret->data=str1[s1];
int root;
for(int i=s2;i<=e2;i++){
if(str2[i]==str1[s1])
{root=i;break;}
}
int size=root-s2;
//当root不为s2和e2时有左右子树
if(root!=s2)
ret->lchild=build(s1+1,s1+size,s2,root-1);
if(root!=e2)
ret->rchild=build(s1+size+1,e1,root+1,e2);
return ret;
}
int main(){
while(scanf("%s",str1)!=EOF){
scanf("%s",str2);
int len1=strlen(str1);
int len2=strlen(str2);
Node *T=build(0,len1-1,0,len2-1);
PostOrder(T);
printf("\n");
}
return 0;
}
上一篇: 解决jquery .ajax 在IE下卡死问题的解决方法_jquery
下一篇: 收藏 不显示删除回复显示所有回复显示星级回复显示得分回复 这算是代理下载吗。 有人做过吗,哪位高手给个方案。 多谢了
推荐阅读
-
Python利用前序和中序遍历结果重建二叉树的方法
-
Python实现输入二叉树的先序和中序遍历,再输出后序遍历操作示例
-
PHP实现二叉树深度优先遍历(前序、中序、后序)和广度优先遍历(层次)实例详解
-
[PHP] 算法-根据前序和中序遍历结果重建二叉树的PHP实现
-
c/c++ 用前序和中序,或者中序和后序,创建二叉树
-
Python实现二叉树前序、中序、后序及层次遍历示例代码
-
【算法】二叉树的前序、中序、后序、层序遍历和还原。
-
PHP基于非递归算法实现先序、中序及后序遍历二叉树操作示例
-
Python二叉树的遍历操作示例【前序遍历,中序遍历,后序遍历,层序遍历】
-
L2-006 树的遍历 (后序中序求层序)