Доброго времени суток. Возникла небольшая сложность в создании не бинарных деревьев.
Смысл я понял: надо создать элемент с ключом и список или массив(как у меня) с его сыновьями.
вот код:
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
| //---------------------------------------------------------------------------
#pragma argsused
#pragma hdrstop
#include <tchar.h>
#include <stdlib.h>
#include <iostream>
#include <conio.h>
using namespace std;
//---------------------------------------------------------------------------
//Задача 20. Найти поддерево не включающее ни одну из заданных вершин
//---------------------------------------------------------------------------
class Making
{
private:
int count; //количество элементов дерева
int sons; //количество сыновей дерева
bool f_sons; //флаг идентификации корня дерева
struct Tree //структура дерева
{
int key; //ключ
Tree *arr; //массив сыновей элемента
};
void processing(int count) //формирование эл-ов дерева
{
cout << "\nEnter the number of sons of the element (available "
<< count-1
<< ") : ";
cin >> sons;
while (sons < f_sons || sons > count-1) //обработка ввода
{
cerr << "Wrong input! Number of sons of the tree can not be"
<< " less than 1 or you \nexceed the allowable number"
<< " of sons\nRepeat\n> ";
cin >> sons;
}
if(f_sons)
{
count--;
f_sons = false; //прекращение обработки корня
Tree *root = new Tree;
root->key = count; //присвоение ключа корню дерева
root->arr = new Tree [sons]; //выделение памяти под его сыновей
for(int i(0);i<sons;i++)
{
count--;
root->arr[i] = *create_sons();
}
}
if (count) processing(count);
}
Tree *create_sons()
{
Tree *temp = new Tree;
temp->key = count;
temp->arr = NULL;
return temp;
}
public:
void start();
void show();
~Making();
};
//---------------------------------------------------------------------------
void Making::start()
{
system("CLS");
cout << "Welcome to the construction of binary trees.\n\n"
<< "Follow the instructions.\n\n"
<< "Enter the root of the tree. Attention!\nOn a selected number will"
<< " depend on the number of items in the subtrees.\nThus, the root "
<< "is recommended to choose based on the total number "
<< "of elements\nin the tree. \n\nInput: ";
cin >> count;
while (count < 1) //обработка ввода
{
cerr << "Wrong input! Root of the tree can not be less than 0"
<< "\nRepeat\n> ";
cin >> count;
}
f_sons = true; //обрабатывать корень
processing(count); //добавление элементов дерева в само дерево
}
void Making::show()
{
}
Making::~Making()
{
cout << "\n\nPress enter to exit...";
}
//---------------------------------------------------------------------------
int _tmain(int argc, _TCHAR* argv[])
{
Making tree;
tree.start();
tree.~Making();
getch();
return 0;
}
//--------------------------------------------------------------------------- |
|
Подскажите пожалуйста как дальше писать, а то корень с детьми я создаю, а как дальше просматривать не могу реализовать. Есть идея спрашивать у каждого листа нужны ли ему дети