Реализация на дърво чрез структури

Ето една примерна реализация на дърво чрез структура:

#include <cstdlib>
#include <iostream>

using namespace std;

// структура, която съхранява данните за един елемент
struct tree {
    int value;
    tree* parent;
    tree* left;
    tree* right;
};

// добавя елемент в дървото
void insert_tree(tree* &t, int value, tree* parent) {
    tree* p;

    // ако добавяме на върха на дървото
    if (t == NULL) {
        p = new tree;
        p->left = p->right = NULL;
        p->parent = parent;
        p->value = value;
        t = p;
    }

    // добавяне в съответното поддърво
    else if (value < t->value)
        insert_tree(t->left, value, t);
    else
        insert_tree(t->right, value, t);

}

// търсене на стойност в дървото
tree* search_tree(tree* t, int i) {
    // ако няма дърво, няма какво да търсиме
    if (t == NULL) return NULL;
    // ако сме попаднали на точният елемент - също
    if (t->value == i) return t;
    // търсим в съответното поддърво
    if (i < t->value) {
        return search_tree(t->left, i);
    } else {
        return search_tree(t->right, i);
    }
}

// намиране на най-малка стойност
tree* find_min(tree* t) {
    // ако няма дърво, няма какво да търсиме
    if (t == NULL) return NULL;
    // намираме най-левия елемент
    tree *min = t;
    while (min->left != NULL) {
        min = min->left;
    }
    return min;
}

// изтриване на елемент
void delete_element(tree* &t, int value) {
    // ако няма дърво, няма какво да изтриваме
    if (t == NULL) return;
    // намираме каквото ни трябва
    tree* element = search_tree(t, value);
    // ако няма такъв елемент, до тук сме
    if (element == NULL) return;
    // проверка има ли родител
    int hasParent = element->parent != NULL;
    // проверка дали е ляв наследник
    int isLeft = hasParent && element->value < element->parent->value;
    // ако елемента няма деца е лесно - изчистваме само указателя при родителя
    if (element->left == NULL && element->right == NULL) {
        if (hasParent) {
            if (isLeft) {
                element->parent->left = NULL;
            } else {
                element->parent->right = NULL;
            }
        }
        delete element;
    }
    // има само наследници отляво, свързваме наследника с родителя
    else if (element->left != NULL && element->right == NULL) {
        element->left->parent = element->parent;
        if (hasParent) {
            if (isLeft) {
                element->parent->left = element->left;
            } else {
                element->parent->right = element->left;
            }
        }
        // наследника е новият корен на дървото
        else {
            t = element->left;
        }
        delete element;
    }
    // има само родител отдясно, свързваме наследника с родителя
    else if (element->left == NULL && element->right != NULL) {
        element->right->parent = element->parent;
        if (hasParent) {
            if (isLeft) {
                element->parent->left = element->right;
            } else {
                element->parent->right = element->right;
            }
        }
        // наследника е новият корен на дървото
        else {
            t = element->right;
        }
        delete element;
    }
    // ако има два наследника, намираме най-малкия в дясното поддърво
    else {
        tree* right_min = find_min(element->right);
        // нашият ще е със стойността му
        element->value = right_min->value;
        // изтриваме най-малкия отдясно
        delete_element(right_min, right_min->value);
    }
}

// обработка на възел при обхождане - в случая отпечатваме възела,
// но може да е и произволна друга операция със стойността му
void process_node(int value) {
    cout<<value<<' ';
}

// inorder обхождане на дърво – посещаване на лявото поддърво, корена и дясното поддърво.
// при това обхождане стойностите са в нарастващ ред
void traverse_tree_inorder(tree* t) {
    if (t == NULL) return;
    traverse_tree_inorder(t->left);
    process_node(t->value);
    traverse_tree_inorder(t->right);
}

// preorder обхождане на дърво – посещаване на корена, лявото поддърво и дясното поддърво.
void traverse_tree_preorder(tree* t) {
    if (t == NULL) return;
    process_node(t->value);
    traverse_tree_preorder(t->left);
    traverse_tree_preorder(t->right);
}

// postorder обхождане на дърво – посещаване на лявото поддърво, дясното поддърво и корена.
void traverse_tree_postorder(tree* t) {
    if (t == NULL) return;
    traverse_tree_postorder(t->left);
    traverse_tree_postorder(t->right);
    process_node(t->value);
}

int main()
{
    // създаваме празно дърво
    tree* t = NULL;

    // добавяме елементи в него
    int n;
    cout<<"Vavedete broi na elementite: ";
    cin>>n;
    cout<<"Vavedete "<<n<<" chisla, koito da zapisha v darvoto: ";
    int value;
    for(int i=0; i<n; i++) {
      cin>>value;
      insert_tree(t, value, t);
    }

    // отпечатване на елементите
    cout<<"print inorder: "; traverse_tree_inorder(t); cout<<endl;
    cout<<"print preorder: "; traverse_tree_preorder(t); cout<<endl;
    cout<<"print postorder: "; traverse_tree_postorder(t); cout<<endl;

    // намиране на най-малка стойност
    tree* node = find_min(t);
    if(node)
      cout<<"Nai-malkata stoinonst e "<<node->value<<endl;

    // намиране на произволна стойност
    cout<<"Vavedete chislo, koeto da potarsia:";
    cin>>value;
    node=search_tree(t, value);
    if(node)
      if(node->parent)
        cout<<"Namereno e, roditel mu e "<<node->parent->value<<endl;
      else
        cout<<"Namereno e, namira se v korena na darvoto"<<endl;
    else cout<<"Niama takava stoinost v darvoto"<<endl;

    // изтриване на произволна стойност
    cout<<"Vavedete chislo, koeto da iztriya:";
    cin>>value;
    delete_element(t, value);

    // отпечатване на елементите
    cout<<"print inorder: "; traverse_tree_inorder(t); cout<<endl;
    cout<<"print preorder: "; traverse_tree_preorder(t); cout<<endl;
    cout<<"print postorder: "; traverse_tree_postorder(t); cout<<endl;

    return 0;
}
Публикувано в 12а, 12в с етикети . Постоянна връзка.

Вашият коментар