【数据结构】【输入一个整数数组，判断该数组是不是某二元查找树

题目来源：北航14级6系数据结构作业题

【问题描述】输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true，否则返回false。
【输入形式】输入任意长度的数组，数字之间空格分开
【输出形式】true 或者 false
【样例输入】输入576911108
【样例输出】true
【样例说明】由于这一整数序列是如下树的后序遍历结果：

8
/
610
/ /
57911

因此返回true。

【评分标准】暴力求解法不得分。

一开始我是想先利用这个后序遍历去还原一个二叉排序树的，但是发现怎么运行都是true，这里面应该是有问题的

于是在网上发现一个根本不用建立二叉树的做法

根据二叉树的后序遍历的特点我们知道，最后一个是根节点，然后，根节点的左子树分布在遍历输出的前部，其右子树在中间

即： 左子树||右子树||根节点

而且又是二叉排序树，所以只要判断属于左子树里面的元素有没有大于根节点的，属于右子树的元素有没有小于根节点的

算法流程：先从i=0开始，从左往右找到第一个属于右子树的元素，再往右开始进行判断

C代码：

#include <stdio.h>
#include <stdlib.h>

#define MAXNUM 50

int main() {

    int post[MAXNUM] = {0};//后序遍历
    int len_post = 0;
    int i,j;
    int rootN;


    while( (scanf("%d",&post[len_post])) != EOF) {
        len_post ++;
    }

    rootN = post[len_post-1];
    for( i = 0; i < len_post; i++) {
        if( post[i] > rootN)
            break;
    }

    for( j = i; j < len_post; j++) {
        if( post[j] < rootN ) {
            printf("false");
            break;
        }
    }

    if( j == len_post )
        printf("true");

    return 0;

}

算法是向yuucyf借鉴的，感谢他

他的博客链接：http://blog.csdn.net/yuucyf/article/details/6394770

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!