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

Бинарное дерево поиска - C++

Восстановить пароль Регистрация
 
cats2013
1 / 1 / 0
Регистрация: 14.04.2013
Сообщений: 17
14.04.2013, 22:15     Бинарное дерево поиска #1
Пишу программу - Бинарное дерево поиска для Bag class.

Заголовочный файл:
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
#ifndef BAG6_H 
#define BAG6_H
#include <cstdlib>     // Provides NULL and size_t
#include "bintree.h"   // Provides binary_tree_node and related functions
 
namespace main_savitch_10
{
    template <class Item>
    class bag
    {
    public:
        // TYPEDEFS
    typedef std::size_t size_type;
        typedef Item value_type;
        // CONSTRUCTORS and DESTRUCTOR
        bag( );
        bag(const bag& source);
        ~bag( );    
        // MODIFICATION functions
        size_type erase(const Item& target);
        bool erase_one(const Item& target);
        void insert(const Item& entry);
        void operator +=(const bag& addend);
        void operator =(const bag& source); 
        // CONSTANT functions
        size_type size( ) const;
        size_type count(const Item& target) const;
    private:
        binary_tree_node<Item> *root_ptr; // Root pointer of binary search tree
        void insert_all(binary_tree_node<Item>* addroot_ptr);
    };
 
    // NONMEMBER functions for the bag<Item> template class
    template <class Item>
    bag<Item> operator +(const bag<Item>& b1, const bag<Item>& b2);
}
 
#include "bag6.template" // Include the implementation.
#endif
Необходимо дополнить implementation file:
- count;
- insert;
- bst_remove_max;
- bst_remove_all.

Файл implementation file (без выполнения этих операций):
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
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
#include <cassert>
#include <cstdlib>
 
namespace main_savitch_10
{
    template <class Item>
    void bst_remove_max(binary_tree_node<Item>*& root_ptr, Item& removed)
    // Precondition: root_ptr is a root pointer of a non-empty binary 
    // search tree.
    // Postcondition: The largest item in the binary search tree has been
    // removed, and root_ptr now points to the root of the new (smaller) 
    // binary search tree. The reference parameter, removed, has been set 
    // to a copy of the removed item.
    {
       ////// необхадима помощь
    }
 
    template <class Item>
    bool bst_remove(binary_tree_node<Item>*& root_ptr, const Item& target)
    // Precondition: root_ptr is a root pointer of a binary search tree 
    // or may be NULL for an empty tree).
    // Postcondition: If target was in the tree, then one copy of target
    // has been removed, and root_ptr now points to the root of the new 
    // (smaller) binary search tree. In this case the function returns true.
    // If target was not in the tree, then the tree is unchanged (and the
    // function returns false).
    {
        binary_tree_node<Item> *oldroot_ptr;
        
        if (root_ptr == NULL)
        {   // Empty tree
        return false;
        }
 
        if (target < root_ptr->data( ))
        {   // Continue looking in the left subtree
        // Note: Any change made to root_ptr->left by this recursive
        // call will change the actual left pointer (because the return
        // value from the left() member function is a reference to the
        // actual left pointer.
        return bst_remove(root_ptr->left( ), target);
        }
 
        if (target > root_ptr->data( ))
        {   // Continue looking in the right subtree
        // Note: Any change made to root_ptr->right by this recursive
        // call will change the actual right pointer (because the return
        // value from the right() member function is a reference to the
        // actual right pointer.
        return bst_remove(root_ptr->right( ), target);
        }
        
        if (root_ptr->left( ) == NULL)
        {   // Target was found and there is no left subtree, so we can
        // remove this node, making the right child be the new root.
        oldroot_ptr = root_ptr;
        root_ptr = root_ptr->right( );
        delete oldroot_ptr;
        return true;
        }
        
        // If code reaches this point, then we must remove the target from
        // the current node. We'll actually replace this target with the
        // maximum item in our left subtree.
        // Note: Any change made to root_ptr->left by bst_remove_max
        // will change the actual left pointer (because the return
        // value from the left() member function is a reference to the
        // actual left pointer.
        bst_remove_max(root_ptr->left( ), root_ptr->data( ));
        return true;
    }
 
