二叉搜索樹的數(shù)據(jù)結構-后序遍歷序列

標題: 輸入整數(shù)數(shù)組，以確定該數(shù)組是否是遍歷二叉搜索樹的結果. 如果為true，則返回true，否則為false. 假設輸入數(shù)組中的任何兩個數(shù)字互不相同

分析: 通過后遍歷二叉排序樹的遍歷，我們可以知道最后一個數(shù)字是樹的根節(jié)點，而二叉搜索樹的性質可以知道左節(jié)點值小于根節(jié)點值二叉排序樹的遍歷，右節(jié)點值大于根節(jié)點值. 遞歸.

/*
劍指offer面試題24
*/
#include <iostream>
using namespace std;
bool IsPostTree(int* a,int length){
    if(length <= 0){
        return false;
    }
    int root = *(a+length-1);
    int i=0;
    for(;i<length-1;i++){
        if(a[i] > root){
            break;
        }
    }
    int j=0;
    for(j=i;j<length-1;j++){
        if(a[j] < root){
            return false;
        }
    }
    bool left = true;
    if(i>0){
        left = IsPostTree(a,i);
    }
    bool right = true;
    if(j<length-1){
        right = IsPostTree(a+i,length-i-1);
    }
    return (left && right);
}
int main()
{
    int length,n;
    cin >> length;
    int a[length];
    if(length > 0){
        for(int i=0;i<length;i++){
            cin >> n;
            a[i] = n;
        }
    }
    bool result = IsPostTree(a,length);
    cout << result;
    return 0;
}

發(fā)布于2014-05-20 14: 49Ja°Read（...）評論（...）編輯

本文來自本站，轉載請注明本文網(wǎng)址：
http://www.pc-fly.com/a/jisuanjixue/article-265145-1.html