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

Найти всех двойников в данном целочисленном бинарном дереве - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.83
fkty
1 / 1 / 0
Регистрация: 06.01.2013
Сообщений: 265
23.10.2013, 15:56     Найти всех двойников в данном целочисленном бинарном дереве #1
Здравствуйте,нужна помощь в задаче:назовем пару различных вершин дерева двойниками,если их значения и уровни совпадают.Найти всех двойников в данном целочисленном бинарном дереве.
Как сделать ввод с клавиатуры?и как реализовать поиск двойников,если в моем коде не может быть одинаковых значений?
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
//Программа формирует дерево из массива целых чисел и выводит его на экран
//root - корень дерева
#include <iostream>
#include <conio.h>
using namespace std;
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);     //Обход дерева
 
//-------------------------------------------
int main()
{
        int b[]={10,25,20,6,21,8,1,30}; 
        Node *root=first(b[0]);    //Формируем корень дерева
      //Ищем место куда вставить и вставляем новые элементы
       for(int i=1;i<8;i++)search_insert(root,b[i]); 
        print_tree(root,0);            //вывод дерева на экран
        getch();
        return 0;
}
 
//--------------------------------------------
//Формирование первого элемента
Node *first(int d){
Node *pv =new Node;   //Создаём элемент
pv->d=d;              //Присваиваем значение элементу поля
pv->left=0;           //Ссылка на левое поддерево равна NULL
pv->right=0;          //Ссылка на правое поддерево равна NULL
return pv;            //Возвращаем адрес элемента
}
 
//---------------------------------------------
 
//Поиск с включением
Node *search_insert(Node *root,int d){
Node*pv=root,*prev;
bool found = false;    //Переменная отвечающая за то что нашли ли элемент или нет
/*Ниже приведён алгоритм поиска короче если нашли такой же элемент то мы его не вставляем в дерево выходим из функции возвратив адрес совпавшего элемента*/
while(pv&&!found){
        prev=pv;                       //получаем адрес элемента от которого будем пускать корни
        if(d==pv->d)found=true;        //совпадение выходим из цикла
        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->right,level+1);          //Перемещение по правым поддеревьям     
                for(int i=0;i<level;i++)cout<<"   ";
                cout<<p->d<<'\n';                      //вывод значений дерева
                  print_tree(p->left,level+1);           //Перемещение по левым поддеревьям
                
     }
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.10.2013, 15:56     Найти всех двойников в данном целочисленном бинарном дереве
Посмотрите здесь:

C++ Количество листьев в бинарном дереве
Поиск ключа в бинарном дереве поиска C++
Сумма чисел в бинарном дереве C++
Строки в бинарном дереве C++
Поиск дубликатов в бинарном дереве C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Мимино
 Аватар для Мимино
180 / 151 / 5
Регистрация: 22.05.2013
Сообщений: 435
Записей в блоге: 1
23.10.2013, 16:05     Найти всех двойников в данном целочисленном бинарном дереве #2
Цитата Сообщение от fkty Посмотреть сообщение
и как реализовать поиск двойников,если в моем коде не может быть одинаковых значений?
Никак. Бинарное дерево по определению не может содержать повторяющиеся элементы. Они должны отсекаться на этапе добавления узлов.
Ilot
Модератор
Эксперт С++
1765 / 1140 / 221
Регистрация: 16.05.2013
Сообщений: 3,017
Записей в блоге: 5
Завершенные тесты: 1
23.10.2013, 16:18     Найти всех двойников в данном целочисленном бинарном дереве #3
Цитата Сообщение от fkty Посмотреть сообщение
Здравствуйте,нужна помощь в задаче:назовем пару различных вершин дерева двойниками,если их значения и уровни совпадают.Найти всех двойников в данном целочисленном бинарном дереве.
Как сделать ввод с клавиатуры?и как реализовать поиск двойников,если в моем коде не может быть одинаковых значений?
Вся проблема в том, что вы реализуете бинарное дерево поиска, а не просто бинарное дерево. Надеюсь данное замечание вам поможет.

Не по теме:

Есть довольно неплохая книга И.В.Красиков Алгоритмы просто как 2x2. Для новичка самое пожалуй то. Сам по ней учусь.

fkty
1 / 1 / 0
Регистрация: 06.01.2013
Сообщений: 265
23.10.2013, 19:44  [ТС]     Найти всех двойников в данном целочисленном бинарном дереве #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
#include <iostream>
#include <conio.h>
#include <stdlib.h>
#include <stdio.h>
using namespace std;
//Наша структура
struct node
{
    int info; //Информационное поле
    node *l, *r;//Левая и Правая часть дерева
};
 
node * tree=NULL; //Объявляем переменную, тип которой структура Дерево
 
/*ФУНКЦИЯ ЗАПИСИ ЭЛЕМЕНТА В БИНАРНОЕ ДЕРЕВО*/
void push(int a,node **t)
{
    if ((*t)==NULL) //Если дерева не существует
    {
        (*t)=new node; //Выделяем память
        (*t)->info=a; //Кладем в выделенное место аргумент a
        (*t)->l=(*t)->r=NULL; //Очищаем память для следующего роста
        return; //Заложили семечко, выходим
    }
       //Дерево есть
        if (a>(*t)->info) push(a,&(*t)->r); //Если аргумент а больше чем текущий элемент, кладем его вправо
        else push(a,&(*t)->l); //Иначе кладем его влево
}
 
/*ФУНКЦИЯ ОТОБРАЖЕНИЯ ДЕРЕВА НА ЭКРАНЕ*/
void print (node *t,int u) 
{
    if (t==NULL) return; //Если дерево пустое, то отображать нечего, выходим
    else //Иначе
    {
    print(t->l,++u);//С помощью рекурсивного посещаем левое поддерево
    for (int i=0;i<u;++i) cout<<"|";
    cout<<t->info<<endl; //И показываем элемент
    u--;
    }
    print(t->r,++u); //С помощью рекурсии посещаем правое поддерево
}
 
void main ()
{   
    int n; //Количество элементов
    int s; //Число, передаваемое в дерево
    cout<<"введите количество элементов  ";
    cin>>n; //Вводим количество элементов
 
    for (int i=0;i<n;++i)
    {
    cout<<"введите число  ";
    cin>>s; //Считываем элемент за элементом
   
    push(s,&tree); //И каждый кладем в дерево
    }
    cout<<"ваше дерево\n";
    print(tree,0);
    getch();       
}
Добавлено через 2 часа 5 минут
вот все переделала,но выводит неправильно.
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
#include <iostream>
#include <conio.h>
#include <stdlib.h>
#include <stdio.h>
#include <clocale>
using namespace std;
//Наша структура
struct node
{
    int d;//элементы дерева
    node *l, *r;//Левая и Правая часть дерева
};
 
void MakeSubTrees(node *leaf)
{
    node *Top;int key;
    cout<<"введите текущий узел";
    cin>>leaf->d;
    cout<<"он имеет левое поддерево?";
    cin>>key;
    if (key==1)
    {
        (Top)=new node;
        leaf->l=Top;
        MakeSubTrees(Top);
    }
    else
        leaf->l=NULL;
    cout<<"он имеет правое поддерево?";
    cin>>key;
    if (key==1)
    {
        (Top)=new node;
        leaf->r=Top;
        MakeSubTrees(Top);
    }
    else
        leaf->r=NULL;
}
 
void MakeTree(node **Top)
{
    (*Top)=new node;
    MakeSubTrees(*Top);
}
 
int High(node *Top)
{ 
    int Highleft,Highright,H;
    if (Top==NULL)
        H=0;
    else
    {
        Highleft=High(Top->l);
        Highright=High(Top->r);
        if (Highleft>Highright)
            H=Highleft+1;
        else
        H=Highright+1;
    }
    return H;
}
void WayHoriz(node *Top,int level)
{
    if (Top!=NULL)
        if (level==1)
            cout<<Top->d;
        else
        {
            WayHoriz(Top->l,level-1);
            WayHoriz(Top->r,level-1);
        }
}
void ViewTree(node Top)
{
    int i,HighTree;
    HighTree=High(&Top);
    for (int i=0;i<HighTree;i++)
    {
        WayHoriz(&Top, i);
    }
}
void main()
{
    setlocale(LC_CTYPE, "Russian");
    node *Top;
    MakeTree(&Top);
    ViewTree(*Top);
    getch();
    return;
}
zer0mail
2185 / 1868 / 187
Регистрация: 03.07.2012
Сообщений: 6,640
Записей в блоге: 1
23.10.2013, 20:13     Найти всех двойников в данном целочисленном бинарном дереве #5
Цитата Сообщение от Мимино Посмотреть сообщение
Никак. Бинарное дерево по определению не может содержать повторяющиеся элементы. Они должны отсекаться на этапе добавления узлов.
Мимино, кто же запретил бинарному дереву иметь узлы с одинаковыми значениями?
Мимино
 Аватар для Мимино
