Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Prolancer93
0 / 0 / 0
Регистрация: 13.01.2013
Сообщений: 2
#1

Обход АВЛ-Дерева - C++

24.01.2013, 20:19. Просмотров 798. Ответов 0
Метки нет (Все метки)

Всем привет! Возникла небольшая проблема, в программе которая реализует обход АВЛ-Дерева не срабатывает функция добавления элемента, не могли бы Вы объяснить почему?

Вот код программы:

AVL.h
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
#pragma once
#include <iostream>
#include <string>
 
using namespace std;
 
struct node // структура для представления узлов дерева
{
    int key;
    unsigned char height;
    node* left;
    node* right;
    node(int k) { key = k; left = right = 0; height = 1; }
};
 
class Tree
{
public:
    Tree();
    ~Tree();
    void Add(const int &key);
    void ShowTree();
 
private:
    void Show(node *&node, int level);
    node *Head;
};

AVL.cpp
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
#include "AVL.h"
#include <iostream>
#include <string>
 
using namespace std;
 
unsigned char height(node* p) // обертка для поля height
{
    return p?p->height:0;
}
 
int bfactor(node* p) // вычисляет balance factor заданного узла
{
    return height(p->right)-height(p->left);
}
 
void fixheight(node* p) // восстанавливает корректное значение поля height заданного узла
{
    unsigned char hl = height(p->left);
    unsigned char hr = height(p->right);
    p->height = (hl>hr?hl:hr)+1;
}
 
node* rotateright(node* p) // правый поворот вокруг p
{
    node* q = p->left;
    p->left = q->right;
    q->right = p;
    fixheight(p);
    fixheight(q);
    return q;
}
 
node* rotateleft(node* q) // левый поворот вокруг q
{
    node* p = q->right;
    q->right = p->left;
    p->left = q;
    fixheight(q);
    fixheight(p);
    return p;
}
 
node* balance(node* p) // балансировка узла p
{
    fixheight(p);
    if( bfactor(p)==2 )
    {
        if( bfactor(p->right) < 0 )
            p->right = rotateright(p->right);
        return rotateleft(p);
    }
    if( bfactor(p)==-2 )
    {
        if( bfactor(p->left) > 0  )
            p->left = rotateleft(p->left);
        return rotateright(p);
    }
    return p; // балансировка не нужна
}
 
node* insert(node* p, int k) // вставка ключа k в дерево с корнем p
{
    if( !p ) return new node(k);
    if( k<p->key )
        p->left = insert(p->left,k);
    else
        p->right = insert(p->right,k);
    return balance(p);
}
 
Tree::Tree()
{
    Head = NULL;
}
 
Tree::~Tree()
{
 
}
 
void Tree::Add(const int &key)
{
    insert(Head, key);
}
 
void Tree::ShowTree()
{
    Show(Head, 0);
}
 
void Tree::Show(node *&node, int level)
{
    if (node==NULL) return;
    Show(node->right, level+1);
    for(int i = 0;i< level;i++) cout<<"   ";
    cout<<node->key<<endl;
    Show(node->left, level+1);
}

main.cpp
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
#include "AVL.h"
#include <iostream>
#include <string>
 
using namespace std;
 
void main()
{
    Tree tree;
    tree.Add(6);
    tree.Add(10);
    tree.Add(5);
    tree.Add(1);
    tree.Add(8);
    tree.Add(9);
    tree.Add(4);
    tree.Add(11);
    tree.ShowTree();
    cout<<endl;
    cout<<endl;
    cout<<endl;
    system ("pause");
    return;
}
Очень прошу помочь и заранее благодарю!
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.01.2013, 20:19
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Обход АВЛ-Дерева (C++):

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

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

Обход дерева - C++
Вот начал читать про деревья и способы их обхода (PreOrder, InOrder и PostOrder). С алгоритмами проблем нет, но видно, как бы это сказать...

обход дерева - C++
struct SAcson { int l,c; // строка, столбец float x; // заряд bool e; // возбуждающий или тормозящий }; struct SSinapc { ...

обход дерева - C++
Здравствуйте! У меня вопрос: Есть класс: class D { vector &lt;A*&gt; count; }; ...

Обход дерева - C++
Всем доброе время суток. Не могу нормально обойти дерево и просмотреть введённое, по всей видимости, возможно я неправильно поставил...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.01.2013, 20:19
Привет! Вот еще темы с ответами:

Обход дерева) - C++
Прога работает) но сказали, что нужно сделать отдельную функцию обхода дерева) можете помочь) или пример)) #include &lt;iostream.h&gt; ...

Обход произвольного дерева - C++
struct tree { char info; struct tree *left; struct tree *right; }; так, вопрос глупый -меня просто сомнения берут. вот...

Обход n-арного дерева - C++
вопрос какой алгоритм использовать в плане КАК? знаю как хранить и как обходить, но алгоритм Лево Корень Право, а тут распечатывать...

Обход дерева по образцу - C++
Помогите осуществить обход дерева по образцу.


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

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

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