С наступающим Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.57/7: Рейтинг темы: голосов - 7, средняя оценка - 4.57
AndriyNNNQS
0 / 0 / 0
Регистрация: 10.02.2017
Сообщений: 30
1

Реализация деревьев

10.05.2017, 23:16. Просмотров 1378. Ответов 11
Метки нет (Все метки)

Я вот сделал простое дерево (максимально дочерних узлов в корне - 3). Теперь нужно доработать, чтобы были списки сыновей.
Помогите пожалуйста. Вот сылка на метод по которому нужно сделать:http://bookwu.net/book_algoritmy-i-s...zaciya-derevev

Мой код который реализован через указатели:
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#define _CRT_SECURE_N0_WARNINGS
 
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <conio.h>
 
//-------------------------------------------------------------------------
//структура для описания узла дерева
struct tree
{
    int data;
    struct tree *lchild, *mchild, *rchild;
};
 
 
//функции для вставки узлов в дерево.Данная функция принимает на вход три параметра: 
//указатель на вставляемый узел, значение вставляемого узла и направление вставки — влево, 
//в середину или вправо.
struct tree * my_insert(struct tree *p, int n, int dir) {
    struct tree *temp;
 
    temp = (struct tree *)malloc(sizeof(struct tree));
    temp->data = n;
    temp->lchild = temp->rchild = temp->mchild = NULL;
 
    if (p == NULL)
    {
        return temp;
    }
    else
    {
        if (dir == 0) // влево
        {
            p->lchild = temp;
            return temp;
        }
        else if (dir == 1) // посередине
        {
            p->mchild = temp;
            return temp;
        }
        else // вправо
        {
            p->rchild = temp;
            return temp;
        }
    }
}
 
 
//Симетричний обхід дерева
void inorder(struct tree *p) {
    if (p != NULL)
    {
        inorder(p->lchild);
        printf("%d ", p->data);
        inorder(p->mchild);
        inorder(p->rchild);
    }
}
//-------------------------------------------------------------------------
int main() {
 
 
    struct tree *root;
    struct tree *node_2, *node_3, *node_5;
    struct tree *node_8, *node_9, *node_6, *node_10, *node_4, *node_7;
 
    //создание дерева
    root = NULL;
    root = my_insert(root, 1, 0);
    node_2 = my_insert(root, 2, 0);
    node_3 = my_insert(root, 3, 1);
    node_4 = my_insert(root, 4, 2);
    node_5 = my_insert(node_3, 5, 0);
    node_8 = my_insert(node_5, 8, 0);
    node_9 = my_insert(node_5, 9, 2);
    node_6 = my_insert(node_3, 6, 2);
    node_10 = my_insert(node_6, 10, 1);
    node_7 = my_insert(node_4, 7, 1);
 
 
 
 
    //выполнение обхода дерева
    //printf("\n");
    inorder(root);
    printf("\n");
 
 
    _getch();
    return 0;
}
0
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.05.2017, 23:16
Ответы с готовыми решениями:

Массив: Учащиеся участвовали в посадке деревьев. Сколько деревьев было посажено
1)Учащиеся 8-х классов участвовали в посадке деревьев. 8-а посадил 100...

Реализация двоичных деревьев поиска: Зачем в параметрах функции используется указатель на указатель
Всем привет, встретил в книге такой пример добавления узла в дерево: typedef...

Слияние деревьев
Сижу, мучаюсь, не могу понять что подразумевается в задании о слиянии деревьев....

Турнирная сортировка деревьев
Здравствуйте, программа турнирная сортировка деревьев. Но проблема в том, что...

Слияние бинарных деревьев
Слияние - это функция выбора элемента из двух Берем два дерева; функцию,...

11
GoldenId
131 / 130 / 64
Регистрация: 11.11.2010
Сообщений: 771
Записей в блоге: 14
Завершенные тесты: 1
10.05.2017, 23:43 2
Насколько я помню, стандартной реализацией дерева с произвольным количеством дочерних узлов у данного, для каждого узла делается список соседей:
C++
1
2
3
4
5
6
struct Node
{
    ...
    Node* parent;  // опционально
    Node* nextNeigh;  // указатель на следующего соседа, брата по родителю
};
0
AndriyNNNQS
0 / 0 / 0
Регистрация: 10.02.2017
Сообщений: 30
11.05.2017, 00:11  [ТС] 3
Я что-то не особо понимаю как теперь с этой структурой работать.
0
DU3
281 / 233 / 115
Регистрация: 07.09.2016
Сообщений: 587
11.05.2017, 00:52 4
берите ее с собой на работу. в кармане можно носить например.
конкретные вопросы задавайте, а то на неопределенные вопросы можно ответить вроде того, что в первом предложении.
0
AndriyNNNQS
0 / 0 / 0
Регистрация: 10.02.2017
Сообщений: 30
11.05.2017, 08:10  [ТС] 5
Как в неё записывать елеметы дерева? Сперва должен быть масив указателей вроде?
0
sourcerer
Модератор
Эксперт CЭксперт С++
4874 / 2060 / 325
Регистрация: 20.02.2013
Сообщений: 5,558
Записей в блоге: 24
Завершенные тесты: 1
11.05.2017, 08:31 6
 Комментарий модератора 
