Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 17, средняя оценка - 4.82
Jaksn
3 / 3 / 0
Регистрация: 26.03.2011
Сообщений: 114
#1

Построение бинарного дерева на основе не бинарного - C++

15.05.2011, 13:52. Просмотров 2294. Ответов 8
Метки нет (Все метки)

В лабораторной работе есть такое задание:
Создайте процедуру построения бинарного дерева на основе не бинарного.
Объясните как вообще создавать эти деревья и что необходимо реализовать в задании.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.05.2011, 13:52     Построение бинарного дерева на основе не бинарного
Посмотрите здесь:
Построение бинарного дерева C++
Построение бинарного дерева C++
C++ Создание строкового калькулятора на основе бинарного дерева
Построение бинарного дерева из строки C++
C++ Построение бинарного дерева. Где ошибка?
Построение бинарного дерева из двумерного массива C++
C++ Код Хаффмана реализованный через построение бинарного дерева
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Daemon025
380 / 329 / 67
Регистрация: 06.12.2010
Сообщений: 900
17.05.2011, 20:59     Построение бинарного дерева на основе не бинарного #2
Создайте процедуру построения бинарного дерева на основе не бинарного.
это как?
с массивом может?
Jaksn
3 / 3 / 0
Регистрация: 26.03.2011
Сообщений: 114
17.05.2011, 21:17  [ТС]     Построение бинарного дерева на основе не бинарного #3
Нет, никаких массивов. Тема лабораторной "Способы представления структур данных. Деревья" Все делается с помощью списков.
Jaksn
3 / 3 / 0
Регистрация: 26.03.2011
Сообщений: 114
22.05.2011, 19:01  [ТС]     Построение бинарного дерева на основе не бинарного #4
Народ, помогите хотя бы разобраться как строить эти деревья. Я что-то во всех этих указателях путаюсь.
lemegeton
2923 / 1352 / 135
Регистрация: 29.11.2010
Сообщений: 2,725
23.05.2011, 16:23     Построение бинарного дерева на основе не бинарного #5
Цитата Сообщение от Jaksn Посмотреть сообщение
Создайте процедуру построения бинарного дерева на основе не бинарного.
Покажите вашу реализацию небинарного дерева, а то хз, чего надо-то.
pito211
186 / 173 / 8
Регистрация: 22.03.2010
Сообщений: 612
23.05.2011, 16:36     Построение бинарного дерева на основе не бинарного #6
с++ дерево классы
дерево ничего в себе не содержит
Дерево
тоже самое дерево, но наспех переделанное в шаблонное, может содержать в себе что-нибудь, но там требуется дописать его малость, функцию add например. Но все свойства дерева, взаимосвязи между сыновьями и родителями есть, поэтому можешь от него унаследовать своё бинарное дерево, child[0] интерепретировать всегда как левого сына, child[1] соответственно, как правого. И ещё надо приделать функцию root() чтобы она ссылку на корень возвращала
Jaksn
3 / 3 / 0
Регистрация: 26.03.2011
Сообщений: 114
23.05.2011, 22:09  [ТС]     Построение бинарного дерева на основе не бинарного #7
Не, мне с использованием классов не нужно. Мы их еще даже не проходили. Мы делаем с помощью списков.
Вот пример из методички. В ней только показано как объявить дерево при помощи структуры и приведена функция обхода в ширину. Я не могу понять каким образом она реализована. Что и почему на что указывает???

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
struct node {
    int key;
    node *parent;
    node *left;
    node *right;
}
 
 
void deep_walk(node *root){
    stack=create_stack();
stack_push(stack, root)
while((node *n=stack_pop(stack))!= NULL){
    do{
        printf("%c",n->key);
 
        if(n->left != NULL){
            if(n->right != NULL)
                stack_push(stack, n->right);
            n=n->left;
        }
        else 
            N=n->right;
    }
    while(n!=NULL)
}
}
Помогите хотя бы разобраться в этом фрагменте.
lasbat
2 / 2 / 0
Регистрация: 06.05.2010
Сообщений: 18
23.05.2011, 22:51     Построение бинарного дерева на основе не бинарного #8
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
struct node {
        int key;
        node *parent;// предок
        node *left;//левый потомок
        node *right;//правый
}
 
 
void deep_walk(node *root){//указатель на корень *root
        stack=create_stack();//
stack_push(stack, root);//помещаем в стек корень дерева
while((node *n=stack_pop(stack))!= NULL){// пока не пройдем дерево до конца
        do{
                printf("%c",n->key);//выводим значение корня на экран
 
                if(n->left != NULL){//если есть левый потомок
                        if(n->right != NULL)//и правый
                                stack_push(stack, n->right);//помещаем в стек правого
                        n=n->left;//идем влево по дереву
                }
                else 
                        N=n->right;//иначе вправо
        }
        while(n!=NULL)//пока дерево не кончится
}
}
как-то так

Добавлено через 10 минут
вобщем, тебе надо по обычному дереву сделать обход, и получить стек, то есть массив элементов, и по нему построить дерево бинарного поиска

Добавлено через 4 минуты
если есть список элементов, дерево можно задать так
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
struct Ttree
{
    int inf;
    Ttree *left;
    Ttree *right;
};
void create(int n, Ttree *&tr)
{
    
    int a;
    if(n>0)
    {
        tr=new Ttree;
        in>>a;
        tr->inf=a;
        tr->left=NULL;
        tr->right=NULL;
        int nl=n/2;
        int nr=n-nl-1;
        create(nl,tr->left);
        create(nr,tr->right);
    }
    
}
int main()
{
        Ttree *tree=NULL;//задаем пустое дерево
        create(n,tree);// n - количество элементов
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.05.2011, 22:59     Построение бинарного дерева на основе не бинарного
Еще ссылки по теме:
Балансировка бинарного дерева C++
Удаление из бинарного дерева C++
C++ Обход бинарного дерева
C++ Обход Бинарного дерева
C++ Высота бинарного дерева

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Jaksn
3 / 3 / 0
Регистрация: 26.03.2011
Сообщений: 114
23.05.2011, 22:59  [ТС]     Построение бинарного дерева на основе не бинарного #9
Спасибо, попробую разобраться. А чтобы полностью написать код, например того же обхода в глубину, еще что-то в код нужно или только добавить библиотеки и такой пойдет?

Добавлено через 1 минуту
Например, как где объявить root и пододные веще в коде.
Yandex
Объявления
23.05.2011, 22:59     Построение бинарного дерева на основе не бинарного
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru