Указатель на корень двоичного дерева

Question

Дан указатель на корень двоичного дерева Опишите словами алгоритм, который вернёт True если дерево является двоичным деревом поиска и False если не является

Вершина дерева содержит целочисленное значение (value) и два указателя на поддеревья (left и right).

В виде структуры на языке C это можно записать так:

struct node { int value; node* left; node* right; }

Answer 1

в бинаром дереве поиска правое значение больше текущего, а левое значение меньше текущего, так же нет повторений. чтобы проверить что бинарное дерево является бинарным деревом поиска тебе надо написать рекурсивный алгоритм который проверяет эти три условия. на си я бы сделал это так:

    C:
    struct node {
        int val;
        struct node *left;
        struct node *right;
    };

    bool is_binary_search_tree( struct node *root ) {
        if ( !root || ( !root->left && !root->right ) ) return true;
        if ( root->left && root->left->val >= root->val ) return false;
        if ( root->right && root->right->val <= root->val ) return false;
       return is_binary_search_tree( root->left ) && is_binary_search_tree( 
    root->right );
   }

взято с сайта https://www.blast.hk/threads/125931/

Answer 2

Читать снизу вверх:

typedef struct node node;
struct node {
    int value;
    node* left;
    node* right; 
};

/* дерево поиска в промежутке:
 * или пусто
 * или (  корень в промежутке
 *      и левое поддерево между меньшим концом промежутка и корнем
 *      и правое поддерево между корнем и большим концом промежутка)
 */
bool between(const node *tree, int low_value, int high_value) {
    if (tree == NULL) {
        return true;
    }
    return
                             low_value < tree->value               &&
                                         tree->value < high_value  &&
        between(tree->left , low_value,  tree->value             ) &&
        between(tree->right,             tree->value,  high_value);
}

/* дерево поиска меньше значения:
 * или пусто
 * или (  корень меньше значения
 *      и левое поддерево меньше корня
 *      и правое поддерево между корнем и значением)
 */
bool below(const node *tree, int high_value) {
    if (tree == NULL) {
        return true;
    }
    return
                             tree->value < high_value  &&
        below  (tree->left , tree->value             ) &&
        between(tree->right, tree->value,  high_value);
}

/* дерево поиска больше значения:
 * или пусто
 * или (  корень больше значения
 *      и левое поддерево между значением и корнем
 *      и правое поддерево больше корня)
 */
bool above(const node *tree, int low_value) {
    if (tree == NULL) {
        return true;
    }
    return
                             low_value < tree->value  &&
        between(tree->left , low_value,  tree->value) &&
        above  (tree->right,             tree->value);
}

/* дерево поиска:
 * или пусто
 * или (  левое поддерево меньше корня
 *      и правое поддерево больше корня)
 */
bool is_search_tree(const node *tree) {
    if (tree == NULL) {
        return true;
    }
    return
        below(tree->left , tree->value) &&
        above(tree->right, tree->value);
}

БЛОГ НА HUSL

Указатель на корень двоичного дерева

Ответы (2 шт):