来自预序遍历的二进制搜索树以及关于左右节点的信息

Question

需要验证给定的前序遍历是否是BST？输入是包含二叉树的前序遍历的文件，以及节点是否有左、右、两个子节点或没有子节点。例如

-2 3
-4 3
-5 0
-3 0
 2 3
 0 3
-1 0
 1 0
 5 1
 4 0

表示“-2”节点同时具有左子节点和右子节点。“-5”没有子项。基本上

0 -> no children
1 -> right child
2 -> left child
3 -> both Children

这是无法修改的节点结构

    typedef struct _Tnode {
       int key;
       int height;
       struct _Tnode *left;
       struct _Tnode *right;
    } Tno

PS:在这个例子中，它不是BST。我可以用它来构建一棵树，就像这样

                            -2 
                          /    \
                        /        \
                      -4          2
                      / \        /  \
                    -5   -3     0    5
                               / \    \
                             -1   1    4

Answer 1

您可以使用递归函数来解析输入并检查每个值是否在可接受的范围内。实际上并不需要使用 Tno 类型实际构建树：

#include <stdio.h>
#include <limits.h>

int isBST(min, max) {
    int value, flags;
    scanf("%d %d", &value, &flags);
    if (value < min || value > max) return 0;
    if ((flags > 1) && !isBST(min, value)) return 0;
    if ((flags % 2 > 0) && !isBST(value, max)) return 0;
    return 1;
}

int main(void) {
    int result = isBST(INT_MIN, INT_MAX);
    if (result) printf("This BST is fine\n");
    else        printf("Not a valid BST\n");
    return 0;
}

如果您需要构建树，然后才验证它是否是BST，那么您可以通过以下方式执行此操作：

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

typedef struct _Tnode {
    int key;
    int height;
    struct _Tnode *left;
    struct _Tnode *right;
} Tno;

Tno* createNode(int key) {
    Tno* node = malloc(sizeof(Tno));
    node->key = key;
    node->left = node->right = NULL;
    return node;
}

Tno* discardTree(Tno* node) {
    if (node == NULL) return NULL;
    discardTree(node->left);
    discardTree(node->right);
    free(node);
    return NULL;
}

Tno* createTreeFromInput() {
    int value, flags;
    scanf("%d %d", &value, &flags);
    Tno* node = createNode(value);
    if (flags > 1) node->left = createTreeFromInput();
    if (flags % 2 > 0) node->right = createTreeFromInput();
    return node;
}

int isBST(Tno* node, int min) {
    if (node == NULL) return min;
    if (node->key < min) return INT_MAX; // Indication of error
    min = isBST(node->left, min);
    if (min > node->key) return INT_MAX;
    return isBST(node->right, node->key);
}

int main(void) {
    Tno* root = createTreeFromInput();
    int ok = isBST(root, INT_MIN) < INT_MAX;
    if (ok) printf("This BST is fine\n");
    else    printf("Not a valid BST\n");
    discardTree(root);
    return 0;
}