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

Реализация обхода в ширину и глубину бинарного дерева

14.06.2018, 20:45. Просмотров 466. Ответов 7
Метки нет (Все метки)

Как реализовать обход дерева (глубины три, т.е. трех уровневое) в глубину и ширину и что под этим подразумевается?
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
14.06.2018, 20:45
Ответы с готовыми решениями:

Разобраться с рекурсивной функцией обхода бинарного дерева
Люди, помогите разобраться с рекурсивной функцией обхода бинарного дерева. Бьюсь головой об стену,...

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

Реализация бинарного дерева
Доброго времени суток, уважаемые форумчане. Возник вопрос по реализации бинарного дерева на С++, а...

Реализация бинарного дерева
написать программу, реализующую бинарное дерево. Предусмотреть процедуры и функции: инициализация...

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

7
SuperKir
449 / 408 / 284
Регистрация: 10.03.2015
Сообщений: 1,749
Завершенные тесты: 1
14.06.2018, 21:02 2
Можно же всё найти, если поискать: https://medium.com/@dimko1/%D0%B0%D0...0-ed54848c2d47
Скорее всего на форуме в блогах тоже есть подобная инфа и реализации.
0
nenahov
0 / 0 / 2
Регистрация: 11.10.2016
Сообщений: 109
14.06.2018, 21:06  [ТС] 3
SuperKir, та я читал но там на графах и используют контейнеры
0
SuperKir
449 / 408 / 284
Регистрация: 10.03.2015
Сообщений: 1,749
Завершенные тесты: 1
14.06.2018, 21:17 4
nenahov, А что есть дерево по-твоему?
0
Ромаха
237 / 129 / 27
Регистрация: 16.12.2012
Сообщений: 586
Записей в блоге: 1
Завершенные тесты: 1
15.06.2018, 10:58 5
Но разница-то есть. Так что претензия обоснована
0
SuperKir
449 / 408 / 284
Регистрация: 10.03.2015
Сообщений: 1,749
Завершенные тесты: 1
16.06.2018, 20:03 6
Ромаха, и какая же?)
0
Ромаха
237 / 129 / 27
Регистрация: 16.12.2012
Сообщений: 586
Записей в блоге: 1
Завершенные тесты: 1
16.06.2018, 22:43 7
Например, dfs

для графа
C++
1
2
3
4
5
6
void dfs(int v) {
   if(used[v]) return;
   used[v] = true;
   for(int i = 0; i < g[v].size(); i++) 
       dfs(g[v][i]);
}
для дерева
C++
1
2
3
4
void dfs(int v, int from) {
    for(int i = 0; i < g[v].size(); i++) 
        if(g[v][i] != from) dfs(g[v][i], v);
}
0
Fixer_84
1310 / 822 / 753
Регистрация: 30.04.2016
Сообщений: 2,736
03.10.2018, 20:06 8
nenahov, здравствуйте! Я сейчас довольно активно изучаю бинарные деревья. В посте #2 вам дали правильную ссылку, однако можно найти гораздо больше материала с помощью англоязычного поиска. Действительно, существует два обхода - в ширину и глубину. Обход в глубину разбивается на три вида: preorder traversal, inorder traversal и postorder traversal. Эти три обхода (а именно, вывод узлов уже построенного дерева) в коде лишь различаются расположением функции printf() или cout (обычно это происходит рекурсивно), однако имеют очень большое практическое применение. В частности, с помощью inorder traversal можно вывести узлы в отсортированном порядке, а если добавить множество, то перевести, к примеру, обычное бинарное дерево в бинарное дерево поиска (не нарушая структуру). Более того, данные три вида обходов применяются при выводе нотаций (префиксная, инфиксная и постфиксная). Так, построив бинарное дерево выражений (binary expression tree) можно постфиксную запись, без особого труда, перевести в инфиксную или префиксную (будет меняться лишь тип обхода при выводе). Я рекомендую вам поискать в англоязычном поиске задачи, а именно, посмотреть binary search tree (BST) и binary expression tree и вы найдете целое множество примеров на использование деревьев. Я со своей стороны даю вам ссылку на код, который недавно реализовал с помощью очереди - это обход бинарного дерева в ширину: Задача на интересное применение очереди (обход дерева в ширину) Что касается обхода в глубину (их три), советую вам разобрать их на примере бинарного дерева поиска - это, кстати, очень классная тренировка на понимание рекурсии.

P.S. Я мог бы рассказать вам гораздо больше, если вы действительно заинтересованы в данной тематике.

Добавлено через 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
#include <bits/stdc++.h> 
 
    using namespace std;
    
struct node { 
    int data;
    int count;
    node *left;
    node *right;
};
    
node* newNode(int data) {
  node* element = new node; 
  element->data = data;
  element->count = 1;
  element->left = NULL; 
  element->right = NULL; 
  return element;
}
 
node* insert(node* element, int key) { 
    if (element == NULL) 
        return newNode(key);
    if (key < element->data)
        element->left = insert(element->left, key);
    else if (key > element->data)
        element->right = insert(element->right, key);
    else {
        element->count++;
    }   
    return element;
}
 
void printOrder(node* element) { 
    if (element == NULL)
        return;
    printOrder(element->left);
    cout << element->data << " " << element->count << "\n"; //Inorder traversal
    printOrder(element->right);
}
 
int main() {
    int n, k = 0;
    node* root = NULL;
    do {
        k++;
        cin >> n;
        if (n == 0) break;
        if (k == 1) root = insert(root, n); 
        else insert(root, n);
  } while (n);
  printOrder(root);
  system("pause");
  return 0;
}
0
03.10.2018, 20:06
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.10.2018, 20:06

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

Реализация бинарного дерева классом
Добрый вечер. Написал класс class TreeClass { int number; TreeClass *left, *right; public:...

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


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

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

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