Бинарное дерево на C++ - C++ - Ответ 13460270

#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();