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

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

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

Дано дерево. Распечатать дерево по уровням.
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.06.2017, 17:54
Ответы с готовыми решениями:

Бинарное дерево. Удалить из дерева часть вершин так, чтобы оставшееся дерево стало пирамидой
Дано бинарное дерево. Удалить из дерева часть вершин так, чтобы оставшееся дерево стало пирамидой.

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

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

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

Дано дерево. Требуется найти самую удаленную вершину от данной
Формат входных данных В первой строке дано число n — количество вершин дерева и число k — номер...

10
MrGluck
Форумчанин
Эксперт CЭксперт С++
8132 / 4984 / 1436
Регистрация: 29.11.2010
Сообщений: 13,456
27.06.2017, 18:02 2
Деревья разные бывают. Вы какое подразумеваете?

Добавлено через 24 секунды
Огромный шрифт в названии использовать не обязательно, мы тут не слепые.
0
АннаПавловна
0 / 0 / 0
Регистрация: 06.01.2017
Сообщений: 14
27.06.2017, 18:05  [ТС] 3
Необходимо создать бинарное дерево в соответствии с заданием, вывести его элементы,
используя симметричный обход и выполнив задание, вывести новое дерево.
0
MrGluck
Форумчанин
Эксперт CЭксперт С++
8132 / 4984 / 1436
Регистрация: 29.11.2010
Сообщений: 13,456
27.06.2017, 18:10 4
Цитата Сообщение от АннаПавловна Посмотреть сообщение
в соответствии с заданием
Цитата Сообщение от АннаПавловна Посмотреть сообщение
выполнив задание
Какое задание?
0
27.06.2017, 18:10
АннаПавловна
0 / 0 / 0
Регистрация: 06.01.2017
Сообщений: 14
27.06.2017, 18:11  [ТС] 5
Распечатать бинарное дерево по уровням. это всё задание
0
MrGluck
Форумчанин
Эксперт CЭксперт С++
8132 / 4984 / 1436
Регистрация: 29.11.2010
Сообщений: 13,456
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Эксперт С++
8132 / 4984 / 1436
Регистрация: 29.11.2010
Сообщений: 13,456
27.06.2017, 18:47 8
Цитата Сообщение от АннаПавловна Посмотреть сообщение
что означает value ?
Поле структуры
Цитата Сообщение от АннаПавловна Посмотреть сообщение
должно быть что-то после этого?
Смотря что вы имеете в виду.
Я вам дал пример вывода бинарного дерева, представленного структурой выше. Вам нужно создать структурную переменную и как-то заполнить её данными, а потом вызывать функцию print.
0
IGPIGP
Комп_Оратор)
Эксперт по математике/физике
7560 / 3726 / 506
Регистрация: 04.12.2011
Сообщений: 10,698
Записей в блоге: 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
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.06.2017, 19:41

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

Дерево дерево, странное дерево
Нужна помощь в построении дерева. Задание таково: Вершина дерева содержит N целых значений и два...

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


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

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

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