Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
АннаПавловна
0 / 0 / 0
Регистрация: 06.01.2017
Сообщений: 14
#1

Дано дерево. Распечатать дерево по уровням - C++

27.06.2017, 17:54. Просмотров 454. Ответов 10
Метки нет (Все метки)

Дано дерево. Распечатать дерево по уровням.
http://www.cyberforum.ru/cpp-beginners/thread843564.html
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.06.2017, 17:54
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Дано дерево. Распечатать дерево по уровням (C++):

Распечатать, посчитать среднее арифметическое, преобразовать в дерево поиска [Бинарные деревья]
Дано идеально сбалансированное дерево. Не выводиться дерево:(... Не понимаю...

Дано N-дерево. Удалить самый низкий лист(листья)
Нашел в сети вот такой код, пишут что он рабочий, но у меня при компиляции...

Исходное бинарное дерево превратить в бинарное дерево поиска, при этом сохранив его структуру
Помогите, не могу понять!( Нужно исходное бинарное дерево превратить в...

Напишите программу, которая бы читала дерево в формате (а) и затем печатала бы это дерево в формате (б).
Представление дерева: а) Д (Б (А, Ф (В,)), Е (,З (Ж, И))) б) Д ...

Дерево дерево, странное дерево
Нужна помощь в построении дерева. Задание таково: Вершина дерева содержит N...

10
MrGluck
Модератор
Эксперт CЭксперт С++
7980 / 4861 / 1422
Регистрация: 29.11.2010
Сообщений: 13,235
27.06.2017, 18:02 #2
Деревья разные бывают. Вы какое подразумеваете?

Добавлено через 24 секунды
Огромный шрифт в названии использовать не обязательно, мы тут не слепые.
0
АннаПавловна
0 / 0 / 0
Регистрация: 06.01.2017
Сообщений: 14
27.06.2017, 18:05  [ТС] #3
Необходимо создать бинарное дерево в соответствии с заданием, вывести его элементы,
используя симметричный обход и выполнив задание, вывести новое дерево.
0
MrGluck
Модератор
Эксперт CЭксперт С++
7980 / 4861 / 1422
Регистрация: 29.11.2010
Сообщений: 13,235
27.06.2017, 18:10 #4
Цитата Сообщение от АннаПавловна Посмотреть сообщение
в соответствии с заданием
Цитата Сообщение от АннаПавловна Посмотреть сообщение
выполнив задание
Какое задание?
0
АннаПавловна
0 / 0 / 0
Регистрация: 06.01.2017
Сообщений: 14
27.06.2017, 18:11  [ТС] #5
Распечатать бинарное дерево по уровням. это всё задание
0
MrGluck
Модератор
Эксперт CЭксперт С++
7980 / 4861 / 1422
Регистрация: 29.11.2010
Сообщений: 13,235
27.06.2017, 18:13 #6
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct bin_tree
{
   int value;
   bin_tree *left, *right;
}
 
void print(bin_tree *tree, const int level = 0)
{      
    if (tree->left) 
        print(tree->left, level + 1);
    for (int i = 0; i < level; i++)
         std::cout << " ";
    std::cout << tree->value << std::endl;
    if (tree->right) 
       print(tree->right, level + 1);
}
0
АннаПавловна
0 / 0 / 0
Регистрация: 06.01.2017
Сообщений: 14
27.06.2017, 18:43  [ТС] #7
что означает value ?
должно быть что-то после этого?
0
MrGluck
Модератор
Эксперт CЭксперт С++
7980 / 4861 / 1422
Регистрация: 29.11.2010
Сообщений: 13,235
27.06.2017, 18:47 #8
Цитата Сообщение от АннаПавловна Посмотреть сообщение
что означает value ?
Поле структуры
Цитата Сообщение от АннаПавловна Посмотреть сообщение
должно быть что-то после этого?
Смотря что вы имеете в виду.
Я вам дал пример вывода бинарного дерева, представленного структурой выше. Вам нужно создать структурную переменную и как-то заполнить её данными, а потом вызывать функцию print.
0
IGPIGP
Комп_Оратор)
Эксперт по математике/физике
7002 / 3294 / 448
Регистрация: 04.12.2011
Сообщений: 9,114
Записей в блоге: 5
27.06.2017, 21:47 #9
АннаПавловна, как вариант:
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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <iostream>
#include <list>
using namespace std;
 