    template <class Item>
    typename bag<Item>::size_type bst_remove_all
    (binary_tree_node<Item>*& root_ptr, const Item& target)
    // Precondition: root_ptr is a root pointer of a binary search tree 
    // or may be NULL for an empty tree).
    // Postcondition: All copies of target have been removed from the tree
    // has been removed, and root_ptr now points to the root of the new 
    // (smaller) binary search tree. The return value tells how many copies
    // of the target were removed.
    {
        ////////////////// необхадима помощь
        
        binary_tree_node<Item> *oldroot_ptr;
        
        if (root_ptr == NULL)
        {   // Empty tree
            ////  необхадима помощь
        }
 
        if (target < root_ptr->data( ))
        {   // Continue looking in the left subtree
            ///// необхадима помощь
        }
 
        if (target > root_ptr->data( ))
        {   // Continue looking in the right subtree
            //// необхадима помощь
        }
        
        if (root_ptr->left( ) == NULL)
        {   // Target was found and there is no left subtree, so we can
        // remove this node, making the right child be the new root.
        oldroot_ptr = root_ptr;
        root_ptr = root_ptr->right( );
        delete oldroot_ptr;
        return 1;
        }
        
        // If code reaches this point, then we must remove the target from
        // the current node. We'll actually replace this target with the
        // maximum item in our left subtree. We then continue
        // searching for more copies of the target to remove.
        // This continued search must start at the current root (since
        // the maximum element that we moved up from our left subtree
        // might also be a copy of the target).
      /////////// необхадима помощь
 
    }
 
    template <class Item>
    bag<Item>::bag(const bag<Item>& source)
    // Library facilities used: bintree.h
    {
        root_ptr = tree_copy(source.root_ptr);
    }
 
    template <class Item>
    bag<Item>::~bag( )
    // Header file used: bintree.h
    {
        tree_clear(root_ptr);
    }
 
    template <class Item>
    typename bag<Item>::size_type bag<Item>::size( ) const
    // Header file used: bintree.h
    {
        return tree_size(root_ptr);
    }
 
    template <class Item>
    void bag<Item>::insert(const Item& entry)
    // Header file used: bintree.h
    {
        binary_tree_node<Item> *cursor;
    
        if (root_ptr == NULL)
        {   // Add the first node of the binary search tree:
        root_ptr = new binary_tree_node<Item>(entry);
        return;
        }
 
        else
        {   // Move down the tree and add a new leaf:
        cursor = root_ptr;
        //////  необхадима помощь
        }
    }
 
    template <class Item>
    typename bag<Item>::size_type bag<Item>::count(const Item& target) const
    {
        size_type answer = 0;
        binary_tree_node<Item> *cursor;
 
        cursor = root_ptr;
        //////   необхадима помощь
        
        return answer;
    }
 
    template <class Item>
    typename bag<Item>::size_type bag<Item>::erase(const Item& target)
    {
        return bst_remove_all(root_ptr, target);
    }
 
    template <class Item>
    bool bag<Item>::erase_one(const Item& target)
    {
        return bst_remove(root_ptr, target);
    }
 
    template <class Item>
    void bag<Item>::operator =(const bag<Item>& source)
        // Header file used: bintree.h
        {
        if (root_ptr == source.root_ptr)
            return;
        tree_clear(root_ptr);
        root_ptr = tree_copy(source.root_ptr);
    }
 
    template <class Item>
    void bag<Item>::operator +=(const bag<Item>& addend)
        {
        if (root_ptr == addend.root_ptr)
        {
        bag<Item> copy = addend;
        insert_all(copy.root_ptr);
        }
        else
            insert_all(addend.root_ptr);
    }
 
    template <class Item>
    bag<Item> operator +(const bag<Item>& b1, const bag<Item>& b2)
    {
        bag<Item> answer = b1;
        answer += b2;
        return answer;
    }
 
    template <class Item>
    void bag<Item>::insert_all(binary_tree_node<Item>* addroot_ptr)
        // Precondition: addroot_ptr is the root pointer of a binary search tree that
        // is separate for the binary search tree of the bag that activated this
        // method.
        // Postcondition: All the items from the addroot_ptr's binary search tree
        // have been added to the binary search tree of the bag that activated this
        // method.
    {
        if (addroot_ptr != NULL)
        {
        insert(addroot_ptr->data( ));
        insert_all(addroot_ptr->left( ));
        insert_all(addroot_ptr->right( ));
        }
    }
}
Прошу помоши.

