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

Бинарные деревья - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 21, средняя оценка - 4.76
Student100
3 / 3 / 2
Регистрация: 08.04.2011
Сообщений: 27
27.05.2011, 17:59     Бинарные деревья #1
Разработать набор классов упорядоченных бинарных деревьев поиска типов: вещественные числа, двоичные строки(строка из 0 и 1) и линейные многочлены (ax+b меньше cx+d если пара <a,b> меньше <c,d>). Двоичные строки и линейные многочлены сравниваются в лексикографмческом порядке.Я не пойму как это сделать((есть думки что нужно просто класс шаблон дерева и три класса этих типов(вещественные числа, двоичные строки и линейные многочлены).Подскажите как сделать?

пока что готов только класс шаблон дерева
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.05.2011, 17:59     Бинарные деревья
Посмотрите здесь:

C++ бинарные деревья
Бинарные деревья C++
Бинарные деревья C++
Бинарные деревья C++
C++ Бинарные деревья
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Nameless One
Эксперт С++
 Аватар для Nameless One
5753 / 3402 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
27.05.2011, 18:01     Бинарные деревья #2
Цитата Сообщение от Student100 Посмотреть сообщение
Я не пойму как это сделать((есть думки что нужно просто класс шаблон дерева и три класса этих типов(вещественные числа, двоичные строки и линейные многочлены).
правильно думаешь. Для классов типов должна быть перегружена операция <.
Student100
3 / 3 / 2
Регистрация: 08.04.2011
Сообщений: 27
27.05.2011, 18:04  [ТС]     Бинарные деревья #3
а можешь подказать как перегрузить оператор для двоичных строк и линейных многочленов?
kjahert
48 / 48 / 5
Регистрация: 08.04.2011
Сообщений: 124
27.05.2011, 18:05     Бинарные деревья #4
Есть примеры классов и структур деревьев
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
#include<iostream.h>
#include <alloc.h>
#include<math.h>
#include<conio.h>
#include<stdio.h>
#include<string.h>
 
class elem
 {
  public:
  int number;//room
  char FIO[40];
  int info[4];
  elem *left;
  elem *right;
 };
elem  AddNode(elem **root, int number,char FF[40],int infoo[4]);
void PrintTree(elem **root);
void SearchNode(elem **root);
void DelNode(elem **root);
void Del(elem **root, elem **rootl);
void Print(elem **root,int y,int x);
 
void main()
{ elem *root=NULL;
  elem *cons=NULL;
  int num,count;
  char F[40];
  int info[4];
  clrscr();
  cout<<"‚ўҐ¤ЁвҐ Є®«ЁзҐбвў® §*ЇЁбҐ©:\t";
  cin>>count;
  for (int i=1;i<=count;i++)
    {
    cout<<"‚ўҐ¤ЁвҐ *®¬Ґа бв㤥*в*:\n";
    cin>>num;
    cout<<"”.?.Ћ.:\n";
    cin>>F;
    cout<<"‚ўҐ¤ЁвҐ ®жҐ*ЄЁ(2-5):\n";
    for(int i=0;i<=3;i++)
    cin>>info[i];
    root=&AddNode(&root,num,F,info);
    }
  cout<<"„ҐаҐў®:"<<endl;
  cons=root;
  clrscr();
  Print(&root,10,20);
  getchar();
  root=cons;
  for ( i=1;i<=count;i++)
  DelNode(&root);
  clrscr();
  gotoxy(10,30);
  cout<<endl<<"ђҐ§г«мв*в:\n";
  Print(&root,10,20);
   getchar();
}
 
elem AddNode(elem **root, int number,char FF[40],int infoo[4])
{ if(*root==NULL)
   {
     *root=new elem;
     (*root)->number=number;
     for(int j=0;j<=3;j++)
     ((*root)->info)[j]=infoo[j];
     strcpy(((*root)->FIO),FF);
     (*root)->left=NULL;
     (*root)->right=NULL;
   }
    else
     if ((*root)->number>number)
      (*(*root)->left)=AddNode(&(*root)->left,number, FF,infoo);
     else
     if ((*root)->number<number)
      (* (*root)->right)=AddNode(&(*root)->right,number,FF,infoo);
return **root;
}
 
void DelNode(elem **root)
{int b=0;
      if ((*root)!=NULL)
    {
     for (int i=0;i<=3;i++ )
     { if (((*root)->info)[i]==5)
     b++;
     else  b=1;
     }
     if (b==4)
          { DelNode(&((*root)->left));
          DelNode(&((*root)->right));
        }
      else
        {
          elem *old=*root;
          if ((*root)->right==NULL)
           {
           *root=(*root)->left;
        delete old;
           }
           else
           if ((*root)->left==NULL)
        {
         *root=(*root)->right;
         delete old;
        }
        else
          Del(&old,&(*root)->left);
         }
      }
}
void Del(elem **root, elem **rootl)
{
   elem *old=new elem;
   if ((*rootl)->right==NULL)
    {
     (*root)->number=(*rootl)->number;
     old=*rootl;
     (*rootl)=(*rootl)->left;
     delete old;
    }
   else
   Del(&(*root),&((*root)->right));
}
 
void Print(elem **root,int y,int x)
 {if (*root != NULL){
    gotoxy(10+x,y);
    if ((*root)->left != NULL) cout << "/ {";
      else cout << " {";
    cout << (*root)->FIO<<": ";
     for (int i=0;i<=3;i++)
      cout<<((*root)->info)[i] ;
    if ((*root)->right != NULL) cout << "} \\";
       else cout << "} ";
    Print(&(*root)->left, y + 2, x - 6);
    Print(&(*root)->right, y + 2, x + 6);
}
    }
Структуры
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
//Tree
#include <iostream.h>
 
struct node{
 int d;
 node *left;
 node *right;
};
node * first(int d);
node * search_insert(node *root, int d);
void print_tree(node *root, int l);
//----------------------------------------------------
void main()
{
    int n, i, what;
    cout<<"input n \n";
    cin>>n;
    cout<<"input first what \n";
    cin>>what;
    node *root = first(what);
    for (i = 1; i<n; i++)
    {
    cout<<"input what \n";
    cin>>what;
    search_insert(root, what);
    }
    print_tree(root, 0);
 
}
//-----------------------------------------------------
node * first(int d)
{
    node *pv = new node;
    pv->d    = d;
    pv->left = 0;
    pv->right = 0;
    return pv;
}
//------------------------------------------------------
node * search_insert(node *root, int d)
{
    node *pv = root, *prev;
    int found = 0;
    while (pv && !found){
       prev = pv;
       if   (d == pv->d) found = 1;
       else if  (d <  pv->d)pv     = pv->left;
       else         pv     = pv->right;
    }
    if (found) return pv;
    node *pnew  = new node;
    pnew->d     = d;
    pnew->left  = 0;
    pnew->right = 0;
    if (d < prev->d)
       prev->left  = pnew;
    else
       prev->right = pnew;
    return pnew;
}
//-------------------------------------------------------
void print_tree(node *p, int level)
{
    if (p)
    {
    print_tree(p->left, level+1);
    for (int i = 0; i<level; i++)
    cout << "    ";
    cout <<  p->d << endl;
    print_tree(p->right, level + 1);
    }
}
Соответственно структуры легко переделать в классы

Цитата Сообщение от Student100 Посмотреть сообщение
вещественные числа, двоичные строки и линейные многочлены
Можно всё сделать в одном классе(структуре) а не в трёх

Сравнение строковых переменных в лексикограф. порядке
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
node *AddNode(node *root,char FIO[40],char info[15],char p[20])
{ if(root==0)
   {
     root=new node;
     strcpy((root->FIO),FIO);
     strcpy((root->string),info);
     strcpy((root->pr),p);
     root->left=0;
     root->right=0;
   }
    else
     if(strcmp (root->FIO,FIO)<0)
      root->left=AddNode(root->left,FIO,info,p);
     else
     if (strcmp (root->FIO,FIO)>0)
      root->right=AddNode(root->right,FIO,info,p);
return root;
}
Nameless One
Эксперт С++
 Аватар для Nameless One
5753 / 3402 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
27.05.2011, 21:30     Бинарные деревья #5
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Шаблонный класс двоичного дерева. Операции - добавление, удаление элементов с сохранением свойства упорядоченности; проверка, содержится ли элемент в дереве; является ли дерево пустым; очистка дерева; симметричный обход дерева. Файл tree.hpp:
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
#ifndef TREE_HPP
#define TREE_HPP
 
#include <stdexcept>
#include <vector>
#include <functional>
 
namespace my
{
    template <class T>
    class node
    {
    public:
    T value;
    node<T>* left;
    node<T>* right;
    };
    
    template <class T, class comp = std::less<T> >
    class tree
    {
    private:
    comp cmp;
    
    node<T>* root;
    void init(node<T>*&, const node<T>*&);
    void destruct(node<T>*&);
    void insert_leaf(node<T>*&, const T&);
    bool member(const node<T>*, const T&) const;
    void remove(node<T>*&, const T&) throw (std::runtime_error);
    const node<T>* findRightMost(const node<T>*);
    void traverse_symmetric(const node<T>*, std::vector<T>&) const;
    
    public:
    tree();
    tree(const tree<T, comp>&);
    ~tree();
    void insert(const T&);
    bool member(const T&) const;
    void remove(const T&) throw (std::runtime_error);
    bool empty() const;
    void clear();
    std::vector<T> traverse_symmetric() const;
    
    };
 
    template <class T, class comp>
    void tree<T, comp>::init(node<T>*& self, const node<T>*& p_node)
    {
    if(p_node == NULL)
        self = NULL;
    else
    {
        self = new node<T>;
        self->value = p_node->value;
        init(self->left, p_node->left);
        init(self->right, p_node->right);
    }
    }
 
    template <class T, class comp>
    void tree<T, comp>::destruct(node<T>*& p_node)
    {
    if(p_node)
    {
        destruct(p_node->left);
        destruct(p_node->right);
        delete p_node;
        p_node = NULL;
    }
    }
 
    template <class T, class comp>
    void tree<T, comp>::insert_leaf(node<T>*& p_node, const T& val)
    {
    if(p_node == NULL)
    {
        p_node = new node<T>;
        p_node->value = val;
        p_node->left = NULL;
        p_node->right = NULL;
    }
    else if(p_node->value == val)
        return;
    else if(cmp(p_node->value, val))
        insert_leaf(p_node->right, val);
    else if(cmp(val, p_node->value))
        insert_leaf(p_node->left, val);
    }
 
    template <class T, class comp>
    bool tree<T, comp>::member(const node<T>* p_node, const T& val) const
    {
    if(p_node == NULL)
        return false;
    else if(p_node->value == val)
        return true;
    else if(cmp(val, p_node->value))
        return member(p_node->left, val);
    else if(cmp(p_node->value, val))
        return member(p_node->right, val);
 
    // Этот код никогда не должен выполниться
    return false;
    }
 
    template <class T, class comp>
    void tree<T, comp>::remove(node<T>*& p_node, const T& val) throw (std::runtime_error)
    {
    if(p_node == NULL)
        throw std::runtime_error("Tree remove: no such element");
 
    if(p_node->value == val)
    {
        if(p_node->left == NULL)
        {
        node<T>* ptr = p_node;
        p_node = ptr->right;
        delete ptr;
        ptr = NULL;
        }
        else if(p_node->right == NULL)
        {
        node<T>* ptr = p_node;
        p_node = ptr->left;
        delete ptr;
        ptr = NULL;
        } else {
        const node<T>* rm = findRightMost(p_node->left);
        p_node->value = rm->value;
        remove(p_node->left, rm->value);
        }
    }
 
    else if(cmp(val, p_node->value))
        remove(p_node->left, val);
    else if(cmp(p_node->value, val))
        remove(p_node->right, val);
    }
 
    template <class T, class comp>
    const node<T>* tree<T, comp>::findRightMost(const node<T>* p_node)
    {
    if(p_node->right == NULL)
        return p_node;
    return findRightMost(p_node->right);
    }
 
    template <class T, class comp>
    void tree<T, comp>::traverse_symmetric(const node<T>* p_node,
                       std::vector<T>& vec) const
    {
    if(p_node == NULL)
        return;
    traverse_symmetric(p_node->left, vec);
    vec.push_back(p_node->value);
    traverse_symmetric(p_node->right, vec);
    }
    
    template <class T, class comp>
    tree<T, comp>::tree()
    : root(NULL)
    {
    }
 
    template <class T, class comp>
    tree<T, comp>::tree(const tree<T, comp>& rhs)
    {
    init(root, rhs.root);
    }
 
    template <class T, class comp>
    tree<T, comp>::~tree()
    {
    destruct(root);
    }
 
    template <class T, class comp>
    void tree<T, comp>::insert(const T& val)
    {
    insert_leaf(root, val);
    }
 
    template <class T, class comp>
    bool tree<T, comp>::member(const T& val) const
    {
    return member(root, val);
    }
 
    template <class T, class comp>
    void tree<T, comp>::remove(const T& val) throw (std::runtime_error)
    {
    remove(root, val);
    }
 
    template <class T, class comp>
    bool tree<T, comp>::empty() const
    {
    return root == NULL;
    }
 
    template <class T, class comp>
    void tree<T, comp>::clear()
    {
    destruct();
    }
 
    template <class T, class comp>
    std::vector<T> tree<T, comp>::traverse_symmetric() const
    {
    std::vector<T> vec;
    traverse_symmetric(root, vec);
    return vec;
    }
}
 
#endif
Класс битовой строки. Файл bits.hpp:
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
#ifndef BITS_HPP
#define BITS_HPP
 
#include <vector>
#include <stdexcept>
#include <iosfwd>
 
namespace my
{
    class bits
    {
    private:
    std::vector<bool> b;
 
    public:
    typedef std::vector<bool>::iterator iterator;
    typedef std::vector<bool>::const_iterator const_iterator;
    typedef std::vector<bool>::reference reference;
    typedef std::vector<bool>::const_reference const_reference;
    typedef std::vector<bool>::size_type size_type;
    typedef std::vector<bool>::difference_type difference_type;
    typedef std::vector<bool>::value_type value_type;
    typedef std::vector<bool>::allocator_type allocator_type;
    typedef std::vector<bool>::pointer pointer;
    typedef std::vector<bool>::const_pointer const_pointer;
    typedef std::vector<bool>::reverse_iterator reverse_iterator;
    typedef std::vector<bool>::const_reverse_iterator const_reverse_iterator;
                
    bits();
    bits(const bits&);
    bits(std::initializer_list<bool> lst);
    
    reference operator [] (size_t) throw (std::range_error);
    const_reference operator [] (size_t) const throw (std::range_error);
    
    size_t size() const;
    bool empty() const;
 
    iterator begin();
    const_iterator begin() const;
    iterator end();
    const_iterator end() const;
 
    bool operator == (const bits&) const;
    bool operator <  (const bits&) const;
    };
}
 
std::ostream& operator << (std::ostream&, const my::bits&);
 
#endif
Файл bits.cc:
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
#include "bits.hpp"
 
#include <iostream>
#include <algorithm>
#include <iterator>
 
namespace my
{
    bits::bits()
    : b()
    {
    }
 
    bits::bits(const bits& rhs)
    : b(rhs.b)
    {
    }
 
    bits::bits(std::initializer_list<bool> lst)
    : b(lst.begin(), lst.end())
    {
    }
 
    bits::reference bits::operator [] (size_t idx) throw (std::range_error)
    {
    if(idx >= b.size())
        throw std::range_error("Bits: index is out of range");
 
    return b[idx];
    }
 
    bits::const_reference bits::operator [] (size_t idx) const throw (std::range_error)
    {
    if(idx >= b.size())
        throw std::range_error("Bits: index is out of range");
 
    return b[idx];
    }    
 
    size_t bits::size() const
    {
    return b.size();
    }
 
    bool bits::empty() const
    {
    return b.empty();
    }
        
    bits::iterator bits::begin()
    {
    return b.begin();
    }
 
    bits::const_iterator bits::begin() const
    {
    return b.begin();
    }
 
    bits::iterator bits::end()
    {
    return b.end();
    }
 
    bits::const_iterator bits::end() const
    {
    return b.end();
    }
 
    bool bits::operator == (const bits& rhs) const
    {
    return (size() == rhs.size() && std::equal(begin(), end(), rhs.begin()));
    }
 
    bool bits::operator <  (const bits& rhs) const
    {
    return std::lexicographical_compare(begin(), end(), rhs.begin(), rhs.end());
    }
}
 
std::ostream& operator << (std::ostream& os, const my::bits& rhs)
{
    std::copy(rhs.begin(), rhs.end(), std::ostream_iterator<bool>(os, ""));
    return os;
}
Класс линейного многочлена. Файл linear_polynom.hpp:
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
#ifndef LINEAR_POLYNOM_HPP
#define LINEAR_POLYNOM_HPP
 
#include <iosfwd>
 
namespace my
{
    class linear_polynom
    {
    private:
    double a, b;
    
    public:
    linear_polynom();
    linear_polynom(double, double);
    linear_polynom(const linear_polynom&);
 
    double& first();
    const double& first() const;
    double& second();
    const double& second() const;
 
    bool operator == (const linear_polynom&) const;
    bool operator <  (const linear_polynom&) const;
    };
}
 
std::ostream& operator << (std::ostream&, const my::linear_polynom&);
 
#endif
Файл linear_polynom.cc:
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
#include "linear_polynom.hpp"
 
#include <iostream>
 
namespace my
{
    linear_polynom::linear_polynom()
    : a(), b()
    {
    }
 
    linear_polynom::linear_polynom(double f, double s)
    : a(f), b(s)
    {
    }
 
    linear_polynom::linear_polynom(const linear_polynom& rhs)
    : a(rhs.a), b(rhs.b)
    {
    }
 
    double& linear_polynom::first()
    {
    return a;
    }
 
    const double& linear_polynom::first() const
    {
    return a;
    }
    
    double& linear_polynom::second()
    {
    return b;
    }
 
    const double& linear_polynom::second() const
    {
    return b;
    }
 
    bool linear_polynom::operator == (const linear_polynom& rhs) const
    {
    return a == rhs.a && b == rhs.b;
    }
 
    bool linear_polynom::operator <  (const linear_polynom& rhs) const
    {
    if(a < rhs.a)
        return true;
    if(rhs.a < a)
        return false;
    return b < rhs.b;
    }    
}
 
std::ostream& operator << (std::ostream& os,
               const my::linear_polynom& rhs)
{
    double a = rhs.first();
    double b = rhs.second();
    if(a == 0)
    {
    if(b == 0)
        os << 0;
    else
        os << b;
    }
    else
    {
    os << a << "x";
    if(b > 0)
        os << " + " << b;
    else if(b < 0)
        os << " - " << -b;
    }
    return os;
}
Главный файл программы main.cc:
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
#include <iostream>
#include <cstdlib>
#include <iterator>
#include <algorithm>
 
#include "tree.hpp"
#include "bits.hpp"
#include "linear_polynom.hpp"
 
int main()
{
    my::tree<int> itree;
 
    std::cout << "Operations with tree of numbers:" << std::endl;
    
    for(int num: {25, 10, 40, 14, 22, 33, 9, 13, 2, 5, 7, 24, 18})
    {
    std::cout << "Adding number: " << num << std::endl;
    itree.insert(num);
    }
 
    std::vector<int> vec = itree.traverse_symmetric();
    std::cout << "Traversing initial integer tree:" << std::endl;
    std::copy(vec.begin(), vec.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl << std::endl;
 
    for(int num: {40, 13, 22, 6, 100500})
    {
    std::cout << "Removing number: " << num << std::endl;
    try
    {
        if(!itree.member(num))
        std::cout << "Warning: number " << num << " is not in tree; "
              << "an exception will be thrown" << std::endl;
        
        itree.remove(num);
    }
    catch(std::exception& e)
    {
        std::cerr << "Failed to remove number " << num << ": "
              << e.what() << std::endl;
    }
    }
 
    vec = itree.traverse_symmetric();
    std::cout << "Traversing integer tree with removed numbers:" << std::endl;
    std::copy(vec.begin(), vec.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl << std::endl;
 
    std::cout << "Operations with tree of bits:" << std::endl;
    
    my::bits bits[] = {{true, false, false, true},
               {true, false, true},
               {true},
               {true, false, true, true, false, true},
               {true, true, true},
               {true, false, false, false},
               {true, true, true, true, true, false, true},            
               {true, true, true, false, true}};
 
    my::tree<my::bits> btree;
 
    
    for(auto bit: bits)
    {
    std::cout << "Adding bit: " << bit << std::endl;
    btree.insert(bit);
    }
 
    std::vector<my::bits> bvec = btree.traverse_symmetric();
    
    std::cout << "Traversing initial bits tree:" << std::endl;
    
    for(auto bit: bvec)
    {
    std::cout << bit << std::endl;
    }
    
    std::cout << std::endl;
 
    std::cout << "Operations with tree of linear polynoms (lp-tree):" << std::endl;
 
    my::tree<my::linear_polynom> lptree;
 
    std::vector<my::linear_polynom> lpvec;
    
    lpvec.push_back(my::linear_polynom());
    lpvec.push_back(my::linear_polynom(0, 3));
    lpvec.push_back(my::linear_polynom(4, 5));
    lpvec.push_back(my::linear_polynom(2, 2));
    lpvec.push_back(my::linear_polynom(2, -3));
    lpvec.push_back(my::linear_polynom(4, 1));
    lpvec.push_back(my::linear_polynom(2, 0));
    lpvec.push_back(my::linear_polynom(-3, 2));
    lpvec.push_back(my::linear_polynom(5, 1));
    lpvec.push_back(my::linear_polynom(-1, 0));
    lpvec.push_back(my::linear_polynom(-4, -5));
    lpvec.push_back(my::linear_polynom(0, -5));
    
    for(auto lp: lpvec)
    {
    std::cout << "Adding linear polynom: " << lp << std::endl;
    lptree.insert(lp);
    }
 
    std::cout << "Traversing initial lp-tree:" << std::endl;
    lpvec = lptree.traverse_symmetric();
    for(auto lp: lpvec)
    {
    std::cout << lp << std::endl;
    }
    
    std::cout << std::endl;
    
    return 0;
}
Кстати, никто не подскажет, почему мне не удается вывести элементы векторов bvec, lpvec с помощью алгоритма std::copy?
Student100
3 / 3 / 2
Регистрация: 08.04.2011
Сообщений: 27
27.05.2011, 21:46  [ТС]     Бинарные деревья #6
СПАСИБО!!
Student100
3 / 3 / 2
Регистрация: 08.04.2011
Сообщений: 27
05.06.2011, 21:55  [ТС]     Бинарные деревья #7
Ааа!!народ выручайте((преподу не нравится решение задачи

Добавлено через 50 секунд
ворчит что всё замудрёно((ему надо проще сделать
Nursik77
05.06.2011, 21:56
  #8

Не по теме:

Student100, а что препод рядом сидит?

MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.06.2011, 22:25     Бинарные деревья
Еще ссылки по теме:

бинарные деревья С++ C++
C++ Бинарные деревья
Бинарные деревья C++

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

Или воспользуйтесь поиском по форуму:
Student100
3 / 3 / 2
Регистрация: 08.04.2011
Сообщений: 27
05.06.2011, 22:25  [ТС]     Бинарные деревья #9
ага и как решать подсказывает

Добавлено через 8 минут
файл TreeNode.h
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
template< typename T > class Tree;
template< typename T >
class TreeNode
{
    friend class Tree< T >;
 
public:
    TreeNode();
    TreeNode(const T &);
private:
    T _data;
    TreeNode< T > *_left;
    TreeNode< T > *_right;
};
файл TreeNode.cpp
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include "TreeNode.h"
template< typename T >
TreeNode< T >::TreeNode():
_left(0),
_right(0)
{
}
 
template< typename T >
TreeNode< T >::TreeNode(const T &data):
_data(data),
_left(0),
_right(0)
{
}
файл Tree.h
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include "TreeNode.cpp"
template< typename T >
class Tree
{
public:
    Tree();
    ~Tree();
    void insert(const T &);
    void remove(const T &);
    void print() const;
private:
    TreeNode< T > *_root;
    void insert_helper(TreeNode< T > **, const T &);
    void remove_helper(TreeNode< T > **, const T &);
    void delete_helper(TreeNode< T > *); 
    void print_helper(TreeNode< T >*, int) const;
};
файл Tree.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
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
#include "Tree.h"
template< typename T >
Tree< T >::Tree():
_root(0)
{
}
 
template< typename T >
Tree< T >::~Tree()
{
    delete_helper(_root);
}
 
template< typename T >
void Tree< T >::delete_helper(TreeNode< T > *node)
{
    if (node != 0)
    {
        delete_helper(node->_left);
        delete_helper(node->_right);
 
        delete node;
    }
}
 
template< typename T >
void Tree< T >::insert(const T &data)
{
    insert_helper(&_root, data);
}
 
template< typename T >
void Tree< T >::insert_helper(TreeNode< T > **node, const T &data)
{
    if (*node == 0)
        *node = new TreeNode< T > (data);
    else
    {
        if ((*node)->_data > data)
            insert_helper(&((*node)->_left), data);
        else
        {
            if ((*node)->_data < data)
                insert_helper(&((*node)->_right), data);
        }
    }
}
 
template< typename T >
void Tree< T >::remove(const T &data)
{
    remove_helper(&_root, data);
}
 
template< typename T >
void Tree< T >::remove_helper(TreeNode< T > **node, const T &data)
{
    if ((*node)->_data == data)
    {
        TreeNode< T > *del_node = *node;
 
        if ((*node)->_left == 0 && (*node)->_right == 0)
        {
            *node = 0;
 
            delete del_node;
        }
        else
        {
            if ((*node)->_left == 0)
            {
                *node = (*node)->_right;
 
                delete del_node;
            }
            else
            {
                if ((*node)->_right == 0)
                {
                    *node = (*node)->_left;
 
                    delete del_node;
                }
                else
                {
                    TreeNode< T > *p = *node;
                    TreeNode< T > *i = (*node)->_left;
 
                    while (i->_right != 0)
                    {
                        p = i;
                        i = i->_right;
                    }
 
                    *node = i;
                    p->_right = i->_left;
                    i->_right = del_node->_right;
                    i->_left = p;
 
                    delete del_node;
                }
            }
        }
    }
    else
    {
        if ((*node)->_data > data)
            remove_helper(&((*node)->_left), data);
        else
        {
            if ((*node)->_data < data)
                remove_helper(&((*node)->_right), data);
        }
    }
}
 
template< typename T >
void Tree< T >::print() const
{
    print_helper(_root, 0);
}
 
template< typename T >
void Tree< T >::print_helper(TreeNode< T > *node, int spaces) const
{
    while (node != 0)
    {
        print_helper(node->_right, spaces + 5);
 
        for (int i = 1; i < spaces; ++i)
            std::cout << ' ';
 
        std::cout << node->_data << std::endl;
        node = node->_left;
        spaces += 5;
    }
}
файл bits.h
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//двоичные строки(сравнивать в лексикографическом порядке)
#include "string.h"
#include <iostream>
using namespace std;
template< typename T > class Tree;
class bits
{
    public:
        char* data; 
        bits();
        ~bits();
        friend istream& operator>>(istream &,bits &);//перегруженный оператор ввода
        friend ostream& operator<<(ostream &,bits &);//перегруженный оператор вывода
        friend bool operator>(const bits &,const bits &);
        friend bool operator<(const bits &,const bits &);
};
файл bits.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
#include "bits.h"
bits::bits()
{
    data=new char[20];
}
bits::~bits()
{
    delete data;
}
bool operator>(const bits &tmp1,const bits &tmp2)
{
    int k=0;
    k=strcmp(tmp1.data,tmp2.data);
    if(k>0) 
        return true;
    else 
        return false;
}
bool operator<(const bits &tmp1,const bits &tmp2)
{
    int k=0;
    k=strcmp(tmp1.data,tmp2.data);
    if(k<0) 
        return true;
    else 
        return false;
}
std::ostream& operator <<(std::ostream &out,bits &t)//Стандартный оператор вывода.
{
    out<<t.data;
    return out;
}
std::istream& operator >>(std::istream &in,bits &t)//Стандартный оператор ввода.
{
    in.sync();
    in.clear();
    while (in.peek()!=10||in.eof())
    {
        in>>t.data;
    }
    return in;
}
главный файл
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include "stdafx.h"
#include "Tree.cpp"
#include "bits.cpp"
 
void main()
{
    Tree<bits> n;
    bits t;
    int i=0;
    for(i;i<3;i++)
    {
        cin>>t; 
        n.insert(t);//здесь он должен добавлять двоичные строки в дерево, но строка постоянно присваивается корню дерева((
    }
    n.print();
 
 
}
З.Ы. переделывал программу по другому

Добавлено через 19 минут
киньте хотя бы идейку как правильно сделать перегрузку оператора сравнения(
Yandex
Объявления
05.06.2011, 22:25     Бинарные деревья
Ответ Создать тему
Опции темы

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