180 / 151 / 5
Регистрация: 22.05.2013
Сообщений: 435
Записей в блоге: 1
23.10.2013, 20:52     Найти всех двойников в данном целочисленном бинарном дереве #6
Цитата Сообщение от zer0mail Посмотреть сообщение
Мимино, кто же запретил бинарному дереву иметь узлы с одинаковыми значениями?
Я имел в виду дерево бинарного поиска.
zer0mail
2185 / 1868 / 187
Регистрация: 03.07.2012
Сообщений: 6,640
Записей в блоге: 1
23.10.2013, 21:16     Найти всех двойников в данном целочисленном бинарном дереве #7
Сам домыслил - сам раскритиковал - сам опроверг
Мимино
 Аватар для Мимино
180 / 151 / 5
Регистрация: 22.05.2013
Сообщений: 435
Записей в блоге: 1
24.10.2013, 15:12     Найти всех двойников в данном целочисленном бинарном дереве #8
Цитата Сообщение от zer0mail Посмотреть сообщение
Сам домыслил
Не сам домыслил. Код ТСа описывает именно дерево поиска. Там же сразу при добавлении данных не пропускаются дубли.
fkty
1 / 1 / 0
Регистрация: 06.01.2013
Сообщений: 265
28.10.2013, 20:43  [ТС]     Найти всех двойников в данном целочисленном бинарном дереве #9
вот итоговый вариант ввода и вывода.помогите пожалуйста с двойниками
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
//назовем пару различных вершин дерева двойниками,если их значения и уровни совпадают.найти 
//всех двойников в данном целочисленном бинарном дереве
#include <iostream>
#include <conio.h>
#include <stdlib.h>
#include <stdio.h>
#include <clocale>
using namespace std;
 
struct node
{
    int d;//элементы дерева
    node *l, *r;//Левая и Правая часть дерева
};
 
//создание поддерева
void MakeSubTrees(node *leaf)
{
    node *Top;int key;
    cout<<"введите текущий узел"<<endl;
    cin>>leaf->d;
    cout<<leaf->d<<" имеет левое поддерево?"<<endl;
    cin>>key;
    if (key==1)
    {
        (Top)=new node;
        leaf->l=Top;
        MakeSubTrees(Top);
    }
    else
        leaf->l=NULL;
    cout<<leaf->d<<" имеет правое поддерево?"<<endl;
    cin>>key;
    if (key==1)
    {
        (Top)=new node;
        leaf->r=Top;
        MakeSubTrees(Top);
    }
    else
        leaf->r=NULL;
}
 
//создание дерева
void MakeTree(node **Top)
{
    (*Top)=new node;
    MakeSubTrees(*Top);
}
 
void ViewTree(node *Top,int level)
{
    if (Top){
        ViewTree(Top->l,level+1);
        for (int i=0;i<level;i++)
            cout<<"   ";
        cout<<Top->d<<endl;
        ViewTree(Top->r,level+1);
    }
}
 
void main()
{
    setlocale(LC_CTYPE, "Russian");
    node *Top;
    MakeTree(&Top);
    ViewTree(Top,0);
    getch();
    return;
}
fkty
1 / 1 / 0
Регистрация: 06.01.2013
Сообщений: 265
11.11.2013, 16:44  [ТС]     Найти всех двойников в данном целочисленном бинарном дереве #10
помогите пожалуйста с двойниками....вот приблизительный план:обходим дерево(например обратный обход);берем какую-нибудь вершину k с уровня L;снова перебираем с корня до этого уровня L;если k==ai,то выводим пару двойников
fkty
1 / 1 / 0
Регистрация: 06.01.2013
Сообщений: 265
12.11.2013, 19:17  [ТС]     Найти всех двойников в данном целочисленном бинарном дереве #11
вот функция прямого обхода
C++
1
2
3
4
5
6
7
8
void WayUpDown(node *Top)
{ 
    if (Top==NULL)
        return;
    cout<<Top->d;
    WayUpDown(Top->l);
    WayUpDown(Top->r);
}
zitxbit
Master C/C++
 Аватар для zitxbit
