判断整数序列是不是某二叉查找树的后序遍历的结果
答案:1 悬赏:70 手机版
解决时间 2021-12-29 18:47
- 提问者网友:献世佛
- 2021-12-29 06:26
判断整数序列是不是某二叉查找树的后序遍历的结果
最佳答案
- 五星知识达人网友:不想翻身的咸鱼
- 2022-01-22 06:13
题目:输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true,否则返回false。
例如输入5、7、6、9、11、10、8,由于这一整数序列是如下树的后序遍历结果:
8
/ \
6 10
/ \ / \
5 7 9 11
因此返回true。
如果输入7、4、6、5,没有哪棵树的后序遍历的结果是这个序列,因此返回false。
树的题目一般都是递归的思路,因为是因为是排序树,而且是后序,所以思路是序列最后一个必是根节点,从前往后遍历,比根节点小的都是其左子树,并且位于序列的左半部分,比其大的为其右子树,应该位于其右半部分。左右子树按上述思路分别进行判断。
代码如下:
#include<iostream>
using namespace std;
void test(const int data[],int start,int node,bool &flag){
if(flag&&start<node){ // 判断条件,注意start<node
int left=start;
while(data[node]>data[left]){ //取得其左子树
left++;
}
for(int j=left;j<node;j++){ //判断是否为其右子树
if(data[j]<data[node]) {flag=false; return;} //若
}
test(data,0,left-1,flag); //递归
test(data,left,node-1,flag);
}
}
int main(void){
bool flag=true;
int a[]={5,7,6,9,11,10,8};
test(a,0,6,flag);
if(flag) cout<<"yes"<<endl;
else cout<<"no"<<endl;
int b[]={7,4,6,5};
test(b,0,3,flag);
if(flag) cout<<"yes"<<endl;
else cout<<"no"<<endl;
system("pause");
return 0;
例如输入5、7、6、9、11、10、8,由于这一整数序列是如下树的后序遍历结果:
8
/ \
6 10
/ \ / \
5 7 9 11
因此返回true。
如果输入7、4、6、5,没有哪棵树的后序遍历的结果是这个序列,因此返回false。
树的题目一般都是递归的思路,因为是因为是排序树,而且是后序,所以思路是序列最后一个必是根节点,从前往后遍历,比根节点小的都是其左子树,并且位于序列的左半部分,比其大的为其右子树,应该位于其右半部分。左右子树按上述思路分别进行判断。
代码如下:
#include<iostream>
using namespace std;
void test(const int data[],int start,int node,bool &flag){
if(flag&&start<node){ // 判断条件,注意start<node
int left=start;
while(data[node]>data[left]){ //取得其左子树
left++;
}
for(int j=left;j<node;j++){ //判断是否为其右子树
if(data[j]<data[node]) {flag=false; return;} //若
}
test(data,0,left-1,flag); //递归
test(data,left,node-1,flag);
}
}
int main(void){
bool flag=true;
int a[]={5,7,6,9,11,10,8};
test(a,0,6,flag);
if(flag) cout<<"yes"<<endl;
else cout<<"no"<<endl;
int b[]={7,4,6,5};
test(b,0,3,flag);
if(flag) cout<<"yes"<<endl;
else cout<<"no"<<endl;
system("pause");
return 0;
我要举报
如以上问答信息为低俗、色情、不良、暴力、侵权、涉及违法等信息,可以点下面链接进行举报!
大家都在看
推荐资讯