已知一颗二叉树S的前序遍历和中序遍历序列,请编程输出二叉树S的后续遍历序列.

待我称王封你为后i 2022-08-07 01:57 28阅读 0赞

\#include <stdio.h>  
\#include <string.h>  
  
  
//在中序中查找根的下标  
int FindRoot(char c, char in\[\], int s, int e)  
\{  
int i;  
for(i=s; i<=e; i++)  
\{  
if(in\[i\] == c)  
\{  
break;  
\}  
\}  
return i;  
\}  
  
  
/\*  
 \*递归遍历求得后序  
 \*@pre:先序序列  
 \*@pre\_s:当前二叉树的先序序列起始下标  
 \*@pre\_e:当前二叉树的先序序列结束下标  
 \*@in:中序序列  
 \*@in\_s:当前二叉树的中序序列起始下标  
 \*@in\_e:当前二叉树的中序序列结束下标  
 \*/  
void PostOrder(char pre\[\], int pre\_s, int pre\_e,  
char in\[\], int in\_s, int in\_e)  
\{  
char c;  //根节点符号  
int root;  //根节点在中序中的下标  
int l\_len, r\_len;//左、右子树节点数  
  
  
//当前二叉树只有一个节点(叶子节点)  
if(in\_s == in\_e)  
\{  
printf("%c", in\[in\_s\]);  
\}  
else  
\{  
//当前二叉树的根节点  
c = pre\[pre\_s\];  
  
  
//获取根节点在中序中的下标  
root = FindRoot(c, in, in\_s, in\_e);  
  
  
//计算左、右子树的节点数  
l\_len = root - in\_s;  
r\_len = in\_e - root;  
  
  
//分割左子树  
if(l\_len > 0)//左子树节点数不为0  
\{  
PostOrder(pre, pre\_s+1, pre\_s+l\_len,  
in, in\_s, root-1);  
\}  
  
  
//分割右子树  
if(r\_len > 0)//右子树节点数不为0  
\{  
PostOrder(pre, pre\_e-r\_len+1, pre\_e,  
in, root+1, in\_e);  
\}  
  
  
//后序输出根  
printf("%c", c);  
\}  
\}  
  
  
int main()  
\{  
char pre\[\] = "ABDECFG";  
char in\[\]  = "DBEACGF";  
  
  
PostOrder(pre, 0, strlen(pre)-1,  
in, 0, strlen(in)-1);  
printf("\\n");  
  
  
return 0;  
\}