86 / 738 / 75
Регистрация: 11.04.2012
Сообщений: 971
09.12.2013, 21:20     Найти всех двойников в данном целочисленном бинарном дереве #12
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
#include <iostream>
#include <conio.h>
#include <stdlib.h>
#include <stdio.h>
#include <clocale>
using namespace std;
 
struct node
{
    int d;//элементы дерева
    node *l, *r, *p;//Левая и Правая часть дерева
};
 
struct leaf
{
    node* nd;
    int level;
};
 
leaf* plf = NULL;
 
//создание поддерева
void MakeSubTrees(node *leaf)
{
    node *Node;int key;
    cout<<"введите текущий узел"<<endl;
    cin>>leaf->d;
    cout<<leaf->d<<" имеет левое поддерево?"<<endl;
    cin>>key;
    if (key==1)
    {
        (Node)=new node;
        Node->p = leaf;
        leaf->l=Node;
        MakeSubTrees(Node);
    }
    else
        leaf->l=NULL;
    cout<<leaf->d<<" имеет правое поддерево?"<<endl;
    cin>>key;
    if (key==1)
    {
        (Node)=new node;
        Node->p = leaf;
        leaf->r=Node;
        MakeSubTrees(Node);
    }
    else
        leaf->r=NULL;
}
 
//создание дерева
void MakeTree(node **Top)
{
    (*Top)=new node;
    (*Top)->p = NULL;
    MakeSubTrees(*Top);
 
    printf("\n");
}
 
void WayUpDown(node *Top)
{ 
    if (Top==NULL)
        return;
    
    static int n = 0;
    int level = 0; node* tmp = Top;
    while (tmp->p != NULL) 
    {
        tmp = tmp->p;
        level++;
    }
    
    if (plf == NULL)
        plf = (leaf*)malloc(sizeof(leaf) + 4);
 
    plf[n].level = level;
    plf[n++].nd = Top;
 
    plf = (leaf*)realloc(plf,(sizeof(leaf) + 4) * (n + 1));
 
    WayUpDown(Top->l);
    WayUpDown(Top->r);
} 
 
int MaxLevel(leaf* plf)
{
    int max = 0;
    for (int i = 0; plf[i].level >= 0; i++)
        max = (plf[i].level > plf[max].level) ? i : max;
    return (plf[max].level >= 0) ? plf[max].level : -1;
}
 
void Normalize(leaf* plf)
{
    for (int i = 0; plf[i].level >= 0; i++)
    {
        int r = i, count = 0;
        for (int t = 0; plf[t].level >= 0; t++)
            if ((plf[t].level == plf[i].level) && 
                (plf[t].nd->d == plf[i].nd->d) && (i != t))
                count = count + 1;
 
        while(plf[r].level >= 0 && count <= 0)
         { plf[r] = plf[r+1]; r++; }
 
        if (count <= 0) i--;
    }
}
 
void ViewTwins(leaf* plf)
{
    int len = MaxLevel(plf); Normalize(plf);
    for (int level = 0; level <= len; level++)
    {
        cout<<"Уровень ("<<level<<"): ";
        for (int i = 0; plf[i].level >= 0; i++)
            if (plf[i].level == level)
                cout<<plf[i].nd->d<<" ";
 
        cout<<endl;
    }
}
 
void ViewTree(node *Top,int level)
{
    if (Top){
        ViewTree(Top->l,level+1);
        for (int i=0;i<level;i++)
            cout<<"   ";
        cout<<Top->d<<endl;
        ViewTree(Top->r,level+1);
    }
}
 
void main()
{
    setlocale(LC_CTYPE, "Russian");
    node *Top;
    MakeTree(&Top);
    //ViewTree(Top,0);
    WayUpDown(Top);
    ViewTwins(plf);
    _getch();
    return;
}
FIDES
2 / 2 / 0
Регистрация: 21.12.2014
Сообщений: 88
31.01.2016, 23:00     Найти всех двойников в данном целочисленном бинарном дереве #13
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
#include <iostream>
#include <iomanip>
#include <locale.h>
#include <fstream>
using namespace std;
 
