03-树3 Tree Traversals Again   (25分)

/*===================================================================================== # COPYRIGHT NOTICE # Copyright (c) 2016 # # @Author :Zehao Wang # @Email :[e-mail] # @from ：https://pta.patest.cn/pta/test/1342/exam/4/question/19893 # @Last modified :2016-11-30 # @Description :已知先序和中序遍历，求后序遍历 ========================================================================================*/




#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAX 50
#define NULL -1

typedef struct SNode *Stack;
struct SNode {
    int data[MAX];
    int Top;
};
void Push(Stack S, int ele);
int Pop(Stack S);
void find_post(int arr1[], int arr2[], int left2, int right2, int head1);
int find_head(int arr[], int data);
int arr_size(int arr[]);





void Push(Stack S, int ele)
{
    if (S->Top == MAX - 1)
    {
        printf("堆栈满");
        return;
    }
    else {

        S->data[++(S->Top)] = ele;

    }
}

int Pop(Stack S)
{
    if (S->Top == -1)
    {
        printf("堆栈空");
        return NULL;
    }
    else {
        return S->data[(S->Top)--];
    }
}


void find_post(int arr1[], int arr2[], int left2, int right2, int head1)
{
    int head2 = find_head(arr2, arr1[head1]);
    int left_size = head2 - left2;
    int tag = 0;//调整输出格式用
    int ele;
    if (head1 != arr_size(arr1))
    {
        if (head2 > left2)
        {
            find_post(arr1, arr2, left2, head2 - 1, head1+1);
        }
        if (head2 < right2)
        {
            find_post(arr1, arr2, head2 + 1, right2, head1 + left_size+1);
        }
        if (head1 != 0)
            printf("%d ", arr1[head1]);
        else
            printf("%d", arr1[head1]);//因为后序遍历最后一个输出的一定是先序遍历第一个输出的元素，所以后序遍历
                                      //输出最后一个元素时head1一定指向数组头。
    }

}




int find_head(int arr[], int data)//求头节点的数组下标位置
{
    for (int i = 0; i < arr_size(arr); i++)
    {
        if (arr[i] == data)
            return i;
    }
}

int arr_size(int arr[])//求数组长度的函数
{
    int i = 0;
    while (arr[i] != NULL)
        i++;
    return i;

}

int main(void)
{
    char s[MAX];
    int preOrder[MAX];
    int inOrder[MAX];//存放先序遍历，中序遍历节点顺序的数组
    int preIndex = 0, inIndex = 0, postIndex = 0;
    Stack S;
    S = (struct SNode*)malloc(sizeof(struct SNode));//一定要有指针！
    S->Top = -1;//结点中的值记得初始化。
    int pushele;//压栈数字
    int popele;//出栈数字
    int N;//结点总数
    for (int i = 0; i < 30; i++)//数组初始化，这点很有必要
    {
        inOrder[i] = -1;
        preOrder[i] = -1;
    }
    scanf("%d", &N);
    for (int i = 0; i < 2 * N; i++)//输入2乘N次
    {
        scanf("%s", s);
        if (strcmp(s, "Push") == 0) 
        {
            scanf("%d", &pushele);
            Push(S,pushele);
            preOrder[preIndex++] = pushele;
        }
        else
            if (strcmp(s, "Pop") == 0) 
            {
                popele = Pop(S);
                inOrder[inIndex++] = popele;//将每一个出栈数字依次存入中序遍历数组
            }
            else
            {
                printf("输入非法");
                return 0;
            }
    }
    find_post(preOrder, inOrder, 0,arr_size(inOrder)-1, 0);
    return 0;


}
/*============================================================================= 注意：1.这道题主要利用递归来求解后序遍历。具体思路是：先序遍历的第一个数字一定是 整个树的根节点，在中序遍历中找到它之后。该元素数组下标左边一定是根节点的坐子树， 然后查找先序遍历的第二个数字在中序遍历数组中的位置，它一定是根节点的左子树的根 节点。就这样不断向下查找。左子树输出完成再输出右子树。该递归比较抽象，不太好想。 2.在解题过程中，犯了几个错误。 第一个，也是最主要的错误，就是以为堆栈的顺序存储可以不用设置指针。但其实如果不设 指针，则在函数调用该堆栈时，则会开辟两个不一样的数组空间，导致程序报错。不管是队 列还是堆栈，不管是顺序存储还是链式存储，指针都是必不可少的！ 第二个：数组在使用时一定要初始化。详见第122行。 =============================================================================*/