template<typename T> 
struct Node
{
T key;
Node *left_;
Node *right_;
Node *parent_;
Node *root_;
Node(const T& key_)
:key(key_), left_(nullptr), right_(nullptr)
{root_=this; parent_=this;}
Node(const T& key_, Node *root)
:key(key_), root_(root), left_(nullptr), right_(nullptr), parent_(nullptr)
{}
void insert( Node *x,  Node *z){            // x — корень поддерева, z — вставляемый элемент
    
    while (x != nullptr){
     if (z->key >= x->key)
        if (x->right_ != nullptr)
           x = x->right_;
        else{
           z->parent_ = x;
           x->right_ = z;
           break;
        }
     else if (z->key < x->key)
        if (x->left_ != nullptr)
           x = x->left_;
        else{
           z->parent_ = x;
           x->left_ = z;
           break;
        }
    }
}
void add(Node *x, T key){
 
    if(root_==nullptr){
        root_=new Node(key);
root_->root_=this;
    }
else
{
Node *y=new Node(key, root_);
 
insert( x, y );
}
}
void add(T key){
    if(root_==nullptr){ root_=new Node(key);
        root_->root_=this;
    }
else{
Node *y=new Node(key, root_);
insert( root_, y );
}
}
void inorderTraversal(Node *x){
    if (x != nullptr){
      inorderTraversal(x->left_);
      cout << x->key<<' ';
      inorderTraversal(x->right_);
    }
}
 
void 
get_next_level_nodes_list( 
list<list<Node*>>& list_nodes_by_levels, int level=0    
    ){
list<list<Node*>>::const_iterator it_begin =  list_nodes_by_levels.begin(), it_last =  list_nodes_by_levels.end();
if(it_last == it_begin){
cout<<"The tree is empty"<<endl;
return;
}
it_last--;
list<Node*> list_nodes_next_level;
list<Node*>::const_iterator it=it_last->begin(), it_fin = it_last->end();
cout<<level<<'\t';
for(; it  != it_fin; ++it){
cout<<(*it)->key<<' ';
if((*it)->left_)
list_nodes_next_level.push_back((*it)->left_);
if((*it)->right_)
list_nodes_next_level.push_back((*it)->right_);
}
cout<<endl;
if(!list_nodes_next_level.empty()){
list_nodes_by_levels.push_back(list_nodes_next_level);
get_next_level_nodes_list( list_nodes_by_levels, ++level); 
}
}
 
};
int main(int argc, char* argv[])
{
const int sz=7;
int a[sz]={2,6,1,3,5,7};
Node<int> *node_root=new Node<int>(4);
for(int i=0; i<sz-1; ++i)node_root->add(node_root, a[i] );
cout<<endl;
node_root->inorderTraversal(node_root);
cout<<endl;
cout<<"\nlevels of the tree:\n";
list<Node<int>*> list_nodes_next_level;
list_nodes_next_level.push_back(node_root->root_);
list<list<Node<int>*>> list_nodes_by_levels;
list_nodes_by_levels.push_back(list_nodes_next_level);
node_root->get_next_level_nodes_list(list_nodes_by_levels);
cout<<endl;
system("pause");
return 0;
}
0
maxm
63 / 35 / 25
Регистрация: 17.07.2014
Сообщений: 457
28.06.2017, 12:51 #10
Чтобы вывести по уровням, гораздо проще использовать BFS.
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
void bfs_print(const vector<vector<bool>>& v, int start) { // матрица смежности и вершина, за которую подвешиваем дерево
    typedef struct Node {
        int id, level;
    };
    map<int,  vector<int>> lvls; // это будем печатать
    queue<Node> q;
    q.push({ start, 1 }); // стартовая вершина, 1 уровень
    vector<bool> used(v.size());
    used[start] = 1;
    while (!q.empty()) {
        auto top = q.front();
        lvls[top.level].push_back(top.id); // закидываем вершину на ее уровень 
        q.pop();
        for (int i = 0; i < v.size(); i++) if (v[top.id][i] && !used[i]) {
            used[i] = 1;
            q.push({ i, top.level + 1 }); // кидаем на уровень ниже (више по номеру, ниже по гравитации)
        }
    }
    for (auto row : lvls) {
        for (auto e : row.second) {
            cout << e << " ";
        }
        cout << endl;
    }
}
 
int main() {
    vector<vector<bool>> v = {
        { false, true, true, false, false, false, false},
        { true, false, false, true, true, false, false },
        { true, false, false, false, false, true, true },
        { false, true, false, false, false, false, false },
        { false, true, false, false, false, false, false },
        { false, false, true, false, false, false, false },
        { false, false, true, false, false, false, false }
 
};
    bfs_print(v, 0);
    return 0;
}
0
elrom
0 / 0 / 0
Регистрация: 28.06.2017
Сообщений: 8
28.06.2017, 19:41 #11
Реализация абстрактного типа данных "дерево"


Задача:

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



Входные данные:

массив курсоров на родительский элемент (значения узлов - индексы в массиве)


Выходные данные:

Последовательность узлов в прямом, обратном и симметричном порядке.



Пример:

Входные данные:

-1 0 0 0 1 2 3 1 2 3


Выходные данные:

0 1 4 7 2 5 8 3 6 9

4 7 1 5 8 2 6 9 3 0

4 1 7 0 5 2 8 6 3 9

Поможете?

Добавлено через 15 секунд
Реализация абстрактного типа данных "дерево"


Задача:

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



Входные данные:

массив курсоров на родительский элемент (значения узлов - индексы в массиве)


Выходные данные:

Последовательность узлов в прямом, обратном и симметричном порядке.



Пример:

Входные данные:

-1 0 0 0 1 2 3 1 2 3


Выходные данные:

0 1 4 7 2 5 8 3 6 9

4 7 1 5 8 2 6 9 3 0

4 1 7 0 5 2 8 6 3 9

Поможете?
0
28.06.2017, 19:41
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.06.2017, 19:41
Привет! Вот еще темы с решениями:

Дерево, бинарное дерево
Читаю про дерево и не до конца понимаю, а точнее понимаю, но вопрос в том,...

Дерево
Добрый вечер)))) Вот сегодне &quot;изучали &quot;деревья&quot;)) Дали задание: &quot;Написать...

дерево
Сделал дерево, если его ветви создаются на стадии компиляции, то все работает...

Дерево
Нужно НЕ рекурсивно распечатать двоичное дерево по слоям, собственно как это...


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

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

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