Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > помогите создать бинарное дерево (4 указателя)

Автор: Podarochek 11.3.2008, 00:14

как создать бинарное дерево понятно...=>

struct tree{
    int Key;//полезные данные (ключ)
    tree *Left, *Right;//ссылки на сыновей
};

tree* MakeTree (tree*Tree,int data[], int &from, int n)
{

    int n1, n2;
    if ( n == 0 ) return NULL;//ограничение рекурсии
    Tree = new tree;//выделить память под вершину
    Tree->Key = data[from++];//записать данные и перейти к следующему элементу
    n1 = n / 2;//размеры левого
    n2 = n - n1 - 1;//и правого поддеревьев
    Tree->Left = MakeTree(Tree,data, from, n1);
    Tree->Right = MakeTree(Tree,data, from, n2);
    return Tree;
}

вопрос как создать дерево с четырмя указателями??? что-то не идет...:(

struct tree
{
    int val;
    tree *p[4]; // Массив указателей на элементы структур данных
};

Автор: bsa 11.3.2008, 00:30

передавать массивы да еще и в рекурсивных функциях очень неблагодарное занятие. Передавай лучше указатель:
tree* MakeTree (tree*Tree, const int *data, int &from, int n)

Автор: andrew_121 11.3.2008, 00:46

Podarochek, что-то я не очень понимаю - ЗАЧЕМ 4-ри ???

Автор: Podarochek 11.3.2008, 00:52

Цитата(bsa @ 11.3.2008, 00:30

)

??? так массивы по умолчанию передаются по ссылке...

Цитата(andrew_121 @ 11.3.2008, 00:46

)

Podarochek, что-то я не очень понимаю - ЗАЧЕМ 4-ри ???

с учебной целью...

Автор: andrew_121 11.3.2008, 01:00

У узла два указателя - на сыновей, а еще два на что должны указывать ???
Я думаю это возможно, но с какой целью, и что из этого получиться, бинарное дерево или мутант, какой-то...
Читай: http://ru.wikipedia.org/wiki/%D0%94%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE

Автор: Podarochek 11.3.2008, 01:05

Цитата(andrew_121 @ 11.3.2008, 01:00

)

У узла два указателя - на сыновей, а еще два на что должны указывать ???
Я думаю это возможно, но с какой целью, и что из этого получиться, бинарное дерево или мутант, какой-то...

Идет реч не о бинарном дереве, а о создании дерева с элементами с 4 потомками...не для практического приминения, а для эксперемента...пример бинарного дерева приведен выше...там все ок...

Автор: korian 11.3.2008, 03:46

если я правильно понял...

Код


struct tree
{
    int val;
    tree *p[4]; // Массив указателей на элементы структур данных
}; 

tree* MakeTree (tree*Tree,int data[], int &from, int n)
{
    
    int n1, n2, n3, n4;
    if ( n == 0 ) return NULL;//ограничение рекурсии
    Tree = new tree;//выделить память под вершину
    Tree->val = data[from++];//записать данные и перейти к следующему элементу
    n1 = n2 = n3 = n / 4; //размеры первого, второго, третьего
    n4 = n - n1 - n2 - n3 - 1; //четвертого
    Tree->p[0] = MakeTree(Tree,data, from, n1);
    Tree->p[1] = MakeTree(Tree,data, from, n2);
    Tree->p[2] = MakeTree(Tree,data, from, n3);
    Tree->p[3] = MakeTree(Tree,data, from, n4);
    return Tree;
}

Автор: Mayk 11.3.2008, 06:42

Цитата(Podarochek @ 11.3.2008, 04:52

)

??? так массивы по умолчанию передаются по ссылке...

Вообще это передача указателя а не ссылки. ЕМНИП это не менялось со времён форка от си.

Цитата(andrew_121 @ 11.3.2008, 05:00

)

У узла два указателя - на сыновей, а еще два на что должны указывать ???

Например на родителя.

Podarochek, заменил бы массив на std::vector<tree*> сразу smile

Автор: Podarochek 11.3.2008, 16:07

Цитата(Mayk @ 11.3.2008, 06:42

)

Вообще это передача указателя а не ссылки. ЕМНИП это не менялось со времён форка от си.

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

korian - ОГРОМНОЕ СПАСИБО!!!! ПОНЯЛ ПРАВИЛЬНО!!! smile