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

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

Восстановить пароль Регистрация
 
Prolancer93
0 / 0 / 0
Регистрация: 13.01.2013
Сообщений: 2
24.01.2013, 20:19     Обход АВЛ-Дерева #1
Всем привет! Возникла небольшая проблема, в программе которая реализует обход АВЛ-Дерева не срабатывает функция добавления элемента, не могли бы Вы объяснить почему?

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

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++
C++ обход дерева
Обход дерева) C++
Обход дерева C++
обход дерева C++
обход дерева C++
Высота авл дерева - как считать? C++
Комменты к реализации Красно-черного и АВЛ дерева C++

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

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

Текущее время: 13:30. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru