【编程题目】判断整数序列是不是二元查找树的后序遍历结果，如果是，构建该二元查找树

#include<stdio.h>
#include<stdlib.h>
#include<vector>
using namespace std;
typedef struct BinaryTree 
{
    int data;
    struct BinaryTree *rchild, *lchild;
}BinaryTree;

void visit(BinaryTree * &p)
{
    if(p != NULL)
    {
        free(p);
        p = NULL;
    }
}

int AferOrderTraverse(BinaryTree *&T) //后序遍历
{
    BinaryTree * p;
    vector<BinaryTree *> Stack;
    int tag[30] = {0}; //用tag标签记录存入的是左子树0 还是右子树1
    int tagnum = 0; //记录存放的数量
    Stack.push_back(T);
    tag[0] = 0;
    tagnum = 1;

    while(!Stack.empty())
    {
        while((p = Stack.back())!= NULL)
        {
            Stack.push_back(p->lchild);
            tag[tagnum++] = 0;
        }
        //只要右子树弹出，其双亲结点就被访问并弹出
        while(tag[tagnum - 1] == 1)  //若是右子树 先弹出开始的空集 访问其parent结点（一定是其上一个结点） 再循环弹出
        {
            Stack.pop_back();
            tagnum--;
            visit(Stack.back());
        }
        Stack.pop_back();
        tagnum--;
    
        if(!Stack.empty())
        {
            p = Stack.back();
            Stack.push_back(p->rchild);
            tag[tagnum++] = 1;
        }
    }
    return 0;
}

//输入,待构造的数组， 数组的长度 和待返回的二元查找树 返回1 说明构造成功 返回0 说明构造失败
int TreeFromAfterOrder(int * in, int leng, BinaryTree * &T)
{
    int n = leng;
    T = NULL;  //令树根初始为空
    while(n != 0) //从后向前 一次插入结点
    {
        BinaryTree * tmp = (BinaryTree *)malloc(sizeof(BinaryTree));  //构造当前带插入的结点
        tmp->data = in[n - 1];   //当前待插入的数据
        tmp->lchild = NULL;
        tmp->rchild = NULL;
        if(T == NULL)  //如果根是空的 把当前结点设为根
        {
            T = tmp;
        }
        else  //如果根不是空的
        {
            BinaryTree * x = T;
            BinaryTree *px = NULL;
            while(x != NULL)   //循环查找应该插入的位置 并判断是否合法
            {
                if(tmp->data > x->data)
                {
                    if(x->lchild != NULL) //向右移动时 必须左子树为空 因为从后向前依次插入点 如果左子树不为空说明 右子树应该已经访问完毕 不应该再次访问了 否则不满足后序遍历条件
                    {
                        AferOrderTraverse(T);  //不满足时后序遍历 释放已分配的内存
                        return 0;
                    }
                    else
                    {
                    px = x;
                    x = x->rchild;
                    }
                }
                else
                {
                    px = x;
                    x = x->lchild;
                }
            }
            if(tmp->data > px->data)
            {
                px->rchild = tmp;
            }
            else
            {
                px->lchild = tmp;
            }
        }
        n--;
    }
    return 1;
}
int main()
{
    int a[8] = {1,3,4,2,6,8,7,5};
    int b[4] = {7,4,6,5};

    BinaryTree * T = NULL;
    int result = TreeFromAfterOrder(b, 4, T);

    if(result == 1)
    {
        printf("success");
    }
    else
    {
        printf("wrong");
    }

    return 0;
}