AndriyNNNQS, пожалуйста, прочитайте правила форума.
Особое внимание обратите на следующие пункты:

.
0
GoldenId
131 / 130 / 64
Регистрация: 11.11.2010
Сообщений: 771
Записей в блоге: 14
Завершенные тесты: 1
11.05.2017, 20:41 7
AndriyNNNQS, вместо того, чтобы использовать указатели на сыновей у родительского узла:
C++
1
2
3
4
5
struct Node
{
   ...
   Node* firstChild, secondChild,...;
};
которые идут в неизменном и ограниченном количестве:
C++
1
2
3
4
5
6
7
8
9
void parseNode( Node* node ) 
{
   if( node == nullptr )
      return;
   // обработать информационные поля узла
   parseNode( node->firstChild );
   parseNode( node->secondChild );
   ...
}
используете указатель на следующего соседа, с помощью которого организуется связанный список всех дочерних узлов родительского:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct Node
{
   // информационные поля
   Node* nextNeigh;
   Node* firstCHild;
};
 
void parseNodeDepth( Node* node )
{
   if( node == nullptr )
      return;
   // обработка информационных полей узла
   parseNodeDepth( firstChild );
   parseNodeDepth( nextNeigh );
}
или в ширину

C++
1
2
3
4
5
6
7
8
void parseNodeWidth( Node* node )
{
   if( node == nullptr )
      return;
   // обработка информационных полей узла
   parseNodeWidth( nextNeigh );
   parseNodeWidth( firstChild );
}
Добавлено через 21 минуту
Если для двоичного дерева, хранящегося в структурах узлов
C++
1
2
3
4
5
struct Node
{
   // инф поля
   Node* leftChild, * rightChild;
};
от указателя на корневой узел
C++
1
Node* root;
первый уровень узлов будет:root
второй:root->leftChild, root->rightChild
третий:root->leftChild->leftChild, root->leftChild->rightChild, root->rightChild->leftChild, root->rightChild->rightChild

то для дерева, хранящегося в узлах вида:
C++
1
2
3
4
5
6
struct Node
{
   // инф поля
   Node* firstChild;
   Node* nextNeigh;
};
от указателя на корневой узел
C++
1
Node* root;
первый уровень узлов будет:root
второй:root->firstChild, root->firstChild->nextNeigh, root->firstChild->nextNeight->nextNeigh ...
третий:root->firstChild->firstChild, root->firstChild->firstChild->nextNeigh, ..., root->firstChild->nextNeight->firstChild, root->firstChild->nextNeigh->firstChild->nextNeigh,...