Добавлено через 3 часа 1 минуту
Программа переделанна.
Подскажите правильно ли выполнены функции:
- count;
- insert;
- bst_remove_all????

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
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
#include <cassert>
#include <cstdlib>
 
namespace main_savitch_10
{
    template <class Item>
    void bst_remove_max(binary_tree_node<Item>*& root_ptr, Item& removed)
    // Precondition: root_ptr is a root pointer of a non-empty binary 
    // search tree.
    // Postcondition: The largest item in the binary search tree has been
    // removed, and root_ptr now points to the root of the new (smaller) 
    // binary search tree. The reference parameter, removed, has been set 
    // to a copy of the removed item.
    
 
    template <class Item>
    bool bst_remove(binary_tree_node<Item>*& root_ptr, const Item& target)
    // Precondition: root_ptr is a root pointer of a binary search tree 
    // or may be NULL for an empty tree).
    // Postcondition: If target was in the tree, then one copy of target
    // has been removed, and root_ptr now points to the root of the new 
    // (smaller) binary search tree. In this case the function returns true.
    // If target was not in the tree, then the tree is unchanged (and the
    // function returns false).
    {
        binary_tree_node<Item> *oldroot_ptr;
        
        if (root_ptr == NULL)
        {   // Empty tree
        return false;
        }
 
        if (target < root_ptr->data( ))
        {   // Continue looking in the left subtree
        // Note: Any change made to root_ptr->left by this recursive
        // call will change the actual left pointer (because the return
        // value from the left() member function is a reference to the
        // actual left pointer.
        return bst_remove(root_ptr->left( ), target);
        }
 
        if (target > root_ptr->data( ))
        {   // Continue looking in the right subtree
        // Note: Any change made to root_ptr->right by this recursive
        // call will change the actual right pointer (because the return
        // value from the right() member function is a reference to the
        // actual right pointer.
        return bst_remove(root_ptr->right( ), target);
        }
        
        if (root_ptr->left( ) == NULL)
        {   // Target was found and there is no left subtree, so we can
        // remove this node, making the right child be the new root.
        oldroot_ptr = root_ptr;
        root_ptr = root_ptr->right( );
        delete oldroot_ptr;
        return true;
        }
        
        // If code reaches this point, then we must remove the target from
        // the current node. We'll actually replace this target with the
        // maximum item in our left subtree.
        // Note: Any change made to root_ptr->left by bst_remove_max
        // will change the actual left pointer (because the return
        // value from the left() member function is a reference to the
        // actual left pointer.
        bst_remove_max(root_ptr->left( ), root_ptr->data( ));
        return true;
    }
 
    template <class Item>
    typename bag<Item>::size_type bst_remove_all
    (binary_tree_node<Item>*& root_ptr, const Item& target)
    // Precondition: root_ptr is a root pointer of a binary search tree 
    // or may be NULL for an empty tree).
    // Postcondition: All copies of target have been removed from the tree
    // has been removed, and root_ptr now points to the root of the new 
    // (smaller) binary search tree. The return value tells how many copies
    // of the target were removed.
    {
        /**  This implementation is similar to bst_remove, except that
         ** all occurrences of the target must be removed, and the return
         ** value is the number of copies that were removed.
         */
        
        binary_tree_node<Item> *oldroot_ptr;
        
        if (root_ptr == NULL)
        {   // Empty tree
         return false;
            
        }
 
        if (target < root_ptr->data( ))
        {   // Continue looking in the left subtree
         return bst_remove(root_ptr->left( ), target);
           
        }
 
        if (target > root_ptr->data( ))
        {   // Continue looking in the right subtree
         return bst_remove(root_ptr->right( ), target);   /* STUDENT WORK */
        }
        
        if (root_ptr->left( ) == NULL)
        {   // Target was found and there is no left subtree, so we can
        // remove this node, making the right child be the new root.
        oldroot_ptr = root_ptr;
        root_ptr = root_ptr->right( );
        delete oldroot_ptr;
        return 1;
        }
        
        // If code reaches this point, then we must remove the target from
        // the current node. We'll actually replace this target with the
        // maximum item in our left subtree. We then continue
        // searching for more copies of the target to remove.
        // This continued search must start at the current root (since
        // the maximum element that we moved up from our left subtree
        // might also be a copy of the target).
       
    }
 
