确定数组是否是遍历二叉搜索树的结果的数组

全部展开

//二元搜索树的2113搜索顺序. cpp: 定义控制台应用程序的入口点. 5261

//

#include“ stdafx.h”

#include

使用命名空间标准；

bool isPostBST（int sequence []，int length）// //注意，此处在4102中传递的序列指向该序列的第一个节点，即1653个点

{

// 1. 容错能力

if（sequence == NULL || length <= 0）

返回假；

// 2. 首先，我们需要找到序列的分界点. 这时，因为遍历了左子树，所以它也等同于左子树的判断

int i; //边界点

for（i = 0; i

{

if（sequence [i]> sequence [length-1]）

休息；

}

// 3. 判断序列的右子树

for（int j = i; j

{

if（sequence [j]

返回假；

}

// 4. 当满足左右两个子树时，必须进行递归

如果（i> = 1）//当左边至少有两个点时

返回isPostBST（sequence，i）;

if（i <= length-3）//当右子树至少有两个点时

return isPostBST（sequence + i，length -i-1）; // i是左子树的数量判断 二叉排序树，1是根节点的数量

返回true;

}

int _tmain（int argc，_TCHAR * argv []）

{

// int s [] = {7,4,6​​,5};

// int s [] = {7，8判断 二叉排序树，6，5};

int s [] = {5,7,6,9,11,10,8};

如果（isPostBST（s，7））

cout <<“输入数组是二进制搜索树的后遍历！” << endl;

其他

cout <<“输入数组不是任何二进制搜索树的后序遍历！” << endl;

返回0；

}

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-234282-1.html