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

Удаление вершин дерева - C++

Восстановить пароль Регистрация
 
alex_stp
0 / 0 / 0
Регистрация: 28.09.2009
Сообщений: 40
12.10.2010, 12:18     Удаление вершин дерева #1
Здравствуйте! Помогите в решении задачи.
Записи вершин 2-3–дерева – вещественные числа. Описать процедуру, которая удаляет все вершины со значением в указанном диапазоне.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.10.2010, 12:18     Удаление вершин дерева
Посмотрите здесь:

удаление из дерева C++
C++ Найти и удалить среднюю по значению из вершин дерева
удаление корня двоичного дерева C++
C++ Удаление узла дерева
C++ найти сумму значений нелистовых вершин дерева
C++ Обмен информации правых вершин одного бинарного дерева на информацию левых вершин другого
Написать рекурсивную процедуру, которая печатает ключи всех вершин двоичного дерева C++
C++ Вершины дерева вещественные числа. Описать процедуру, которая вычисляет среднее арифметическое всех вершин

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
alex_stp
0 / 0 / 0
Регистрация: 28.09.2009
Сообщений: 40
20.10.2010, 14:43  [ТС]     Удаление вершин дерева #2
помогите пожалуйста, хотя бы примером
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9371 / 5421 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
27.10.2010, 09:26     Удаление вершин дерева #3
Цитата Сообщение от alex_stp Посмотреть сообщение
помогите пожалуйста, хотя бы примером
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
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
#include <iostream>
#include <string>
 
template <typename T>
class Bintree {
    class Node {
        friend class Bintree;
        T * value;
        Node * parent;
        Node * left;
        Node * right;
        Node(const T & val, Node * p = 0) : parent(p), left(0), right(0) {
            value = new T(val);
        }
        ~Node(){
            delete value;
        }
    };
 
    Node * root;
 
    bool insertNode(const T & val, Node * & n, Node * p = 0){
        if ( ! n ){
            n = new Node(val, p);
            return true;
        }
        else if ( *(n->value) > val )
            return insertNode(val, n->left, n);
        else if ( *(n->value) < val )
            return insertNode(val, n->right, n);
        else
            return false;
    }
 
    void insertTree(Node * & n, Node * t){
        if ( ! n || ! t )
            return;
        insertTree(n, t->left);
        insertTree(n, t->right);
        insertNode(*(t->value), n);
    }
 
    void delTree(Node * n){
        if ( ! n )
            return;
        delTree(n->left);
        delTree(n->right);
        delete n;
        n = 0;
    }
 
    Node * findNode(const T & val, Node * n) {
        if ( ! n )
            return 0;
        else if ( *(n->value) == val )
            return n;
        else if ( *(n->value) > val )
            return findNode(val, n->left);
        else
            return findNode(val, n->right);
    }
 
    void dumpNodes(std::ostream & ost, Node * n, std::string delim = " ") {
        if ( ! n )
            return;
        dumpNodes(ost, n->left, delim);
        ost << *(n->value) << delim;
        dumpNodes(ost, n->right, delim);
    }
 
    Bintree(const Bintree &);
    Bintree operator = (const Bintree &);
 
public:
    Bintree() : root(0) {}
    ~Bintree(){
        delTree(root);
    }
 
    void add(const T & val){
        if ( ! insertNode(val, root) )
            throw ( std::string("Value exists!") );
    }
 
    void remove(const T & val){
        Node * n = findNode(val, root);
        if ( ! n ){
            throw ( std::string("Value not found!") );
        }
        else if ( n == root ){
            if ( ! n->right ){
                Node * nroot = n->left;
                delete root;
                if ( root = nroot )
                    root->parent = 0;
            }
            else {
                Node * nroot = root->right;
                Node * nleft;
                for ( nleft = nroot; nleft->left; nleft = nleft->left )
                    ;
                nleft->left = root->left;
                delete root;
                root = nroot;
                root->parent = 0;
            }
        }
        else {
            Node * & p = n->parent;
            if ( n == p->left )
                p->left = 0;
            else
                p->right = 0;
            insertTree(p, n->left);
            insertTree(p, n->right);
            delTree(n);
        }
    }
 
    void dump(std::ostream & ost, std::string delim = " "){
        dumpNodes(ost, root, delim);
    }
 
    bool empty(){
        return ! root;
    }
};
 
int menu(){
    int ret;
    std::cout << "\n1 - add value"
            << "\n2 - remove value"
            << "\n3 - dump values"
            << "\n0 - exit"
            << "\n> ";
    std::cin >> ret;
    return ret;
}
 
int main(){
    Bintree<double> bt;
    int m;
    double val;
 
    while ( m = menu() ){
        switch ( m ){
        case 1 :
            std::cout << "Value to add: ";
            std::cin >> val;
            try {
                bt.add(val);
            }
            catch ( std::string err ){
                std::cerr << "\aError: " << err << std::endl;
            }
            break;
        case 2 :
            std::cout << "Value to remove: ";
            std::cin >> val;
            try {
                bt.remove(val);
            }
            catch ( std::string err ){
                std::cerr << "\aError: " << err << std::endl;
            }
            break;
        case 3 :
            bt.dump(std::cout);
            std::cout << std::endl;
            break;
        default :
            std::cerr << "\aWrong command!" << std::endl;
            break;
        }
    }
 
    return 0;
}
Скорее всего не лучшая реализация двоичного дерева - всё-таки в первый раз такое делал. Но вроде работает...
Yandex
Объявления
27.10.2010, 09:26     Удаление вершин дерева
Ответ Создать тему
Опции темы

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