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

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

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

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

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

В лабораторной работе есть такое задание:
Создайте процедуру построения бинарного дерева на основе не бинарного.
Объясните как вообще создавать эти деревья и что необходимо реализовать в задании.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.05.2011, 13:52
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Построение бинарного дерева на основе не бинарного (C++):

Словарь на основе бинарного дерева - C++
Объясните, пожалуйста, что делает программа в функциях push и как осуществляется поиск, не совсем понимаю, для чего нужны l,r. Получается ,...

Построение бинарного дерева - C++
Доброй ночи! Пятые сутки не могу разобрать реализацию алгоритма на С++ Console Wizzard! Что такое бинарное дерево я знаю, даже разобрал...

Построение бинарного дерева - C++
Написать программу построения бинарного дерева с помощью связных структур и поиска в дереве при симметричном порядке обхода его. Если...

Создание строкового калькулятора на основе бинарного дерева - C++
Вот мой исходник. Проблема заключается в том, что не получается разложить строку на операторы с соответствующим приоритетом и операнды,...

Построение бинарного дерева из строки - C++
Доброго времени суток, уважаемые. Хотел бы спросить у вас спросить совета относительно реализации следующей проблемы: Задано...

Построение бинарного дерева. Где ошибка? - C++
Насколько понял, tree->left, tree->right указывает на NULL. Почему, не могу разобратся. #include <iostream> #include <ctime> using...

8
Daemon025
380 / 329 / 67
Регистрация: 06.12.2010
Сообщений: 900
17.05.2011, 20:59 #2
Создайте процедуру построения бинарного дерева на основе не бинарного.
это как?
с массивом может?
0
Jaksn
3 / 3 / 0
Регистрация: 26.03.2011
Сообщений: 114
17.05.2011, 21:17  [ТС] #3
Нет, никаких массивов. Тема лабораторной "Способы представления структур данных. Деревья" Все делается с помощью списков.
0
Jaksn
3 / 3 / 0
Регистрация: 26.03.2011
Сообщений: 114
22.05.2011, 19:01  [ТС] #4
Народ, помогите хотя бы разобраться как строить эти деревья. Я что-то во всех этих указателях путаюсь.
0
lemegeton
2925 / 1354 / 135
Регистрация: 29.11.2010
Сообщений: 2,725
23.05.2011, 16:23 #5
Цитата Сообщение от Jaksn Посмотреть сообщение
Создайте процедуру построения бинарного дерева на основе не бинарного.
Покажите вашу реализацию небинарного дерева, а то хз, чего надо-то.
1
pito211
186 / 173 / 8
Регистрация: 22.03.2010
Сообщений: 612
23.05.2011, 16:36 #6
с++ дерево классы
дерево ничего в себе не содержит
Дерево
тоже самое дерево, но наспех переделанное в шаблонное, может содержать в себе что-нибудь, но там требуется дописать его малость, функцию add например. Но все свойства дерева, взаимосвязи между сыновьями и родителями есть, поэтому можешь от него унаследовать своё бинарное дерево, child[0] интерепретировать всегда как левого сына, child[1] соответственно, как правого. И ещё надо приделать функцию root() чтобы она ссылку на корень возвращала
1
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)
}
}
Помогите хотя бы разобраться в этом фрагменте.
0
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 - количество элементов
}
1
Jaksn
3 / 3 / 0
Регистрация: 26.03.2011
Сообщений: 114
23.05.2011, 22:59  [ТС] #9
Спасибо, попробую разобраться. А чтобы полностью написать код, например того же обхода в глубину, еще что-то в код нужно или только добавить библиотеки и такой пойдет?

Добавлено через 1 минуту
Например, как где объявить root и пододные веще в коде.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.05.2011, 22:59
Привет! Вот еще темы с ответами:

Построение бинарного дерева из двумерного массива - C++
Стыдно, если честно, об этом просить, но "возник стопор" и путных идей не приходит. Суть задачи: Есть массив n*n состоящий из целых...

Создание бинарного дерева из бинарного файла - C++
struct Bin { string name; string city; int players; int score; }; void ReadFromBin(Point*& Tree) { Bin q;

Код Хаффмана реализованный через построение бинарного дерева - C++
Здравствуйте, есть код Хаффмана реализованный через построение бинарного дерева, узлами которого является элемент типа map ,либо символ и...

Запись бинарного дерева в файл и восстановление из него этого дерева - C++
Задача такая: есть бинарное дерево. Каждый элемент дерева содержит 3 указателя - 1 указатель на структуру с данными, 2 и 3й указатель на...


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

Или воспользуйтесь поиском по форуму:
9
Yandex
Объявления
23.05.2011, 22:59
Ответ Создать тему
Опции темы

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