Бинарное дерево поиска на C/C++

#c #алгоритм #бинарное_дерево #дерево #cpp

Есть задачка. Имеется бинарное дерево. Требуется определить, является ли это дерево
бинарным деревом поиска. Желательно представить решение на языке С++ или С. Оцениваются
временная и пространственная сложность алгоритма, а так же универсальность подхода.    

Ответы

Ответ 1

UPD: моя неправда, исправляю.
Предположим, что дерево определено так:
struct BinaryTreeNode {
    BinaryTreeNode(int val) : leftChild(NULL), rightChild(NULL), 
        parent(NULL), value(val) {}

    BinaryTreeNode * leftChild;
    BinaryTreeNode * rightChild;
    BinaryTreeNode * parent;
    int value;
};

Тогда алгоритм проверки будет следующим:
bool isBST(BinaryTreeNode * root)
{
    return isBST_(root, 0, 0);
}

bool isBST_(BinaryTreeNode * node, BinaryTreeNode * minParent, BinaryTreeNode * maxParent)
{
    if (minParent && minParent->value >= node->value)
        return false;
    if (maxParent && maxParent->value <= node->value)
        return false;
    if (node->leftChild != 0 && !isBST_(node->leftChild, minParent, node))
        return false;
    if (node->rightChild != 0 && !isBST_(node->rightChild, node, maxParent))
        return false;
    return true;    
}

Временная сложность O(n), где n — количество узлов в дереве. Пространственная сложность
O(h), где h — глубина дерева.


Ответ 2

http://www.structur.h1.ru/derevo.htm - тут написанна структура дерева
по сути ваша задача хорошо решается рекурсией рекурсивно идете вниз по дереву если
при проверке оказывается что это не дерево - throw SomeError; если все нормально -
то никаких исключений кидать не надо рекурсия развернется свернется и говорите что все ОК


Ответ 3

Обходим дерево по правилу ЛКП, по дороге проверяем, получается ли возрастающая последовательность
(или убывающая, можно определить по первым двум неравным значениям). Если не получается
- то не дерево поиска. Как то так.