来自预序遍历的二叉搜索树以及有关左右节点的信息-解网

问：

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

表示“-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

c 数据结构二进制搜索树 AVL-树

#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;
}

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

Binary search tree from pre-order traversal and information about left and right nodes

评论

构建树

评论