Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.75/4: Рейтинг темы: голосов - 4, средняя оценка - 4.75
d3vn
2 / 2 / 5
Регистрация: 18.11.2013
Сообщений: 118
1

Запись бинарного дерева

25.03.2015, 21:21. Просмотров 735. Ответов 6
Метки нет (Все метки)

Всем привет!
Нужно записать следующий массив (вверху картинки) в бинарное дерево, которое имеет структуру, которая на картинке во вложении.
Проблема в том, что нули в данном массиве указывают на структуру этого дерева (это не дерево поиска) и при записи нужно ее сохранить. Потому что потом это дерево нужно считать, отсортировать и превратить в дерево поиска + оставить его структуру.
Как создавать, записывать и выводить дерево я знаю, но как быть с нулями, которые указывают на структуру - без понятия. Подскажите, кто знает, пожалуйста
P.S. Пример другого дерева ДО и ПОСЛЕ (структура сохранена)
0
Миниатюры
Запись бинарного дерева  
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.03.2015, 21:21
Ответы с готовыми решениями:

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

Запись бинарного дерева в массив
Как можно записать элементы бинарного дерева в массив? Пробовал одну очень...

Запись и считывания бинарного дерева с текстового документа
Подскажите как записать и считать бинарное дерево с текстового документа! Вот...

Запись массива в виде бинарного дерева и вывод его на экран!
Задача: Зарандомить массив с 30 ел... от -100 до 100, создать бинарное дерево...

Написать шаблон бинарного дерева с функцией распечатки дерева
Не понимаю, что от меня хотят. Дано такое задание: Написать шаблон бинарного...

6
sklad1002
20 / 20 / 13
Регистрация: 28.04.2013
Сообщений: 85
25.03.2015, 21:57 2
я тебе в прошлой теме отвечал про дерево поиска ты спрашивал. а тут у тебя оказывается вопрос вообще не про то.

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

ты логику добавления уловил? если неноль пытаемся добавить налево, если слева ноль, то направо, если справа ноль, то поднимаемся на предыдущий элемент и... так далее

это довольно простая рекурсия, тебе может понадобится хранить в узле дополнительный указатель par, указывающий на предыдущий узел
1
d3vn
2 / 2 / 5
Регистрация: 18.11.2013
Сообщений: 118
25.03.2015, 22:04  [ТС] 3
sklad1002, про логику "если ноль, то туда, а не ноль, то сюда" я тоже думал, но не понимаю как подниматься выше и не понимаю конкретно как прописывать условия, на пальцах понимаю, а в код вообще дуб дубом.
Если у меня, например, есть такая связка addNode
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
30
31
32
33
34
35
36
// Add a node
void Tree::addNode(int key) {
     // No elements. Add the root
     if ( root == NULL ) {
        cout << "add root node ... " << key << endl;
        Node* n = new Node();
        n->setKey(key);
        root = n;
     }
     else {
       cout << "add other node ... " << key << endl;
       addNode(key, root);
     }
}
 
// Add a node (private)
void Tree::addNode(int key, Node* leaf) {
    if ( key <= leaf->Key() ) {
       if ( leaf->Left() != NULL )
          addNode(key, leaf->Left());
       else {
          Node* n = new Node();
          n->setKey(key);
          leaf->setLeft(n);
       }
    }
    else {
       if ( leaf->Right() != NULL )
          addNode(key, leaf->Right());
       else {
          Node* n = new Node();
          n->setKey(key);
          leaf->setRight(n);
       }
    }
}
Как мне подниматься вверх?
P.S. такая же логика должна быть и при пробеге in-order, верно? Или так сойдет:
C++
1
2
3
4
5
6
7
void Tree::inOrder(Node* n) {
    if ( n ) {
       inOrder(n->Left());
       cout << n->Key() << " ";
       inOrder(n->Right());
    }
}
0
sklad1002
20 / 20 / 13
Регистрация: 28.04.2013
Сообщений: 85
25.03.2015, 22:11 4
Цитата Сообщение от d3vn Посмотреть сообщение
но не понимаю как подниматься выше
Цитата Сообщение от sklad1002 Посмотреть сообщение
тебе может понадобится хранить в узле дополнительный указатель par, указывающий на предыдущий узел
я писал уже, давай уже почти )
1
d3vn
2 / 2 / 5
Регистрация: 18.11.2013
Сообщений: 118
25.03.2015, 22:19  [ТС] 5
sklad1002, да теоретически я понимаю, что да, нужно хранить, но куда его потом совать, к чему присваивать... уже голова кругом идет
0
sklad1002
20 / 20 / 13
Регистрация: 28.04.2013
Сообщений: 85
25.03.2015, 23:34 6
по коду выше

если мы сейчас говорим про обычное дерево, которое буде заполнять с нулями, то проверка на "меньше" в функции addNode не нужна, нас интересует только ноль-неноль. При реализации добавления рекурсией тебе также может помочь возвращаемое значение функцией addNode(), типа если добавил, то верни неноль, и прекрати все функции.

Добавлено через 1 час 0 минут
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <QtCore>
 
class TNode
{
public:
    TNode( int _key ) : key(_key), left(NULL), right(NULL){}
    int key;
    TNode* left;
    TNode* right;
};
 
class Tree
{
public:
    Tree() : root(NULL){}
    void insert( int key );
private:
    bool addNode( TNode*& _p, int key, int ind );
    TNode* root;
};
 
void Tree::insert( int key )
{
    addNode( root, key, 0 );
}
 
// обрати внимание, передача указателя на узел происходит по ссылке, важный момент
bool Tree::addNode( TNode*& _p, int _key, int ind )
{
    if( _p == NULL ) // если узла нет создадим
    {
        _p = new TNode( _key );
        qDebug() << _key << " added" << (ind&0xFF) << ((ind&0xFF00)>>8);
        return true;
    }
    // нулевой узел, значит ничего не получилось, попробуем вернуться назад и пойти направо или вернуться еще повыше
    else if( _p->key == 0 )
    {
        return false;
    }
    else if( addNode( _p->left, _key, ind+1 ) ) // сначала сходим налево
    {
        return true;
    }
    else if( addNode( _p->right, _key, ind+256 ) ) // потом направо
    {
        return true;
    }
 
    return false;
}
 
int main()
{
    int array[21] = { 1, 4, 6, 10, 0, 0, 0, 7, 0, 8, 0, 0, 2, 5, 0, 0, 3, 9, 0, 0, 0};
    Tree tree;
    for( int i = 0; i < 21; ++i)
    {
        tree.insert( array[i] );
    }
 
    return 0;
}
вот пример той рекурсии про которую я говорил. на конкретном примере тут должно быть все ОЧЕНЬ понятно
параметр "ind" это индикатор пройденного пути в момент добавления. первая цифра количество хождений налево, вторая - количество направо, все как нужно кароч. если не понятно чего спрашуй.
0
sklad1002
20 / 20 / 13
Регистрация: 28.04.2013
Сообщений: 85
25.03.2015, 23:36 7
Название: дерево.png
Просмотров: 28

Размер: 6.3 Кб
0
25.03.2015, 23:36
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.03.2015, 23:36

Построение бинарного дерева на основе не бинарного
В лабораторной работе есть такое задание: Создайте процедуру построения...

Создание бинарного дерева из бинарного файла
struct Bin { string name; string city; int players; int score; };...

Вывод бинарного дерева на экран в виде "дерева"
основная задача: подсчет количества листьев. проблема: при просмотре хочу...


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

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Опции темы

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