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

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

2024-07-15 09:08:28   220人阅读

判断整数序列是不是二元查找树的后序遍历结果
题目：输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。
如果是返回 true，否则返回 false。
例如输入 5、7、6、9、11、10、8，由于这一整数序列是如下树的后序遍历结果：
8
/ \
6 10
/ \ / \
5 7 9 11
因此返回 true。
如果输入 7、4、6、5，没有哪棵树的后序遍历的结果是这个序列，因此返回 false。

 

 

做这个题目的时候最开始傻了，想着从前到后根据数字的大小关系判断。后来幡然醒悟，根据后序遍历的特点。序列最后一个数字就是根节点数字，只要从后向前依次把数字插入的二元查找树中就可以了。 

树一定是可以构建成功的，因为我们只不过是不停的插入数据罢了。 但是这个构建的树 是否符合 后序遍历的结果是 给定序列则不一定了。 需要判断。

判断的原则：

因为我们插入数字是从序列的后面往前面插入。这说明，先插入的点应该在后序遍历的后面出现， 如果一棵树的某个节点的左子树已经被构建了，就说明之后不应该再访问其右子树了， 因为遍历过程中先访问左子树，后访问右子树。根据此可以判定输入序列是否合法。

 

代码： 写了一晚上，构建失败时后序遍历释放内存后 出函数后 T虽然被释放了 但不是我想要的NULL 而是一个随意的值。不知道哪里有问题。 但整体的功能是都正确的。

代码功能：根据输入判断是否是一个二元查找树后序遍历结果，如果是，构建该二元查找树。

#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 = http://www.mamicode.com/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;}

 


联系
我们