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

авл деревья

30.03.2015, 17:20. Просмотров 562. Ответов 0
Метки нет (Все метки)

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
#include <iostream>
#include <string>
using namespace std;
 
struct Node //описание дерева
{
    string Data;
    Node *Left, *Right, *Prev;
};
typedef Node *PNode;
 
string s;
int i, it = 0, n, hmax = 0;
bool b = 0;
 
void input(){ //ввод
    int i = 0;
    getline(cin, s);
    for (i = 0; i < n; i++){
        if (s[i] == 40 || s[i] == 41 || s[i] == 44 || s[i] > 47 && s[i] < 58) continue;
        else{
            cout << "Ошибка. Повторите ввод: ";
            s.clear();
            input();
        }
    }
}
 
void Add(PNode &Tree) //создание дерева
{
    if (s[it] > 47 && s[it] < 58)
    {
        Tree = new Node;
        Tree->Data = s[it];
        Tree->Left = NULL;
        Tree->Right = NULL;
        it++;
    }
    bool flag = 0;
    if (s[it] == 40)
    {
        if (s[it + 1] == 44)
            it += 2, Add(Tree->Right);
        else
            it++, Add(Tree->Left), flag = 1;
 
    }
    if (s[it] == 44 && flag)
    {
        it++, Add(Tree->Right);
    }
    if (s[it] == 41)
        it++;
}
 
void PrintTree(PNode Tree, int h) //вывод дерева на бок
{
    int i;
    if (Tree != NULL)
    {
        PrintTree(Tree->Right, h + 1);
        for (i = 1; i <= h; i++)
            cout << "    ";
        cout << Tree->Data << endl;
        cout << endl;
        PrintTree(Tree->Left, h + 1);
    }
}
 
void TreeHeightMax(PNode Tree, int h) //глубина дерева
{
    if (Tree != NULL)
    {
        TreeHeightMax(Tree->Right, h + 1);
        if (Tree->Left == NULL && Tree->Right == NULL)
            if (h > hmax) hmax = h;
        TreeHeightMax(Tree->Left, h + 1);
    }
}
 
void AVL(PNode Tree, int h) //проверка на АВЛ
{
    if (Tree != NULL)
    {
        AVL(Tree->Right, h + 1);
        if ((Tree->Left == NULL && Tree->Right == NULL) && hmax - h > 1){
            cout << "Дерево не является АВЛ-сбалансированным" << endl << "Узел, для которого нарушается принцип сбалансированности: " << Tree->Data << endl << endl;
            b = 1;
            exit(0);
        }
        AVL(Tree->Left, h + 1);
    }
}
 
void main(){
    setlocale(LC_ALL, "Russian");
    cout << "Введите строку, содержащую описание непустого дерева: ";
    PNode Tree = NULL;
    input();
    n = s.size();
    Add(Tree);
    cout << endl << "Дерево, построенное по описанию: " << endl << endl;
    PrintTree(Tree, 0);
    TreeHeightMax(Tree, 0);
    AVL(Tree, 0);
    if (b == 0) cout << "Дерево является АВЛ-сбалансированным" << endl << endl;
}
необходимо было создать дерево по скобочному описанию вида
вершина(левое,правое) и проверить на авл сбалансированность
но неправильно строится правое поддерево и не всегда корректно определяется его авл сбалансированность. помогите исправить
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.03.2015, 17:20
Ответы с готовыми решениями:

Добрый день, читал на хабре про АВЛ-деревья и хотелось бы кое-что уточнить
Добрый день, читал на хабре про АВЛ-деревья и возник один вопрос вот ссылка на статью...

АВЛ-дерево
Из входной последовательности символов построить АВЛ-дерево без повторов. Найти в нем узел,...

АВЛ дерево
Здравствуйте. Я начинающий программист и мне нужна помощь. Сейчас пытаюсь понять тему АВЛ деревьев...

АВЛ дерево и коллизия хэша
До некоторых пор думал, что красно-черное и авл деревья, да и вообще любые структуры, позволяющие...

Высота авл дерева - как считать?
Добрый вечер. Забавно. Предположим, что пустой указатель равен -1, высота пр - высота лев. ...

0
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.03.2015, 17:20

Комменты к реализации Красно-черного и АВЛ дерева
Люди добрые помогите разобрать и по возможности написать комментарии к этим 2м кодам .. Это коды...

Как в АВЛ-дереве найти самую короткую ветвь и удалить ее?
Доброго времени суток. Нужна помощь. В АВЛ-дереве надо найти самую короткую ветвь и удалить ее. Я...

Деревья
Я не особо разбираюсь в программировании (т.к это не связано с моей будущей специальностью,но те...


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

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

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