Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Бинарные деревья. Вывод потомков для каждого из узлов бинарного дерева поиска https://www.cyberforum.ru/ cpp-beginners/ thread2485107.html
Здравствуйте, уважаемые форумчане! Продолжая изучать бинарные деревья, решил подумать о выгодности использования третьего указателя, а именно указателя на родительский элемент. Если кому-то...
C++ Одинаковые переменные в разных .h
Доброго времени суток. Есть у меня 2 .h файла (назовем их firstHeder, secondHeder) которые содержат в себе по одной одинаковой функции и одной одинаковой переменной. Так же есть класс (Назовем его...
Какое значение примет переменная x после выполнения следующего фрагмента программы C++
unsigned short int x,y; scanf("&d&d", &x, &y); x<<=y; при y, равном 8, x, равном 56506? В ответ введите шестнадцатиразрядное двоичное число.
C++ Крашится приложение при чтении адреса памяти Здравствуйте. Мой скрипт работает с другой офисной программой с помощью инжекта, помогая клиенту автоматизировать некоторые действия. Мне необходимо проверять состояние чекбокса, затем устанавливать... https://www.cyberforum.ru/ cpp-beginners/ thread2485064.html
C++ Сортировка по нескольким параметрам https://www.cyberforum.ru/ cpp-beginners/ thread2485061.html
Доброго времени суток, мне нужно сделать сортировку, по нескольким параметрам, т.е. сначало по имени, потом по номеру телефона, потом по улице, потом по номеру дома, естественно я могу это сделать,...
C++ Задача на инверсии
Здравствуйте. Прошу помощи с задачей: "Во время лыжных соревнований N спортсменов стартуют с интервалом в 1 минуту. Скорость каждого лыжника на дистанции постоянна: i-й лыжник преодолевает 1 км...
C++ Время выполнении функции
Можно ли сделать так, что б к примеру, функция _getch(), если она не выполнилась(то есть она не вернула какое-то значение за определенное время) за определенное время, то пусть программа выполняет...
C++ Неработающая нотация char* Добрый день, господа и дамы. Столкнулся с такой проблемой: Изучаю тему "Строки и массивы строк". В данной теме сказано, что можно использовать char* для, например, написания какого-либо текста... https://www.cyberforum.ru/ cpp-beginners/ thread2485027.html
C++ Сортировка массива указателей на строки https://www.cyberforum.ru/ cpp-beginners/ thread2485018.html
Здравствуйте. Есть две функции, которые используются для сортировки - одна, реализуя метод пузырьковой сортировки, вызывает в себе вторую, которая при необходимости меняет местами строки. Задание...
C++ Журнал событий Есть объект. И есть 30 сигналов. У каждого сигнала есть своё одно состояние (либо авария(красный цвет), либо предупреждение( жёлтый цвет), либо нормальная работа «зелёный цвет»). Когда я нажимаю на... https://www.cyberforum.ru/ cpp-beginners/ thread2484939.html
1460 / 926 / 807
Регистрация: 30.04.2016
Сообщений: 3,197
0

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

22.07.2019, 19:00. Просмотров 943. Ответов 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
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.