(или для экономии можно начать первый уровень сразу заполненным
первый уровень:root, root->nextNeigh, root->nextNeigh->nextNeigh,...
0
AndriyNNNQS
0 / 0 / 0
Регистрация: 10.02.2017
Сообщений: 30
11.05.2017, 21:27  [ТС] 8
Да что ж это такое, я вроде сделал, но не работает. Пожалуйста ты можешь в мой код своё решение впихнуть? Буду ОЧЕНЬ благодарен.
0
GoldenId
131 / 130 / 64
Регистрация: 11.11.2010
Сообщений: 771
Записей в блоге: 14
Завершенные тесты: 1
11.05.2017, 22:22 9
Какие функции нужно реализовать? Вставить узел и обойти дерево (в ширину и в глубину)?
По какому критерию выбирать, куда вставлять?
0
AndriyNNNQS
0 / 0 / 0
Регистрация: 10.02.2017
Сообщений: 30
11.05.2017, 22:47  [ТС] 10
Реализовать дерево с помощю списка сыновей и обойти дерево любым способом.

Добавлено через 11 минут
Реализовать простое (не бинарное) дерево с помощю списка сыновей и обойти дерево любым способом.
0
GoldenId
131 / 130 / 64
Регистрация: 11.11.2010
Сообщений: 771
Записей в блоге: 14
Завершенные тесты: 1
12.05.2017, 01:39 11
Лучший ответ Сообщение было отмечено AndriyNNNQS как решение

Решение

Забыл очистку

trees.h
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <cstddef>
 
namespace trees
{
    // ====================================================
    // declarations
    // ====================================================
    template <typename T>
    struct Node
    {
        T data;
        Node* firstChild;
        Node* nextNeigh;
    };
 
    /// проход по дереву в ширину с предобработкой данных
    /// @param callback - адрес функции обратного вызова для поля данных каждого узла
    template <typename T>
    void traversePreWidth( Node<T>* node, void (*callback)( const T& ) );
 
    /// создание дерева от узла
    /// @param childNum - каким по счёту дочерним узлом данный приходится родительскому
    /// @param callback - адрес функции обратного вызова, возвращающей количество дочерних узлов
    /// которые следует добавить к данному, и возможно устанавливающей поле данных данного узла
    template <typename T>
    void generate( Node<T>* node, Node<T>* parent, size_t childNum,
                   size_t (*callback)( const Node<T>* parent, T& data, size_t childNum ) );
 
    /// создание дерева вместе с корнем
    /// @param callback - адрес функции обратного вызова, возвращающей количество дочерних узлов
    /// которые следует добавить к данному, и возможно устанавливающей поле данных данного узла
    template <typename T>
    Node<T>* generate( size_t (*callback)( const Node<T>* parent, T& data, size_t childNum ) );
 
    /// уничтожение дерева
    template <typename T>
    void dispose( Node<T>* node );
 
    // ====================================================
    // implementation
    // ====================================================
    template <typename T>
    void traversePreWidth( Node<T>* node, void (*callback)( const T& ) )
    {
        if( node == nullptr )
            return;
 
        callback( node->data );
 
        traversePreWidth( node->nextNeigh, callback );
        traversePreWidth( node->firstChild, callback );
    }
 
    template <typename T>
    Node<T>* generate( size_t (*callback)( const Node<T>* parent, T& data, size_t childNum ) )
    {
        Node<T>* root = new Node<T>;
        root->nextNeigh = nullptr;
        generate<T>( root, nullptr, 0, callback );
        return root;
    }
 
    template <typename T>
    void generate( Node<T>* node, Node<T>* parent, size_t childNum,
                   size_t (*callback)( const Node<T>* parent, T& data, size_t childNum ) )
    {
        if( node == nullptr )
            return;
        size_t n = callback( parent, node->data, childNum );
 
        Node<T>* child;
        if( n > 0 )
        {
            child = node->firstChild = new Node<T>;
            generate( child, node, 0, callback );
 
            for( size_t i = 1; i < n; i++ )
            {
                child = child->nextNeigh = new Node<T>;
                generate( child, node, i, callback );
            }
            child->nextNeigh = nullptr;
        }
        else
            node->firstChild = nullptr;
 
    }
 
    template <typename T>
    void dispose( Node<T>* node )
    {
        if( node->nextNeigh )
            dispose( node->nextNeigh );
        if( node->firstChild )
            dispose( node->firstChild );
        delete node;
    }
}
main.cpp
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
#include <cstdlib>
#include <ctime>
#include <iostream>
#include "trees.h"
 
void traverseCallback( const float& data );
 
/// @param data - поле данных узла, для которого вызван callback
/// @param childNum - каким по счёту дочерним узлом данный приходится родительскому
/// @return сколько дочерних узлов следует добавить к данному
size_t generateCallback( const trees::Node<float>* parent, float& data, size_t childNum );
 
int main()
{
    srand( time( 0 ) );
 
    trees::Node<float>* root = trees::generate<float>( &generateCallback );
    trees::traversePreWidth( root, &traverseCallback );
    trees::dispose( root );
}
 
void traverseCallback( const float& data )
{
    std::cout << data << " ";
}
 
/// @param data - поле данных узла, для которого вызван callback
/// @param childNum - каким по счёту дочерним узлом данный приходится родительскому
/// @return сколько дочерних узлов следует добавить к данному
size_t generateCallback( const trees::Node<float>* parent, float& data, size_t childNum )
{
    if( parent )
    {
        data = float( rand() ) / RAND_MAX * parent->data;
        return rand() % ( (int)parent->data / 2 + 1 );
    }
    else
    {
        data = float( rand() ) / RAND_MAX * 10;
        return rand() % 10;
    }
}
Конечно с узлом root получилось негибко, что он создаётся в любом случае. Но задачи по этому поводу и не стояло. Если дорабатывать, надо обернуть в класс.
1
AndriyNNNQS
0 / 0 / 0
Регистрация: 10.02.2017
Сообщений: 30
12.05.2017, 07:52  [ТС] 12
Спасибо.
0
12.05.2017, 07:52
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.05.2017, 07:52

Контейнеры STL и виды деревьев
подскажите, или покажите где есть эта информация например я знаю, что...

Определить, сколько посажено деревьев
Учащиеся 8-х классов участвовали в посадке деревьев. 8-а посадил 100 деревьев,...

Сравнить структуру двух деревьев
Написать два варианта функции(с рекурсией и без). Даны два дерева,два указателя...


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

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

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