0

Добрый вечер, вопрос следующий: есть элемент бинарного дерева

struct element{
    int info;
    element *left, *right, *parent;
};

никак не могу написать функцию заполнения дерева, трудность у меня заключается в указателе на родителя, никак не могу додуматься. Интересно было бы послушать ваши предложения

1
  • @skies, где-то в Вашей функции вставки нового узла должен быть примерно такой код: curnode->left = new_element; или curnode->right = new_element; По сути с этого момента новый узел стал частью дерева. Так вот, там же добавьте new_element->parent = curnode;
    – avp
    23 апр 2014 в 7:57

2 ответа 2

1

Когда ты идешь по дереву вниз (от корня) в поисках подходящего листа, чтобы прицепить свою info под ним, у тебя должен быть указатель на этот-самый лист. Его и записать в родители. Функция может выглядеть примерно так:

bool сreateNode(
    int     data,       // in
    Element *root,      // in
    Element **newNode   // out
)
{
    if ( root == nullptr )
        return false;

    Element *currentNode = root;

    //...
    // Допустим, тут цикл поиска необходимого листа,
    // который окажется в currentNode
    //...

    // Создаем новый элемент, заполняем информацией
    // "Родительский" указатель ссылается на найденный лист
    (*newNode) = new Element;
    (*newNode)->info = data;
    (*newNode)->left = (*newNode)->right = nullptr;
    (*newNode)->parent = currentNode;

    // Теперь "подвешиваем" новый элемент справа или слева
    // от родителя, в соответствии с условием сравнения
    if ( currentNode->info > data )
        currentNode->left = *newNode; 
    else
        currentNode->right = *newNode;

    return true; 
}

ЗЫ Проблему понять не могу, т.к. не вижу ваш вариант функции.

0
#include <iostream>
#include <cstdlib>
using namespace std;

struct element{
    int info;
    element *left, *right, *parent;
};

//добавление
int  tree_insert(element** tree, int info){
        element* p = *tree;
        element* t = NULL;
        while(p != NULL){
                t = p;
                if(info < p->info) {
                        tree = &p->left;
                        p    = p->left;
                } else {
                        if(info == p->info)
                                return 0;
                        tree = &p->right;
                        p    = p->right;
                }
        }
        if((p = new element()) != NULL){
                p->info   = info;
                p->left   = p->right = NULL;
                p->parent = t;
                *tree     = p;
        }
        return (p != NULL);
}

//проход по возрастанию
void  tree_print(std::ostream& _out, const element* p){
        const element* i;
        if(p == NULL)
                return;

        while(p->left != NULL)
                p = p->left;

        while(p != NULL) {
                _out << p->info << std::endl;
                if(p->right != NULL) {
                        i = p->right;
                        while(i->left != NULL)
                                i = i->left;
                } else {
                        i = p->parent;
                        while((i != NULL) && (p == i->right)) {
                                p = i;
                                i = i->parent;
                        }
                }
                p = i;
        }
}

int main(void){
        element* tree = NULL;

        for(int i = 0; i < 10; ++i)
                tree_insert(&tree, rand() % 20);

        tree_print(std::cout, tree);
        return 0;
}

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.