Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.50/4: Рейтинг темы: голосов - 4, средняя оценка - 4.50
3 / 2 / 1
Регистрация: 17.11.2018
Сообщений: 40
1

Сбалансированное дерево

07.09.2019, 22:59. Показов 645. Ответов 2
Метки нет (Все метки)

Неупорядоченную последовательность из n различных чисел изобразить в виде сбалансированного дерева. Найти высоту дерева и варианты обхода.
Сижу над задачей уже день.... Такое чувство , что мне попалась нерешаемая задача
0

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
07.09.2019, 22:59
Ответы с готовыми решениями:

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

Сбалансированное дерево
Всем привет!) Для учебной практики требуется решить задачу: Написать программу в С++, суть...

Идеально сбалансированное дерево
Дано идеально сбалансированное дерево. Нужно найти сумму его листьев. Дерево построил, но как...

Сбалансированное дерево (бинарное)
кто сможет, пожалуйста напишите код с++, построения сбалансированного дерева,функцию добавления...

2
170 / 122 / 61
Регистрация: 06.02.2015
Сообщений: 300
08.09.2019, 08:36 2
https://www.geeksforgeeks.org/... insertion/
Кликните здесь для просмотра всего текста
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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include <iostream>
 
using namespace std;
 
class Node{
public:
    int key;
    Node *left;
    Node *right;
    int height;
};
 
int height(Node *N){
    if (N == NULL){
        return 0;
    }
    return N->height;
}
  
int max(int a, int b){
    return (a > b) ? a : b;
}
 
Node* newNode(int key){
    Node* node = new Node();
    node->key = key;
    node->left = NULL;
    node->right = NULL;
    node->height = 1; 
    return(node);
}
 
Node *rightRotate(Node *y){
    Node *x = y->left;
    Node *T2 = x->right;
 
    x->right = y;
    y->left = T2;
 
    y->height = max(height(y->left),
        height(y->right)) + 1;
    x->height = max(height(x->left),
        height(x->right)) + 1;
 
    return x;
}
 
Node *leftRotate(Node *x){
    Node *y = x->right;
    Node *T2 = y->left;
 
    y->left = x;
    x->right = T2;
 
    x->height = max(height(x->left),
        height(x->right)) + 1;
    y->height = max(height(y->left),
        height(y->right)) + 1;
 
    return y;
}
 
int getBalance(Node *N){
    if (N == NULL)
        return 0;
    return height(N->left) - height(N->right);
}
  
Node* insert(Node* node, int key){
    if (node == NULL)
        return(newNode(key));
 
    if (key < node->key)
        node->left = insert(node->left, key);
    else if (key > node->key)
        node->right = insert(node->right, key);
    else 
        return node;
 
    node->height = 1 + max(height(node->left),
        height(node->right));
 
    int balance = getBalance(node);
 
    if (balance > 1 && key < node->left->key)
        return rightRotate(node);
 
    if (balance < -1 && key > node->right->key)
        return leftRotate(node);
 
    if (balance > 1 && key > node->left->key){
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }
 
    if (balance < -1 && key < node->right->key){
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }
 
    return node;
}
 
void preOrder(Node *root){
    if (root != NULL){
        cout << "Height: " << root->height << endl;
        cout << root->key << " ";
        preOrder(root->left);
        preOrder(root->right);
    }
}
 
int main(){
    Node *root = NULL;
    int n = 0;
 
    cout << "n=" << endl;
    cin >> n;
    int *arr = NULL;
    arr = new int[n];
    
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
 
    for (int i = 0; i < n; i++) {
        root = insert(root, arr[i]);
    }
    
 
    cout << "Preorder traversal of the "
        "constructed AVL tree is \n";
    preOrder(root);
 
    delete[]arr;
    system("pause");
    return 0;
}


либо тут https://www.tutorialspoint.com... t-avl-tree

Добавлено через 6 минут
Либо тут https://www.geeksforgeeks.org/... rotations/
можно понять
1
6738 / 4537 / 1839
Регистрация: 07.05.2019
Сообщений: 13,725
Записей в блоге: 1
08.09.2019, 09:41 3
Цитата Сообщение от Пограммис Посмотреть сообщение
Неупорядоченную последовательность из n различных чисел изобразить в виде сбалансированного дерева. Найти высоту дерева и варианты обхода.
Сижу над задачей уже день.... Такое чувство , что мне попалась нерешаемая задача
Отсортируй последовательность и пройдись по ней от середины, рекурсивно для левой половины и для правой. Глубина рекурсии и будет глубиной дерева.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
08.09.2019, 09:41

Идеально сбалансированное дерево
В файле input.txt хранится последовательность целых чисел.По входной последовательности построить...

Сбалансированное не бинарное дерево
Каково определение сбалансированного произвольного, не бинарного дерева ? Например, для...

Идеально сбалансированное дерево
Всем привет. Нужно построить идеально сбалансированное дерево из букв, упорядоченное я сделал, но...

Идеально сбалансированное дерево
Интересует как работает этот кусок кода) по идеи Create(&amp;tmp-&gt;right, nr); сюда компилятор никогда...


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

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

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