    template <class Item>
    bag<Item>::bag(const bag<Item>& source)
    // Library facilities used: bintree.h
    {
        root_ptr = tree_copy(source.root_ptr);
    }
 
    template <class Item>
    bag<Item>::~bag( )
    // Header file used: bintree.h
    {
        tree_clear(root_ptr);
    }
 
    template <class Item>
    typename bag<Item>::size_type bag<Item>::size( ) const
    // Header file used: bintree.h
    {
        return tree_size(root_ptr);
    }
 
    template <class Item>
    void bag<Item>::insert(const Item& entry)
    // Header file used: bintree.h
    {
        binary_tree_node<Item> *cursor;
    
        if (root_ptr == NULL)
        {   // Add the first node of the binary search tree:
        root_ptr = new binary_tree_node<Item>(entry);
        return;
        }
 
        else
        {   // Move down the tree and add a new leaf:
        cursor = root_ptr;
        
        while(root_ptr != NULL)
        {
        if(entry <= root_ptr->getItem())
            root_ptr = root_ptr->getLeft();
        else
            root_ptr = root_ptr->getRight();
        }
      }
 
    template <class Item>
    typename bag<Item>::size_type bag<Item>::count(const Item& target) const
    {
        size_type answer = 0;
        binary_tree_node<Item> *cursor;
 
        cursor = root_ptr;
        
        if( root_ptr == NULL)
                return(0);
        else
                if( cursor->left == NULL && cursor->right == NULL)
                        return(1);
                else
                        return(1 + (count(cursor->left) + count(cursor->right)));
     }
        
 
        return answer;
    }
 
    template <class Item>
    typename bag<Item>::size_type bag<Item>::erase(const Item& target)
    {
        return bst_remove_all(root_ptr, target);
    }
 
    template <class Item>
    bool bag<Item>::erase_one(const Item& target)
    {
        return bst_remove(root_ptr, target);
    }
 
    template <class Item>
    void bag<Item>::operator =(const bag<Item>& source)
        // Header file used: bintree.h
        {
        if (root_ptr == source.root_ptr)
            return;
        tree_clear(root_ptr);
        root_ptr = tree_copy(source.root_ptr);
    }
 
    template <class Item>
    void bag<Item>::operator +=(const bag<Item>& addend)
        {
        if (root_ptr == addend.root_ptr)
        {
        bag<Item> copy = addend;
        insert_all(copy.root_ptr);
        }
        else
            insert_all(addend.root_ptr);
    }
 
    template <class Item>
    bag<Item> operator +(const bag<Item>& b1, const bag<Item>& b2)
    {
        bag<Item> answer = b1;
        answer += b2;
        return answer;
    }
 
    template <class Item>
    void bag<Item>::insert_all(binary_tree_node<Item>* addroot_ptr)
        // Precondition: addroot_ptr is the root pointer of a binary search tree that
        // is separate for the binary search tree of the bag that activated this
        // method.
        // Postcondition: All the items from the addroot_ptr's binary search tree
        // have been added to the binary search tree of the bag that activated this
        // method.
    {
        if (addroot_ptr != NULL)
        {
        insert(addroot_ptr->data( ));
        insert_all(addroot_ptr->left( ));
        insert_all(addroot_ptr->right( ));
        }
    }
}
Добавлено через 18 часов 31 минуту
Please, Help!!!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
14.04.2013, 22:15     Бинарное дерево поиска
Посмотрите здесь:

C++ Бинарное (двоичное) дерево поиска
C++ Бинарное дерево поиска знаков зодиака
C++ Вставить новый элемент в бинарное дерево поиска
C++ Структура, по строкам построить бинарное дерево поиска
Бинарное дерево поиска C++
C++ Бинарное дерево поиска C++
C++ Бинарное дерево поиска
C++ Бинарное дерево поиска

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

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

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