Проверьте, является ли дерево двоичным деревом поиска, используя inorder - PullRequest
Новая
       8

Проверьте, является ли дерево двоичным деревом поиска, используя inorder

0 голосов
/ 27 июня 2018 
int* inorder(node* root)
{
    //Dynamically Created array as we are required to pass array into main function
    int* arr=new int[100];
    int i=0;
    if(root==NULL)
    return 0;
    inorder(root->left);
    arr[i]=root->data;
    i++;
    inorder(root->right);
    return arr;
}

Мы должны проверить, является ли дерево Bst или нет, используя обход Inorder. Если данные, присутствующие в массиве, отсортированы, то это Bst. После передачи массива в main () мы проверим, отсортирован ли массив или нет, но , когда я проверил содержимое массива, оно оказалось мусорным значением и дерево всегда оказывается не Bst для входного дерева, которое BST 

int main()
{
    node* root= newNode(6);
    root->left= newNode(4);
    root->right= newNode(8);
    root->left->left= newNode(3);
    root->left->right= newNode(5);
    root->right->left= newNode(7);
    root->right->right= newNode(9);
    int* ptr=inorder(root);
    if(is_sorted(ptr,ptr+7))
    cout<<"Tree is Binary search tree: "<<endl;
    else
    cout<<"Tree is not a binary search tree: "<<endl;
}

1 Ответ

0 голосов
/ 27 июня 2018

Использование вектора здесь не нужно. Определение того, является ли дерево двоичным деревом поиска, не требует дополнительной памяти, кроме стека для рекурсивных вызовов.

Если вы определяете отдельный алгоритм обхода дерева порядков, который делает реализацию почти тривиальной: 

#include <utility>
#include <functional>

template<class T>
struct Node {
    T value;
    Node *left, *right;
};

template<class T, class F>
bool traverse_inorder(Node<T> const* tree, F&& f) {
    return !tree || (
           traverse_inorder(tree->left, std::forward<F>(f))
        && f(tree->value)
        && traverse_inorder(tree->right, std::forward<F>(f))
        );
}

template<class T, class Pred>
bool is_bst(Node<T> const* tree, Pred&& pred) {
    T const* p = 0;
    return traverse_inorder(tree, [&p, &pred](T const& next) {
        T const* prev = p;
        p = &next;
        return !prev || !pred(next, *prev);
    });
}

template<class T>
bool is_bst(Node<T> const* tree) {
    return is_bst(tree, std::less<T>{});
}

int main() {
    // bst tree:
    //       33
    //   20      35
    // 10  30
    Node<int> n1{10}, n3{30}, n2{20, &n1, &n3}, n5{35}, n4{33, &n2, &n5};
    auto tree = &n4;

    std::cout << is_bst(tree) << '\n'; // Outputs 1.

    // Break bst property.
    n4.value = 25;
    std::cout << is_bst(tree) << '\n'; // Outputs 0.
}

Чтобы преобразовать дерево в вектор с помощью обхода по порядку, вы можете использовать следующую функцию: 

template<class T>
std::vector<T> inorder_to_vector(Node<T> const* tree) {
    std::vector<T> v;
    traverse_inorder(tree, [&v](T const& t) {
        v.push_back(t);
        return true;
    });
    return v;
}
...