Бинарное дерево на C++

@svagafox · Регистрация: 21.09.2017

Доброго времени суток. Выношу себе мозг с реализацией этого дерева уже несколько дней.

Прошу помощи.

Задание:

Реализовать BST (Binary Search Tree).

Дерево должно быть шаблонизировано - нужно продемонстрировать работу на хотя бы значениях int, double, string.

Нужно реализовать операции добавления элемента и поиска элемента.

Нужно реализовать автоматическую балансировку.
Для демонстрации ее работы в пустое дерево добавляем последовательно значения от 0 до 30 и выводим дерево в консоль/svg.
Глубина каждой ветки не должна быть больше 5.

Вывод дерева в консоль/svg

Свой код я прикрепляю к теме. Помогите, пожалуйста, добить это.

C++

#include <iostream>
 
 
 
 
using namespace std;
 
 
class btree {
 
    struct node {
        int value;
        unsigned char height;
        node *left;
        node *right;
        node(int v) { value = v; left = right = 0; height = 1;}
    }; /// структура для представления узлов дерева
 
    node* rotateright(node* y){
        node* x = y->left;
        y->left = x->right;
        x->right = y;
        fixheight(y);
        fixheight(x);
        return x;
    } /// правый поворот вокруг y
 
    node* rotateleft(node* x){
        node* y = x->right;
        x->right = y->left;
        y->left = x;
        fixheight(x);
        fixheight(y);
        return y;
    } /// левый поворот вокруг x
 
    node* balance(node* leaf){
        fixheight(leaf);
        if( balancefactor(leaf)==2 )
        {
            if( balancefactor(leaf->right) < 0 )
                leaf->right = rotateright(leaf->right);
            return rotateleft(leaf);
        }
        if( balancefactor(leaf)==-2 )
        {
            if( balancefactor(leaf->left) > 0  )
                leaf->left = rotateleft(leaf->left);
            return rotateright(leaf);
        }
        return leaf;
    } /// Балансировка узла
 
    node *root;
 
    node* clear_tree(node *leaf){
        if (leaf != nullptr) {
            clear_tree(leaf->left);
            clear_tree(leaf->right);
            delete leaf;
        }
    } /// Очистка дерева
 
    node* insert(node* leaf, int x){
        if( !leaf ) return new node(x);
        if( x<leaf->value )
            leaf->left = insert(leaf->left,x);
        else
            leaf->right = insert(leaf->right,x);
        return balance(leaf);
    }/// Вставка значений
 
    node* search(int key, node *leaf){
        if (leaf != nullptr) {
            if (key == leaf->value) {
                cout << "There is" << " " << key << endl;
                return leaf;
 
            }
            if (key < leaf->value) {
                return search(key, leaf->left);
            } else {
                return search(key, leaf->right);
            }
        } else {
            cout << "There is no" << " " << key << endl;
            return nullptr;
        }
    } /// Поиск значений
 
    unsigned char height(node* leaf){
        return static_cast<unsigned char>(leaf ? leaf->height : 0);
    }
 
    int balancefactor(node* leaf){
        return height(leaf->right)-height(leaf->left);
    }
 
    void fixheight(node* leaf){
        unsigned char hl = height(leaf->left);
        unsigned char hr = height(leaf->right);
        leaf->height = static_cast<unsigned char>((hl > hr ? hl : hr) + 1);
    }
 
    void inorder_print(node* leaf) {
        if (leaf == nullptr)
            return;
        inorder_print(leaf->left);
        cout << leaf->value << " ";
        inorder_print(leaf->right);
 
    }
 
    void preorder_print(node* leaf) {
        if (leaf != nullptr) {
            cout << leaf->value << " ";
            inorder_print(leaf->left);
            inorder_print(leaf->right);
        }
        else
            cout << "There is no trees" << endl;
    }
 
public:
    btree(){
        root= nullptr;
    }
 
    ~btree(){
        root=clear_tree(root);
    }
 
    void insert(int key) {
        root=insert(root, key);
        }
 
    void preorder_print() {
        preorder_print(root);
        cout << "\n";
    }
 
    void inorder_print() {
        inorder_print(root);
        cout << endl;
    }
 
    void search(int key) {
        root = search(key, root);
    }
 
    int Height(node* leaf){
        int left, right;
 
        if(leaf == nullptr)
            return 0;
        left = Height(leaf->left);
        right = Height(leaf->right);
        if(left > right)
            return left+1;
        else
            return right+1;}
 
    void clear_tree() {
        clear_tree(root);
    }
 
};
 
 
int main(){
 
  btree t;
    for (int i = 0; i <= 30; ++i) {
        t.insert(i);
    }
  t.inorder_print();
  t.preorder_print();
 t.search(16);
 t.search(55);
 t.search(5);
 
 
 t.clear_tree();
 t.preorder_print();

@JesD · 04.04.2019, 00:15

При реализации прямого обхода, у вас, вместо рекурсивного вызова этой же функции, вызывается функция симметричного обхода:

C++

void preorder_print(node* leaf) {
        if (leaf != nullptr) 
       {
            cout << leaf->value << " ";
            inorder_print(leaf->left); // имелось ввиду preorder_print ?
            inorder_print(leaf->right); // имелось ввиду preorder_print ?
        }
        else
            cout << "There is no trees" << endl;
    }

Еще момент:

C++

void preorder_print(node* leaf) {
        if (leaf != nullptr) {
            cout << leaf->value << " ";
            inorder_print(leaf->left);
            inorder_print(leaf->right);
        }
        else
            cout << "There is no trees" << endl;
    }

Непонятно, зачем выводить сообщение "*There is no trees". Дело в том, что каждый раз когда функция доходит до конца ветки, leaf становится nullptr. Однако это не означает то, что работа функции preorder_print окончательно завершиться. Это будет означать, что она напечатает вам эту ерунду, потом из стека вызовов будет использована следующая функция, которая дальше пойдет по другой ветке, и так будет повторяться до тех пор, пока не будут пройдены все ветки. Уберите этот блок кода вообще, и все нормально будет выводиться)

C++

1 2	else cout << "There is no trees" << endl;

Ну или найдите ему адекватные альтернативы.

Проблема с поиском уже не так проста) Дело в том, что указателю root, после выполнения функции поиска, каждый раз присваивается адрес искомого узла. Когда вы вызовете функцию поиска для ключа 55, этого ключа найдено не будет, и указателю на корень дерева будет присвоен nullptr.

Затем вы попытаетесь найти элемент с ключом 5, и получите следующее:

C++

void search(int key)
{
        root = search(key, root); // но здесь уже root = nullptr
}

Так как root = nullptr, то при заходе в функцию поиска по дереву, вас сразу же из него выкинет:

C++

if (leaf != nullptr)
{
... // тут должен был быть поиск
}
else
{
      cout << "There is no" << " " << key << endl;
      return nullptr; // но мы попали сюда
}

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

C++

node* searchElement;
void search(int key)
{
    searchElement = search(key, root); // ok: получили указатель на искомый узел, но при этом корень дерева остался неизменным
}

Так все будет работать)

Опции темы