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

Бинарные деревья. Вывод потомка, находящего на заданное число уровней выше заданного элемента

22.07.2019, 19:00. Просмотров 938. Ответов 5
Метки нет (Все метки)

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

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
/*
Дано бинарное дерево поиска (BST). 
Вывести родительский элемент для заданного узла, находящийся на n уровней выше от него (но не выше корня дерева). 
*/
 
#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* getNodeLevelParent(BTree* node, int key, int n) {
    if (node == NULL) {
        return 0;
    }
    if (node->data == key) {
        if (node->parent != NULL) {
            for (int i = 1; i < n; i++) {
                node = node->parent;
            }
            return node->parent;
        } else {
            return node;
        }
    }
    if (key < node->data) {
        return getNodeLevelParent(node->left, key, n);
    } else if (key > node->data){
        return getNodeLevelParent(node->right, key, n);
    }
}
 
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;
}
 
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";
    cout << getNodeLevelParent(root, 7, 3)->data << "\n";
    return 0;
}
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
22.07.2019, 19:00
Ответы с готовыми решениями:

Бинарные деревья: неправильный вывод
неправильно выводит дерево,что делать? #include&lt;iostream&gt; using namespace std; struct...

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

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

Заданы 6 цифр и число. Используя скобки и бинарные арифметические операции +,-,*,/, получить заданное число
помогите написать программу на C#, как-нибудь отблагодарю Заданы 6 цифр и число. Используя...

5
213 / 138 / 26
Регистрация: 11.01.2019
Сообщений: 576
22.07.2019, 19:28 2
Так это ж "прошитые" деревья так строятся!
1
1458 / 924 / 807
Регистрация: 30.04.2016
Сообщений: 3,184
22.07.2019, 19:31  [ТС] 3
Цитата Сообщение от jugu Посмотреть сообщение
Так это ж "прошитые" деревья так строятся!
jugu, здравствуйте! Спасибо за информацию. Не знал этого. Буду изучать.
0
4569 / 3072 / 1286
Регистрация: 07.05.2019
Сообщений: 9,495
Записей в блоге: 1
23.07.2019, 09:10 4
Цитата Сообщение от Fixer_84 Посмотреть сообщение
Здравствуйте, уважаемые форумчане! Продолжая изучать бинарные деревья, решил подумать о выгодности использования третьего указателя, а именно указателя на родительский элемент. Если кому-то интересно, можно найти в сети случаи его использования. Вот один из них, который я придумал:
Указатель на родителя нужен, если ты хочешь сделать обход своего дерева без рекурсии. А ты показываешь обычные рекурсивные алгоритмы, где этот указатель нафиг не нужен.
0
1458 / 924 / 807
Регистрация: 30.04.2016
Сообщений: 3,184
23.07.2019, 18:06  [ТС] 5
Цитата Сообщение от oleg-m1973 Посмотреть сообщение
Указатель на родителя нужен, если ты хочешь сделать обход своего дерева без рекурсии.
oleg-m1973, буду премного благодарен, если вы напишите вариант этой программы без использования данного указателя.
0
4569 / 3072 / 1286
Регистрация: 07.05.2019
Сообщений: 9,495
Записей в блоге: 1
23.07.2019, 21:11 6
Лучший ответ Сообщение было отмечено Fixer_84 как решение

Решение

Цитата Сообщение от Fixer_84 Посмотреть сообщение
oleg-m1973, буду премного благодарен, если вы напишите вариант этой программы без использования данного указателя.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
BTree* getNodeLevelParent(BTree* node, int key, int n, BTree *parent = nullptr) 
{
    if (node == NULL) {
        return 0;
    }
    if (node->data == key) 
        return parent? parent: node;
    
    if (!parent)
        parent = node;
    
    if (n)
        --n;
    else
        parent = node;
 
    if (key < node->data) {
        return getNodeLevelParent(node->left, key, n, parent);
    }
    else if (key > node->data) {
        return getNodeLevelParent(node->right, key, n, parent);
    }
}
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
23.07.2019, 21:11

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

Количество уровней списка с суммой, большей, чем заданное число
Доброго времени суток. Задача: Дан сложный список вида ((1 (2 4 3 6) 7) 9 8 ((9 10 11) 12 (13 14)...

Бинарные деревья: выделить метку вершины дерева, имеющую наибольшее число вхождений
Добрый день. Помогите, пожалуйста, написать программу на Haskell. Выделить метку вершины...

Используя скобки и бинарные арифметические операции +,-,*,/, получить заданное число
помогите написать программу на CommonLisp, как-нибудь отблагодарю Заданы 6 цифр и число....

Используя скобки и бинарные арифметические операции +,-,*,/, получить заданное число
помогите написать программу на F#, как-нибудь отблагодарю Заданы 6 цифр и число. Используя...


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

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

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