【考研408真题】2022年408数据结构41题---判断当前顺序存储结构树是否是二叉搜索树

思路

很明显，这是一个顺序存储结构的树的构成方法。其中树的根节点位置从索引0开始，对于该结构，存在有：如果当前根节点的下标为n，那么其左子树下标为2n+1，右子树下标为2n+2。
而对于BST，我们知道，其一个非常显著的特点就是：对于根节点root，其左子树小于其根节点的值，其右子树大于其根节点的值。同时，如果当前节点为null，不影响其是否为BST。
基于这个理论，我们大概的实现思路是：递归的判断当前根节点的左子树和右子树，并且限定其左右子树的值的大小区间范围。
那么这里应该如何去限制这个范围呢？
从上面的理论中我们可以得到如下的伪代码：

//如下代码基于链式存储结构 不过不影响理论实践
bool isBST(SqBiTree* root,int low,int high)
{
	if(root==null){
		return true;
	}
	//这里逻辑严谨应该增加一个左右指针的非空判断 我就不写了
	if(root.left.val>=root.val || root.right.val <= root.val){
		return false;
	}
	return isBST(root.left,low,root.val) && 
	isBST(root.right,root.val,maxValue);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

为什么要这么写呢？
首先我们基于上面的定义，如果当前节点为空，不影响当前树是否是BST，因此直接返回tree。
之后，我们开始条件判断，当前节点的左右子节点，是否小于和大于当前节点。
如果不是，也就是违法了BST的特性，那么我们直接返回false。
并且，我们一开始也说了，这应该是一个递归的判断过程，因此我们还需要对当前root节点的左子树和右子树继续去执行当前的递归过程。
那么递归的条件是什么？
对于当前节点的左子树，其最小值应该是不限定的，但是其最大值必须小于当前节点的值，
而对于其右子树，其最小值应该大于当前节点的值，其最大值不限。
所以就可以得到最后两行代码的条件了。
那么换到我们题目中，我们只需要将指针操作，修改为对数组下标的数据判断即可。
最终就可以得到如下代码：

// 递归函数，判断以n为根的二叉树是否是BST
bool isBSTUtil(BinaryTree *T, int n, TreeNodeType minVal, TreeNodeType maxVal)
{
    if (T->data[n] == '\0')
        return true;

    TreeNodeType nodeValue = T->data[n];

    // 检查当前节点的值是否在[minVal, maxVal]的范围内
    if ((nodeValue <= minVal) || ( maxVal <= nodeValue))
        return false;

    // 递归检查左子树和右子树，更新范围
    return isBSTUtil(T, 2 * n, minVal, nodeValue) && isBSTUtil(T, 2 * n + 1, nodeValue, maxVal);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

ok，经过上面的解释，我们就已经得到了完整的当前题目的实现思路了。
完整代码如下：

#include 
#include 
#include 
#include 

#define MaxSize 100

typedef int TreeNodeType;

// 二叉树结构
typedef struct
{
    TreeNodeType data[MaxSize];
    int BiTreeNum;
} BinaryTree;

// 声明队列数据结构
typedef struct
{
    int front, rear;
    int size;
    int capacity;
    int *array;
} Queue;

void initTree(BinaryTree *T);
void createTree(BinaryTree *T, int n);
TreeNodeType rootTree(BinaryTree *T);
int countTree(BinaryTree *T);
int maxDepthOfTree(BinaryTree *T, int n);
void preOrderTraverse(BinaryTree *T, int n);
void inOrderTraverse(BinaryTree *T, int n);
void postOrderTraverse(BinaryTree *T, int n);
void levelOrderTraverse(BinaryTree *T); // 层序遍历
bool destoryTree(BinaryTree *T);
void traverseArray(BinaryTree *T); // 遍历数组
bool isBSTUtil(BinaryTree *T, int n, TreeNodeType minVal, TreeNodeType maxVal);

// 队列相关函数
Queue *createQueue(int capacity);
bool isQueueEmpty(Queue *queue);
bool isQueueFull(Queue *queue);
void enqueue(Queue *queue, int item);
int dequeue(Queue *queue);

int main()
{
    BinaryTree T;
    // 开始构造二叉树 其中使用1作为根节点下标
    // 而不是使用0，使用0的问题在于不好表示数据在数组中的位置
    // 我们知道二叉树满足 当前节点n的左子树和右子树的序列号应该为 2n和2n+1
    initTree(&T);
    printf("请输入根结点(输入#表示该结点为空):");
    createTree(&T, 1);

    traverseArray(&T);

    printf("当前二叉树的最大深度为：%d\n", maxDepthOfTree(&T, 1));

    printf("先序遍历：");
    preOrderTraverse(&T, 1);
    printf("\n");

    printf("中序遍历：");
    inOrderTraverse(&T, 1);
    printf("\n");

    printf("后序遍历：");
    postOrderTraverse(&T, 1);
    printf("\n");

    printf("层序遍历：");
    levelOrderTraverse(&T);
    printf("\n");

    if (isBSTUtil(&T, 1, -10000, 10000))
    {
        printf("this is a BST");
    }
    else
    {
        printf("this is not a BST");
    }

    return 0;
}

void initTree(BinaryTree *T)
{
    int i;
    for (i = 0; i < MaxSize; ++i)
    {
        T->data[i] = '\0';
    }

    T->BiTreeNum = 0;
    return;
}

void createTree(BinaryTree *T, int n)
{
    char ch;
    // 刷新（清空）标准输入流（stdin）
    // 主打一个求稳
    fflush(stdin);
    // 输入当前节点信息 # 代表当前节点为空
    // 先构造过字数
    scanf(" %c", &ch);
    if (ch == '#')
    { // 空直接返回
        return;
    }
    else
    {
        T->data[n] = ch;
        T->BiTreeNum++;
        printf("输入 %c 的左子树数据（输入#表示当前左子树为空: ", ch);
        // 这里有一个技巧
        createTree(T, 2 * n);
        printf("输入 %c 的右子树数据（输入#表示当前右边子树为空）: ", ch);
        createTree(T, (2 * n + 1));
    }
}

// 计算二叉树的最大深度
// 从根节点到叶子节点的最长路径的长度
// 由于是顺序结构 因此这里从第一层也就是n=1开始向下遍历
// 然后不断的判断左子树和右子树的高度
// 最后取最大值
int maxDepthOfTree(BinaryTree *T, int n)
{
    if (n <= T->BiTreeNum && T->data[n] != '\0')
    {
        int leftDepth = maxDepthOfTree(T, 2 * n);
        int rightDepth = maxDepthOfTree(T, 2 * n + 1);

        return 1 + fmax(leftDepth, rightDepth);
    }
    else
    {
        return 0;
    }
}

// 先序遍历 根左右
void preOrderTraverse(BinaryTree *T, int n)
{
    if (T->data[n] == '\0')
        return;
    else
    {
        printf("%c ", T->data[n]);
        preOrderTraverse(T, 2 * n);
        preOrderTraverse(T, (2 * n + 1));
    }
}
// 中序遍历 左根由7
void inOrderTraverse(BinaryTree *T, int n)
{
    if (T->data[n] == '\0')
        return;
    else
    {
        inOrderTraverse(T, 2 * n);
        printf("%c ", T->data[n]);
        inOrderTraverse(T, (2 * n + 1));
    }
}
// 后序遍历  左右根
void postOrderTraverse(BinaryTree *T, int n)
{
    if (T->data[n] == '\0')
        return;
    else
    {
        postOrderTraverse(T, 2 * n);
        postOrderTraverse(T, (2 * n + 1));
        printf("%c ", T->data[n]);
    }
}
void traverseArray(BinaryTree *T)
{
    for (int i = 1; i <= T->BiTreeNum; i++)
    {
        printf("%c  ", T->data[i]);
    }
    printf("\n");
}

// 层序遍历二叉树
void levelOrderTraverse(BinaryTree *T)
{
    if (T->BiTreeNum == 0)
    {
        printf("二叉树为空\n");
        return;
    }

    Queue *queue = createQueue(T->BiTreeNum);
    int current = 1; // 从根节点开始

    while (current <= T->BiTreeNum)
    {
        printf("%c ", T->data[current]);

        if (2 * current <= T->BiTreeNum && T->data[2 * current] != '\0')
        {
            enqueue(queue, 2 * current);
        }

        if (2 * current + 1 <= T->BiTreeNum && T->data[2 * current + 1] != '\0')
        {
            enqueue(queue, 2 * current + 1);
        }

        if (!isQueueEmpty(queue))
        {
            current = dequeue(queue);
        }
        else
        {
            break;
        }
    }

    free(queue->array);
    free(queue);
}

// 创建队列
Queue *createQueue(int capacity)
{
    Queue *queue = (Queue *)malloc(sizeof(Queue));
    if (!queue)
    {
        perror("内存分配失败");
        exit(EXIT_FAILURE);
    }

    queue->front = 0;
    queue->rear = -1;
    queue->size = 0;
    queue->capacity = capacity;
    queue->array = (int *)malloc(capacity * sizeof(int));
    if (!queue->array)
    {
        perror("内存分配失败");
        exit(EXIT_FAILURE);
    }

    return queue;
}

// 检查队列是否为空
bool isQueueEmpty(Queue *queue)
{
    return (queue->size == 0);
}

// 检查队列是否已满
bool isQueueFull(Queue *queue)
{
    return (queue->size == queue->capacity);
}

// 入队列
void enqueue(Queue *queue, int item)
{
    if (isQueueFull(queue))
    {
        printf("队列已满\n");
        return;
    }

    queue->rear = (queue->rear + 1) % queue->capacity;
    queue->array[queue->rear] = item;
    queue->size++;
}

// 出队列
int dequeue(Queue *queue)
{
    if (isQueueEmpty(queue))
    {
        printf("队列为空\n");
        return -1;
    }

    int item = queue->array[queue->front];
    queue->front = (queue->front + 1) % queue->capacity;
    queue->size--;

    return item;
}

// 递归函数，判断以n为根的二叉树是否是BST
bool isBSTUtil(BinaryTree *T, int n, TreeNodeType minVal, TreeNodeType maxVal)
{
    if (T->data[n] == '\0')
        return true;

    TreeNodeType nodeValue = T->data[n];

    // 检查当前节点的值是否在[minVal, maxVal]的范围内
    if ((nodeValue <= minVal) || ( maxVal <= nodeValue))
        return false;

    // 递归检查左子树和右子树，更新范围
    return isBSTUtil(T, 2 * n, minVal, nodeValue) && isBSTUtil(T, 2 * n + 1, nodeValue, maxVal);
}

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311

408考研各数据结构C/C++代码（Continually updating）

408考研各数据结构C/C++代码（Continually updating）
这个模块是我应一些朋友的需求，希望我能开一个专栏，专门提供考研408中各种常用的数据结构的代码，并且希望我附上比较完整的注释以及提供用户输入功能，ok，fine，这个专栏会一直更新，直到我认为没有新的数据结构可以讲解了。
目前我比较熟悉的数据结构如下：
数组、链表、队列、栈、树、B/B+树、红黑树、Hash、图。
所以我会先有空更新出如下几个数据结构的代码，欢迎关注。 当然，在我前两年的博客中，对于链表、哈夫曼树等常用数据结构，我都提供了比较完整的详细的实现以及思路讲解，有兴趣可以去考古。