struct tree
{
    int info;
    tree *left, *right;
};
 
//Прототипы
tree * MakeTree(int level);                                 //Создает бинарное дерево
tree * MakeTreeAuto(int level, ifstream & in);              //Создает бинарное дерево из файла
void PrintTree(tree * root, int level);                     //Выводит бинарное дерево на экран
void FindClone(tree * root);                                //Находит элементы-двойники
void SearchClone(tree * root, int level, int SearchLevel,   //Поиск двойников по уровням
                    int & TempPosition, int *LevelValues);
int MaxLevel(tree * root, int level);                       //Вычисляет максимальный уровень бинарного дерева
void SrchInArr(int * LevelValues, int TempPosition);        //Поиск двойников по массиву
 
void main()
{
    setlocale(LC_ALL,"Russian");
    tree * root;    //Инициализуем дерево
 
    cout << "1)Ввести новое дерево" << endl;
    cout << "2)Загрузить дерево A" << endl;
    cout << "3)Загрузить дерево B" << endl;
    cout << "4)Загрузить дерево C" << endl;
    int Select;
    cin >> Select;
 
    switch(Select)
    {
    case 1: 
        {
            root = MakeTree(0); //Создаем и заполняем бинарное дерево
            break;
        }
    case 2:
        {
            ifstream in;        //Поток in будем использовать для чтения
            in.open("1.txt");   //Открываем файл для чтения
            root = MakeTreeAuto(0,in);
            break;
        }
    case 3:
        {
            ifstream in;        //Поток in будем использовать для чтения
            in.open("2.txt");   //Открываем файл для чтения
            root = MakeTreeAuto(0,in);
            break;
        }
    case 4:
        {
            ifstream in;        //Поток in будем использовать для чтения
            in.open("3.txt");   //Открываем файл для чтения
            root = MakeTreeAuto(0,in);
            break;
        }
    default: return;    //Если выбор неверный - завершаем программу
    }
 
    cout << "Исходное дерево:" << endl;
    PrintTree(root, 0);
 
    cout << "Максимальный уровень " << MaxLevel(root, 0) << endl;
 
    FindClone(root);
 
    system("pause");
    return;
}
 
//Создает бинарное дерево(из файла)
tree * MakeTreeAuto(int level, ifstream & in)
{
    int c;      //Переменная для хранения текущего значения
    in >> c;    //Считываем из файла число(или переходим на следующее через пробел)
    if (c)      //Если это число не ноль то создаем ветвь
    {
        tree * p = new tree;
        p -> info = c;          //Присваиваем это значение ветви
 
        p -> left = MakeTreeAuto (level + 1, in);   //Создаем правое поддерево
 
        p -> right = MakeTreeAuto (level + 1, in);  //Создаем левое поддерево
 
        return p;
    }
    else
        return NULL;
}
 
//Создает бинарное дерево
tree * MakeTree(int level)
{
    char c;
    cout << setw(4*level) << "" << "Создать вершину? (y/n)" << endl;
    cin >> c;
 
    if (c == 'y')
    {
        tree * p = new tree;
        cout << setw(4*level) << "" << "Введите значение вершины" << endl;
        cin >> p -> info;
 
        cout << setw(4*level) << "" << "Левое поддерево вершины " << p -> info << endl;
        p -> left = MakeTree (level + 1);
 
        cout << setw(4*level) << "" << "Правое поддерево вершины " << p -> info << endl;
        p -> right = MakeTree (level + 1);
 
        return p;
    }
    else
        return NULL;
}
 
//Выводит бинарное дерево на экран
void PrintTree(tree * root, int level)
{
    if (root)
    {
        PrintTree(root -> left,level+1);
        cout <<setw(4*level)<< root -> info << endl;
        PrintTree(root -> right, level+1);
    }
    return;
}
 
//Вычисляет максимальный уровень бинарного дерева
int MaxLevel(tree * root, int level)
{
    if (root)
    {
        int left = MaxLevel(root -> left, level +1);    //Просматриваем левое поддерево
        int right = MaxLevel(root -> right, level +1);  //Просматриваем правое поддерево
        return max(left,right);                         //Возвращаем наибольшее значение уровня
    }
    else
        return level-1;
}
 
