频道栏目
首页 > 程序开发 > 综合编程 > 其他综合 > 正文
二叉搜索树的后序遍历序列
2015-06-26 11:26:41         来源:xinyu913  
收藏   我要投稿

【题目】

输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true,否则返回false。假设输入的数组的任意两个数字都各不相同。


【分析】

假设输入数组{5,7,6,9,11,10,8}要判断它是不是二叉搜索树的后序遍历结果,就要结合二叉搜索树特点及后序遍历的方法来判断,后序遍历特点是数组最后一个就是二叉树的根节点,所以由此判断树根结点为8,并且先遍历左子树,再遍历右子树,所以关键在于判断出左子树右子树分界点在哪里。由二叉搜索树左子树小于根节点,右子树大于根节点的特点就可以找到分界点,{5,7,6}皆小于根节点8,所以其为左子树,而{9,11,10}大于根节点,所以为右子树,对左子树,右子树分别利用上述判断方法继续判断即可,一旦右子树中出现小于根节点的,则说明此数组并非为某二叉搜索树的后序遍历结果。

举一范例:{7,4,6,5}
1. 树根节点为5;
2. 数组第一个元素不小于5,说明树没有左子树,只有右子树;
3. 对于{7,4,6}都是右子树结点,理应全都大于5,但是4的存在直接就可以判定,此数组不为后序遍历结果。


【测试代码】

#include
#include

#define false 0
#define true 1

bool VerifySequenceOfBst( int sequence[ ], int length )
{
    if(sequence == NULL || length <= 0)
        return false;

    int root = sequence[ length - 1 ];

    //二叉搜索树中左子树的结点小于根结点
    int i = 0;
    for(  ; i < length - 1 ; ++i)
    {
        if( sequence[i] > root )
             break;
    }
    //在二叉搜索树中右子树的结点大于根结点
    int j = i;
    for(; j < length - 1 ; ++j )
    {
        if( sequence[j] < root )
            return false;
    }
    //判断左子树是不是二叉搜索树
    bool left = true;
    if( i > 0 )
        left = VerifySequenceOfBst( sequence, i );
    //判断右子树是不是二叉搜索书
    bool right = true;
    if( i < length - 1)
        right = VerifySequenceOfBst( sequence + i, length - i - 1 );

    return left & right;
}

void main( )
{
    int s[ ] = {5,7,6,9,11,10,8};
    if( VerifySequenceOfBst( s, 7 ))
        printf("存在一棵二叉搜索书,其后序遍历结果为{5,7,6,9,11,10,8}\n");
    else
        printf("不存在一棵二叉搜索书,其后序遍历结果为{5,7,6,9,11,10,8}\n");

    int s2[ ] = {7,4,6,5};
    if( VerifySequenceOfBst( s2,7 ))
        printf("存在一棵二叉搜索书,其后序遍历结果为{7,4,6,5}\n");
    else
        printf("不存在一棵二叉搜索书,其后序遍历结果为{7,4,6,5}\n");
}

【输出】

这里写图片描述

点击复制链接 与好友分享!回本站首页
相关TAG标签 序列
上一篇:一些项目——连续奇数和
下一篇:汉字转拼音再转ASCII
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站