数据结构--二叉树--顺序存储判断是否二叉搜索树(2022统考真题)

数据结构–二叉树–顺序存储判断是否二叉搜索树(2022统考真题)

题目描述：

思路

二叉搜索树（Binary Search Tree，简称BST）是一种具有以下性质的二叉树：

对于树中的每个节点 N，它的左子树（如果存在）中的所有节点的值都小于 N 节点的值。
对于树中的每个节点 N，它的右子树（如果存在）中的所有节点的值都大于 N 节点的值。
左子树和右子树也分别是二叉搜索树。
为了验证给定的数组是否构成一个有效的二叉搜索树，我们需要确保每个节点的值满足上述性质。特别是要保证在每个节点的值满足其左右子节点的值的约束。

从后向前的去验证，节点 N 与 它的父亲是否满足上述的条件。

代码

#include <iostream>
#define MAX_SIZE 100
using namespace std;
typedef struct {
	int sqBitNode[MAX_SIZE];
	int ElemNum;
} SqBiTree;
int lmax[MAX_SIZE], rmin[MAX_SIZE]; 
bool check(SqBiTree tree)
{
	for (int i = 0; i < tree.ElemNum; i++)
		lmax[i] = tree.sqBitNode[i], rmin[i] = tree.sqBitNode[i];
	for  (int i = tree.ElemNum - 1; i ;i--)
	{
		if (tree.sqBitNode[i] == -1) continue;
		int fa = (i - 1) / 2;
		if (i % 2 == 1 && tree.sqBitNode[fa] > lmax[i]) // fa 与 左孩子
			lmax[i] = tree.sqBitNode[fa];
		else if (i % 2 == 0 && tree.sqBitNode[fa] < rmin[i]) // fa 与 右孩子
			rmin[i] = tree.sqBitNode[fa];
		else 	return false;
	}
	return true;
}
int main()
{
	
	SqBiTree tree;
	cin >> tree.ElemNum;	
	for (int i = 0; i < tree.ElemNum; i++)
		cin >> tree.sqBitNode[i];
	cout << (check(tree) == 1 ? "tree" : "false") << '\n';
} 
/*
10 40 25 60 -1 30 -1 80 -1 -1 27

11 40 50 60 -1 30 -1 -1 -1 -1 -1 35
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38