//Находит элементы-двойники
void FindClone(tree * root)
{
    if (root)
    {
        for (int i = 0; i <= MaxLevel(root,0); i++) //Проходим циклом от корня дерева до максимального уровня
        {
            int *LevelValues = new int[50]; //Значения текущего уровня(не более 50-ти)
            int TempPosition = 0;           //Текущая позиция в массиве значений
            SearchClone(root, 0, i, TempPosition, LevelValues);
            cout << "Элементы находящиеся на " << i << "-м уровне:" <<endl;
            for(int j = 0; j < TempPosition; j++)
                cout << LevelValues[j]<< " ";
            cout << endl;
            SrchInArr(LevelValues,TempPosition);
        }
    }
    return;
}
 
//Поиск клонов по уровням
void SearchClone(tree * root, int level, int SearchLevel , int & TempPosition, int *LevelValues)
{
    if (root)
    {
        if (level <= SearchLevel)   //Если этот уровень не больше, чем искомый
        {
            if (level == SearchLevel)
            {
                LevelValues[TempPosition] = root -> info;
                //cout << "Нашел элемент " << level << "-го уровня: " << root -> info << endl;  //!!ДЛЯ ОТЛАДКИ!!
                TempPosition ++;
            }
            else
            {
                SearchClone(root->left, level+1, SearchLevel, TempPosition, LevelValues);
                SearchClone(root->right, level+1, SearchLevel, TempPosition, LevelValues);
            }
        }
        else
            return;
    }
    return;
}
 
//Поиск двойников по массиву
void SrchInArr(int * LevelValues, int TempPosition)
{
    bool Check = false; //Наличие двойников
    int Temp;           //Текущий элемент массива
    for (int i = 0; i < TempPosition-1; i++)
    {
        Temp = LevelValues[i];
        for (int j = i+1; j < TempPosition; j++)
            if (Temp == LevelValues[j])
            {
                cout << "Найден двойник: " << Temp << endl;
                Check = true;
            }
    }
    if (!Check)
        cout << "Двойники не найдены" << endl;
 
    return;
}

Короче там ещё подключи 3 файла в формате .txt с названиями 1, 2, 3 где и добавь бинарное дерево.
fkty
1 / 1 / 0
Регистрация: 06.01.2013
Сообщений: 265
01.02.2016, 09:27  [ТС]     Найти всех двойников в данном целочисленном бинарном дереве #14
спасибо
FIDES
2 / 2 / 0
Регистрация: 21.12.2014
Сообщений: 88
01.02.2016, 12:05     Найти всех двойников в данном целочисленном бинарном дереве #15
fkty, Если интересно могу исходник скинуть) Но это наверное была ваша лабораторная, и уже теперь не интересно
fkty
1 / 1 / 0
Регистрация: 06.01.2013
Сообщений: 265
01.02.2016, 16:29  [ТС]     Найти всех двойников в данном целочисленном бинарном дереве #16
интересно =)
FIDES
2 / 2 / 0
Регистрация: 21.12.2014
Сообщений: 88
01.02.2016, 17:04     Найти всех двойников в данном целочисленном бинарном дереве #17
fkty, держите
Вложения
Тип файла: rar Lab_3.rar (4.22 Мб, 7 просмотров)
fkty
1 / 1 / 0
Регистрация: 06.01.2013
Сообщений: 265
01.02.2016, 17:05  [ТС]     Найти всех двойников в данном целочисленном бинарном дереве #18
FIDES, спасибо
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.02.2016, 17:06     Найти всех двойников в данном целочисленном бинарном дереве
Еще ссылки по теме:

Как в бинарном дереве у всех листьев вычесть введенное число? C++
C++ Разобраться в бинарном дереве
C++ В данном бинарном файле, компоненты которого являются действительными числами, найти min и max

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

Или воспользуйтесь поиском по форуму:
FIDES
2 / 2 / 0
Регистрация: 21.12.2014
Сообщений: 88
01.02.2016, 17:06     Найти всех двойников в данном целочисленном бинарном дереве #19
fkty, незачто, о вы оказывается тоже с Ижа
Yandex
Объявления
01.02.2016, 17:06     Найти всех двойников в данном целочисленном бинарном дереве
Ответ Создать тему
Опции темы

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