Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.50/6: Рейтинг темы: голосов - 6, средняя оценка - 4.50
1458 / 924 / 807
Регистрация: 30.04.2016
Сообщений: 3,184
1

Бинарные деревья. Вывод потомков для каждого из узлов бинарного дерева поиска

22.07.2019, 18:58. Просмотров 1218. Ответов 6
Метки нет (Все метки)

Здравствуйте, уважаемые форумчане! Продолжая изучать бинарные деревья, решил подумать о выгодности использования третьего указателя, а именно указателя на родительский элемент. Если кому-то интересно, можно найти в сети случаи его использования. Я пока нашел пару вариантов его использования. Вот один из них (и еще один в следующей теме).

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
/*
Дано бинарное дерево поиска (BST). 
Вывести каждый узел данного дерева, а также его родителя, если родитель является нечетным числом. 
Для вывода информации использовать симметричный обход.
*/
 
#include <iostream>
 
    using namespace std;
 
struct BTree {
    int data;
    BTree* left;
    BTree* right;
    BTree* parent;
};
 
BTree* add(int data) {
    BTree* node = new BTree;
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    node->parent = NULL;
    return node;
}
 
BTree* insert(BTree* node, int key) { 
    if (node == NULL) 
        return add(key);
    if (key < node->data) {
        node->left = insert(node->left, key);
        node->left->parent = node;
    } else if (key > node->data) {
        node->right = insert(node->right, key);
        node->right->parent = node;
    }
    return node;
}
 
void print(BTree* node) {
    if (node == NULL) {
        return;
    }
    print(node->left);
    if (node->parent != NULL && node->parent->data % 2) {
        cout << node->data << " => " << node->parent->data << "\n";
    }
    print(node->right);
}
 
int main() {
    BTree* root = NULL;
    root = insert(root, 12);
    insert(root, 6);
    insert(root, 3);
    insert(root, 2);
    insert(root, 9);
    insert(root, 7);
    insert(root, 10);
    insert(root, 15);
    
    //Изображение построенного дерева
    /*
          12
         /  \         
        6    15
       / \  
      3   9  
     /   / \
    2   7   10
    */
    
    cout << "Output of the program:\n";
    print(root);
    return 0;
}
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
22.07.2019, 18:58
Ответы с готовыми решениями:

Бинарные деревья, вывод дерева на экран
Создание бинарное дерево, помогите с выводом дерева на экран #include &lt;iostream&gt; #include...

АТД деревья. Вывод бинарного дерева в консоль
Здравствуйте, нужна помощь! Возможно тема заезженная, но извеняйте не чего путнего не...

Бинарные деревья: создание, отображение, поиск узлов
Написать программу, которая выполняет следующие действия: 1. Генерирует с помощью генератора...

Вывод списка всех листьев бинарного дерева поиска
Нужно реализовать бинарное дерево поиска и вывести все его вершины, не имеющие потомков. Само...

6
4569 / 3072 / 1286
Регистрация: 07.05.2019
Сообщений: 9,496
Записей в блоге: 1
23.07.2019, 09:03 2
Цитата Сообщение от Fixer_84 Посмотреть сообщение
Здравствуйте, уважаемые форумчане! Продолжая изучать бинарные деревья, решил подумать о выгодности использования третьего указателя, а именно указателя на родительский элемент. Если кому-то интересно, можно найти в сети случаи его использования. Я пока нашел пару вариантов его использования. Вот один из них (и еще один в следующей теме).
А зачем здесь указатель на родителя? Ты обходишь дерево рекурсивно, т.е. этот указатель по-любому есть в стеке. Зачем его хранить в ноде?
0
1458 / 924 / 807
Регистрация: 30.04.2016
Сообщений: 3,184
23.07.2019, 18:03  [ТС] 3
oleg-m1973, здравствуйте! Указатель на родителя создается еще при добавлении элементов в дерево. Не совсем понимаю ваш вопрос. Указатель на родителя нужен, чтобы указывать на родителя, то есть, подниматься для каждого элемента на один уровень вверх.

Добавлено через 2 минуты
Цитата Сообщение от oleg-m1973 Посмотреть сообщение
Ты обходишь дерево рекурсивно, т.е. этот указатель по-любому есть в стеке. Зачем его хранить в ноде
Буду благодарен, если вы покажите ваш вариант поиска родителя для каждого элемента без использования родительского указателя. Нужно вывести каждый элемент и его родителя. Какой обход вы будете использовать?
0
4569 / 3072 / 1286
Регистрация: 07.05.2019
Сообщений: 9,496
Записей в блоге: 1
23.07.2019, 18:17 4
Лучший ответ Сообщение было отмечено Fixer_84 как решение

Решение

Цитата Сообщение от Fixer_84 Посмотреть сообщение
Буду благодарен, если вы покажите ваш вариант поиска родителя для каждого элемента без использования родительского указателя. Нужно вывести каждый элемент и его родителя. Какой обход вы будете использовать?
C++
1
2
3
4
5
6
7
8
9
10
void print(BTree* node, BTree *parent) {
    if (node == NULL) {
        return;
    }
    print(node->left, node);
    if (parent && parent->data % 2) {
        cout << node->data << " => " << parent->data << "\n";
    }
    print(node->right, node);
}
1
1458 / 924 / 807
Регистрация: 30.04.2016
Сообщений: 3,184
23.07.2019, 19:05  [ТС] 5
oleg-m1973, да, действительно получилось. Я пока еще только начал изучать деревья и не все понимаю. Я могу cкопировать ваш код к себе для разбора и дальнейшей работы с ним?
0
4569 / 3072 / 1286
Регистрация: 07.05.2019
Сообщений: 9,496
Записей в блоге: 1
23.07.2019, 19:08 6
Цитата Сообщение от Fixer_84 Посмотреть сообщение
oleg-m1973, да, действительно получилось. Я пока еще только начал изучать деревья и не все понимаю. Я могу cкопировать ваш код к себе для разбора и дальнейшей работы с ним?
Какой код, который в сообщении? Пожалуйста, тем более это твой код
0
1458 / 924 / 807
Регистрация: 30.04.2016
Сообщений: 3,184
23.07.2019, 19:11  [ТС] 7
Цитата Сообщение от oleg-m1973 Посмотреть сообщение
Какой код, который в сообщении?
Я имею ввиду код, который вы только что написали (где не нужен родительский указатель) из поста #4. Это уже не мой, а ваш код, поэтому я спрашиваю разрешения.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
23.07.2019, 19:11

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Итератор для бинарного дерева поиска.
Господа, нужен совет знатоков. Бинарное дерево поиска представлено следующей структурой. ...

Удалить четные листы (элементы у которых нет потомков) из бинарного дерева
Стоит задача удалить все четные элементы в бинарном дереве у которых нет потомков. Есть функция ...

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

Бинарные деревья. Напечатать все элементы дерева Т по уровням
Всем привет. Помогите написать программу или хотя бы функцию, условие следующее: Напечатать все...


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

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

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