返回主页
已有1条笔记
[数据结构 P2014] 已知非空二叉树T的结点值均为正整数，采用顺序存储方式保存，数据结构定义如下：
未通过
已知非空二叉树T的结点值均为正整数，采用顺序存储方式保存，数据结构定义如下：
typedef struct { // MAX_SIZE为已定义常量
Elemtype SqBiTNode[MAX_SIZE]; // 保存二叉树结点值的数组
int ElemNum; // 实际占用的数组元素个数
}SqBiTree;
T中不存在的结点在数组SqBiTNode中用-1表示。例如，对于下图所示的两棵非空二叉树T1和T2：
请设计一个尽可能高效的算法，判定一棵采用这种方式存储的二叉树是否为二叉搜索树，若是，则返回true，否则，返回false，要求：
⑴ 给出算法的基本设计思想。
⑵ 根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
加入错题本
个人笔记
解答：
注意本题二叉树以静态...
用户登录可进行刷题及查看答案
解答：
注意本题二叉树以静态数组的方式表示，数组起始下标为0。
先画出二叉树，然后将其填充为完全二叉树，按照层序遍历顺序填写编号：
如果根结点下标为0（适用于C/C++语言数组）有 ：
left_child_id = parent_id * 2 + 1;
right_child_id = parent_id * 2 + 2;
如果根结点下标为1，这时候题目会写明条件。
为了方便解答，结构体中的Elemtype默认为int。
方法一：递归
利用二叉搜索树的性质：设 x 是二叉搜索树中的一个结点。如果y是x左子树中的一个结点，那么y.key≤x.key，如果y是x右子树中的一个结点，那么y.key≥x.key。
C代码如下（含测试用例）：
#include <stdio.h>
#include <string.h>
#include <limits.h>
#define MAX_SIZE 20011
#define false 0
#define true 1
typedef int bool;
typedef struct { // MAX_SIZE为已定义常量
int SqBiTNode[MAX_SIZE]; // 保存二叉树结点值的数组
int ElemNum; // 实际占用的数组元素个数
}SqBiTree;
bool helper(SqBiTree T, int i, long long lower, long long upper) {
if (i >= T.ElemNum || T.SqBiTNode[i] == -1) { // 越界或者为空结点
return true;
}
if (T.SqBiTNode[i] <= lower || T.SqBiTNode[i] >= upper) {
return false;
}
return helper(T, 2 * i + 1, lower, T.SqBiTNode[i]) && helper(T, 2 * i + 2, T.SqBiTNode[i], upper);
}
bool isValidBST(SqBiTree T) {
return helper(T, 0, LONG_MIN, LONG_MAX);
}
int main() {
int a1[10] = {40, 25, 60, -1, 30, -1, 80, -1, -1, 27};
SqBiTree bt1;
memset(bt1.SqBiTNode, 0, sizeof(bt1.SqBiTNode));
bt1.ElemNum = 10;
for (int i = 0; i < bt1.ElemNum; ++i) {
bt1.SqBiTNode[i] = a1[i];
}
int ans1 = isValidBST(bt1);
if (ans1 == true) {
printf("T1 is a binary search tree\n");
} else {
printf("T1 is not a binary search tree\n");
}
int a2[11] = {40, 50, 60, -1, 30, -1, -1, -1, -1, -1, 35};
SqBiTree bt2;
memset(bt2.SqBiTNode, 0, sizeof(bt2.SqBiTNode));
bt2.ElemNum = 11;
for (int i = 0; i < bt2.ElemNum; ++i) {
bt2.SqBiTNode[i] = a2[i];
}
int ans2 = isValidBST(bt2);
if (ans2 == true) {
printf("T2 is a binary search tree\n");
} else {
printf("T2 is not a binary search tree\n");
}
return 0;
}
复杂度分析
- 时间复杂度： O(n) ，其中 n 为二叉树的结点个数。在递归调用的时候二叉树的每个结点最多被访问一次，因此时间复杂度为 O(n) 。
- 空间复杂度： O(n) ，其中 n 为二叉树的结点个数。递归函数在递归过程中需要为每一层递归函数分配栈空间，所以这里需要额外的空间且该空间取决于递归的深度，即二叉树的高度。最坏情况下二叉树为一条链，树的高度为 n ，递归最深达到 n 层，故最坏情况下空间复杂度为 O(n) 。
方法二：中序遍历
利用二叉搜索树的性质的推论：中序遍历为单调递增序列。
递归遍历：
考虑保存整个中序遍历序列，最后进行检查。
C代码如下（含测试用例）：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_SIZE 20011
#define false 0
#define true 1
typedef int bool;
typedef struct { // MAX_SIZE为已定义常量
int SqBiTNode[MAX_SIZE]; // 保存二叉树结点值的数组
int ElemNum; // 实际占用的数组元素个数
}SqBiTree;
void inorder(SqBiTree T, int i, int *a, int *j) {
if (i >= T.ElemNum || T.SqBiTNode[i] == -1) { // 越界或者为空结点
return;
}
inorder(T, 2 * i + 1, a, j);
a[(*j)++] = T.SqBiTNode[i];
inorder(T, 2 * i + 2, a, j);
}
bool isValidBST(SqBiTree T){
int *a = (int *)malloc(sizeof(int) * MAX_SIZE);
int j = 0;
inorder(T, 0, a, &j);
for(int k = 0; k < j - 1; k++) {
if(a[k] >= a[k + 1]) {
return false;
}
}
return true;
}
int main() {
int a1[10] = {40, 25, 60, -1, 30, -1, 80, -1, -1, 27};
SqBiTree bt1;
memset(bt1.SqBiTNode, 0, sizeof(bt1.SqBiTNode));
bt1.ElemNum = 10;
for (int i = 0; i < bt1.ElemNum; ++i) {
bt1.SqBiTNode[i] = a1[i];
}
int ans1 = isValidBST(bt1);
if (ans1 == true) {
printf("T1 is a binary search tree\n");
} else {
printf("T1 is not a binary search tree\n");
}
int a2[11] = {40, 50, 60, -1, 30, -1, -1, -1, -1, -1, 35};
SqBiTree bt2;
memset(bt2.SqBiTNode, 0, sizeof(bt2.SqBiTNode));
bt2.ElemNum = 11;
for (int i = 0; i < bt2.ElemNum; ++i) {
bt2.SqBiTNode[i] = a2[i];
}
int ans2 = isValidBST(bt2);
if (ans2 == true) {
printf("T2 is a binary search tree\n");
} else {
printf("T2 is not a binary search tree\n");
}
return 0;
}
复杂度分析
- 时间复杂度： O(n) ，其中 n 为二叉树的结点个数。二叉树的每个结点最多被访问三次，因此时间复杂度为 O(n) 。
- 空间复杂度： O(n) ，其中 n 为二叉树的结点个数。递归栈最深为 n ，中序遍历数组大小为 n ，因此需要额外的 O(n) 的空间。
优化空间复杂度，使用一个变量 prev 记录前驱。由于非空二叉树T的结点值均为正数，初始化 prev=0 。
C代码如下（含测试用例）：
#include <stdio.h>
#include <string.h>
#define MAX_SIZE 20011
#define false 0
#define true 1
typedef int bool;
typedef struct { // MAX_SIZE为已定义常量
int SqBiTNode[MAX_SIZE]; // 保存二叉树结点值的数组
int ElemNum; // 实际占用的数组元素个数
}SqBiTree;
bool inorder(SqBiTree T, int i, int* prev) {
if (i >= T.ElemNum || T.SqBiTNode[i] == -1) { // 越界或者为空结点
return true;
}
if (!inorder(T, 2 * i + 1, prev)) {
return false;
}
if (prev > T.SqBiTNode[i]) {
return false;
}
prev = T.SqBiTNode[i];
return inorder(T, 2 * i + 2, prev);
}
bool isValidBST(SqBiTree T) {
int prev = 0;
return inorder(T, 0, prev);
}
int main() {
int a1[10] = {40, 25, 60, -1, 30, -1, 80, -1, -1, 27};
SqBiTree bt1;
memset(bt1.SqBiTNode, 0, sizeof(bt1.SqBiTNode));
bt1.ElemNum = 10;
for (int i = 0; i < bt1.ElemNum; ++i) {
bt1.SqBiTNode[i] = a1[i];
}
int ans1 = isValidBST(bt1);
if (ans1 == true) {
printf("T1 is a binary search tree\n");
} else {
printf("T1 is not a binary search tree\n");
}
int a2[11] = {40, 50, 60, -1, 30, -1, -1, -1, -1, -1, 35};
SqBiTree bt2;
memset(bt2.SqBiTNode, 0, sizeof(bt2.SqBiTNode));
bt2.ElemNum = 11;
for (int i = 0; i < bt2.ElemNum; ++i) {
bt2.SqBiTNode[i] = a2[i];
}
int ans2 = isValidBST(bt2);
if (ans2 == true) {
printf("T2 is a binary search tree\n");
} else {
printf("T2 is not a binary search tree\n");
}
return 0;
}
复杂度分析
- 时间复杂度： O(n) ，其中 n 为二叉树的结点个数。二叉树的每个结点最多被访问三次，因此时间复杂度为 O(n) 。
- 空间复杂度： O(n) ，其中 n 为二叉树的结点个数。递归栈最深为 n ，因此需要额外的 O(n) 的空间。
迭代遍历：
迭代遍历是对递归遍历的改进，如果中途检测到不符合二叉搜索树性质，可以直接终止，加速程序运行，但无法降低算法时间复杂度。
C代码如下（含测试用例）：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#define MAX_SIZE 20011
#define false 0
#define true 1
typedef int bool;
typedef struct { // MAX_SIZE为已定义常量
int SqBiTNode[MAX_SIZE]; // 保存二叉树结点值的数组
int ElemNum; // 实际占用的数组元素个数
}SqBiTree;
bool isValidBST(SqBiTree T) {
int *stk = (int *)malloc(sizeof(int) * MAX_SIZE);
int top = 0; // 栈顶指针
int prev = -1; // 初始前驱下标
int curr = 0; // 初始指向根结点
while (top > 0 || (curr < T.ElemNum && T.SqBiTNode[curr] != -1)) {
while (curr < T.ElemNum && T.SqBiTNode[curr] != -1) {
stk[top++] = curr;
curr = curr * 2 + 1;
}
curr = stk[--top];
// 如果中序遍历得到的结点的值小于前驱，说明不是二叉搜索树
if (T.SqBiTNode[curr] < (prev == -1 ? INT_MIN : T.SqBiTNode[prev])) {
return false;
}
prev = curr;
curr = curr * 2 + 2;
}
return true;
}
int main() {
int a1[10] = {40, 25, 60, -1, 30, -1, 80, -1, -1, 27};
SqBiTree bt1;
memset(bt1.SqBiTNode, 0, sizeof(bt1.SqBiTNode));
bt1.ElemNum = 10;
for (int i = 0; i < bt1.ElemNum; ++i) {
bt1.SqBiTNode[i] = a1[i];
}
int ans1 = isValidBST(bt1);
if (ans1 == true) {
printf("T1 is a binary search tree\n");
} else {
printf("T1 is not a binary search tree\n");
}
int a2[11] = {40, 50, 60, -1, 30, -1, -1, -1, -1, -1, 35};
SqBiTree bt2;
memset(bt2.SqBiTNode, 0, sizeof(bt2.SqBiTNode));
bt2.ElemNum = 11;
for (int i = 0; i < bt2.ElemNum; ++i) {
bt2.SqBiTNode[i] = a2[i];
}
int ans2 = isValidBST(bt2);
if (ans2 == true) {
printf("T2 is a binary search tree\n");
} else {
printf("T2 is not a binary search tree\n");
}
return 0;
}
复杂度分析
- 时间复杂度： O(n) ，其中 n 为二叉树的结点个数。二叉树的每个结点最多被访问三次，因此时间复杂度为 O(n) 。
- 空间复杂度： O(n) ，其中 n 为二叉树的结点个数。栈最多存储 n 个结点，因此需要额外的 O(n) 的空间。
Morris遍历：
Morris遍历是对迭代遍历的进一步优化。
Morris是就是著名的计算机科学家J.H.Morris，他还与D.E.Knuth和V.R.Pratt一起提出了KMP算法。
Morris中序遍历伪代码如下：
PRINT-BINARY-TREE(T)
x = T.root
y = NIL // rightmost node in x's left subtree
while x ≠ NIL
y = x.left
if y ≠ NIL
while y.right ≠ NIL and y.right ≠ x
y = y.right
if y.right == NIL
y.right = x
x = x.left
continue
else y.right = NIL
print x.key
x = x.right
本质是构造出类似中序遍历线索二叉树的二叉树，构造线索指向后继（下图中用虚线表示）。但注意，若能通过二叉树的孩子指针找到后继的线索（例如二叉树T1中关键字25所在结点到关键字27所在结点的线索），则该线索无需构造，如下图所示：
二叉树静态数组的Morris遍历难度比指针结点表示的二叉树大，由于没有空指针和指针变换，考虑用空结点记录中序遍历后继指针指向。为了区分指针和数字，且避开缺省值-1，下标值从-2开始储存。因为这里所有元素为正，即 x.key≥1 ，我们要存储下标，因为树不为空，所以 y.right 的下标大于等于0，要避开所有正数和缺省-1，结构体SqBiTNode数组中没有填充的部分默认为0，也要完美避开，存负的下标值-2，这样就符合小于等于-2，正好没有产生任何冲突。
由于 x 左子树的最右结点不可能右孩子，所以完全可以直接用空结点存储中序遍历后继结点下标，但是如果是需要记录会发生冲突的线索比如后序遍历的后继线索，这样做就会出现冲突，一旦出现冲突，就需要开辟 O(n) 的数组记录。用静态数组表示的二叉树的Morris遍历的空间复杂度为 O(1) 不简单是巧合。
修改指针这部分是真的复杂，目前想到的办法通过正负号来区分里面存的是下标还是元素值，保证此算法是一个原地算法。这个思路可以参考2018年第41题，其最优解为原地哈希，都是运用负号进行标记，两者原地构造存储有异曲同工之妙。
这里默认MAX_SIZE足够大，不会造成记录后继指针指向时数组越界。
C代码如下（含测试用例）：
#include <stdio.h>
#include <string.h>
#define MAX_SIZE 20011
#define false 0
#define true 1
typedef int bool;
typedef struct { // MAX_SIZE为已定义常量
int SqBiTNode[MAX_SIZE]; // 保存二叉树结点值的数组
int ElemNum; // 实际占用的数组元素个数
}SqBiTree;
bool isValidBST(SqBiTree T) {
int prev = -1; // 前驱结点下标，初始化为NIL
int x = 0; // 初始指向根结点下标，初始化为根结点下标 x = T.root
int y = -1; // x 左子树的最右结点下标，初始化为NIL y = NIL
while (x < T.ElemNum && T.SqBiTNode[x] != -1) { // while x != NIL
y = 2 * x + 1; // y = x.left
if (y < T.ElemNum && T.SqBiTNode[y] != -1) { // if y != NIL
while (T.SqBiTNode[2 * y + 2] != -1 && T.SqBiTNode[2 * y + 2] != 0 && -T.SqBiTNode[2 * y + 2] - 2 != x) { // while (y.right != NIL && y.right != x)
y = T.SqBiTNode[2 * y + 2] < -1 ? -T.SqBiTNode[2 * y + 2] - 2 : 2 * y + 2; // y = y.right
}
if (T.SqBiTNode[2 * y + 2] == -1 || T.SqBiTNode[2 * y + 2] == 0) { // if (y.right == NIL)
T.SqBiTNode[2 * y + 2] = -(x + 2); // y.right = x
x = 2 * x + 1; // x = x.left
continue;
} else {
T.SqBiTNode[2 * y + 2] = -1; // y.right = NIL
}
}
if (T.SqBiTNode[x] < (prev == -1 ? -MAX_SIZE : T.SqBiTNode[prev])) { // 比较当前结点和前驱结点的值检查是否违反二叉搜索树性质
return false;
}
prev = x; // 更新前驱结点下标
x = T.SqBiTNode[2 * x + 2] < -1 ? -T.SqBiTNode[2 * x + 2] - 2 : 2 * x + 2; // x = x.right
}
return true;
}
int main(int argc, const char * argv[]) {
int a1[10] = {40, 25, 60, -1, 30, -1, 80, -1, -1, 27};
SqBiTree bt1;
memset(bt1.SqBiTNode, 0, sizeof(bt1.SqBiTNode));
bt1.ElemNum = 10;
for (int i = 0; i < bt1.ElemNum; ++i) {
bt1.SqBiTNode[i] = a1[i];
}
int ans1 = isValidBST(bt1);
if (ans1 == true) {
printf("T1 is a binary search tree\n");
} else {
printf("T1 is not a binary search tree\n");
}
int a2[11] = {40, 50, 60, -1, 30, -1, -1, -1, -1, -1, 35};
SqBiTree bt2;
memset(bt2.SqBiTNode, 0, sizeof(bt2.SqBiTNode));
bt2.ElemNum = 11;
for (int i = 0; i < bt2.ElemNum; ++i) {
bt2.SqBiTNode[i] = a2[i];
}
int ans2 = isValidBST(bt2);
if (ans2 == true) {
printf("T2 is a binary search tree\n");
} else {
printf("T2 is not a binary search tree\n");
}
return 0;
}
复杂度分析
- 时间复杂度： O(n) ，其中 n 为二叉树的结点个数。二叉树的每个结点最多被访问三次，因此时间复杂度为 O(n) 。
- 空间复杂度： O(1) ，中间过程额外需要常数个变量。
The road of your choice, you have to go on !
粤ICP备16082171号-1
登录后提交答案
暂无评论，来抢沙发