Форум программистов, компьютерный форум CyberForum.ru

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

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

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

24.01.2013, 20:19. Просмотров 724. Ответов 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;
}
Очень прошу помочь и заранее благодарю!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.01.2013, 20:19     Обход АВЛ-Дерева
Посмотрите здесь:

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

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

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

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

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

Обход дерева в ширину - C++
имеется такой кусок программы. требуется обойти дерево в ширину. библиотека #include &lt;queue&gt; подключена void...

Обход дерева Хаффмана - C++
Добрый вечер. Имеем кодовое дерево Хаффмана.(в изображении) До каждого узла данного дерева есть путь из 0 и 1 . Для узла 12 ,...

Нерекурсивный обход дерева - C++
я не могу понять как сделать не рекурсивный обход дерева. понятно что надо добавлять элементы куда-то.в стек например. но я не знаю как...

Симметрический обход дерева - C++
Кто знает - симметрический обход дерева - это тоже самое что и сортировка? Получается так.

Ускорить обход дерева - C++
Во входном файле ancestor.in в первой строке содержится количество узлов дерева, во второй строке массив чисел i-ое из которых определяет...

Рекурсивный обход небинарного дерева - C++
Здравствуйте. бьюсь над задачей уже долго, но без помощи, чувствую, никак. Есть дерево, представлено этими двумя структурами. Нужно...

Бинарное Дерево(обход дерева) - C++
добрый вечер всем!) в универе задали написать бинарное дерево со всеми видами обхода и т.п. я их написал.. но еще дали 1 вывод его надо...


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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