已知非空二叉树T的结点值均为正整数，采用顺序存储方式保存，数据结构定义如下：_

[数据结构 P2014] 已知非空二叉树T的结点值均为正整数，采用顺序存储方式保存，数据结构定义如下：

学习人数: 685

正确率: ??%

题目描述

未通过

已知非空二叉树T的结点值均为正整数，采用顺序存储方式保存，数据结构定义如下：

typedef struct {                    // MAX_SIZE为已定义常量
    Elemtype SqBiTNode[MAX_SIZE];   // 保存二叉树结点值的数组
    int ElemNum;                    // 实际占用的数组元素个数
}SqBiTree;

T中不存在的结点在数组SqBiTNode中用-1表示。例如，对于下图所示的两棵非空二叉树T1和T2：

请设计一个尽可能高效的算法，判定一棵采用这种方式存储的二叉树是否为二叉搜索树，若是，则返回true，否则，返回false，要求：

⑴ 给出算法的基本设计思想。

⑵ 根据设计思想，采用C或C++语言描述算法，关键之处给出注释。

上一题

下一题

加入错题本

个人笔记

已有1条笔记

登录后提交答案

暂无评论，来抢沙发

参考答案

解答：

注意本题二叉树以静态...

用户登录可进行刷题及查看答案

解答：

注意本题二叉树以静态数组的方式表示，数组起始下标为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) ，中间过程额外需要常数个变量。