При выполнении лабораторной работы для каждого задания требуется написать программу на языке С++, в которой выполнено формирование бинарного дерева; осуществлен обход построенного дерева в соответствии со своим вариантом; нахождение указанной вершины в дереве; добавление вершины в дерево; удаление вершины из дерева. Все перечисленные действия оформить в виде функций.
Вот мой вариант задания: Написать функцию, которая определяет,входит ли вершина, содержащая информационное поле E, в заданное бинарное дерево дважды.
Помогите доделать программу:
| 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
| #include <iostream>
#include <random>
#include <time.h>
using namespace std;
struct BinaryTree
{
int Data; //поле данных
BinaryTree* Left; //указатель на левый потомок
BinaryTree* Right; //указатель на правый потомок
};
BinaryTree* BTree = NULL;
//создание бинарного дерева
void Make_Binary_Tree(BinaryTree** Node, int n)
{
BinaryTree** ptr;//вспомогательный указатель
srand(time(NULL)*1000);
while (n > 0) {
ptr = Node;
while (*ptr != NULL) {
if ((double) rand()/RAND_MAX < 0.5)
ptr = &((*ptr)->Left);
else ptr = &((*ptr)->Right);
}
(*ptr) = new BinaryTree();
cout << "Введите значение: ";
cin >> (*ptr)->Data;
n--;
}
}
//печать бинарного дерева
void Print_BinaryTree(BinaryTree* Node, int l)
{
int i;
if (Node != NULL) {
Print_BinaryTree(Node->Right, l+1);
for (i=0; i< l; i++) cout << " ";
printf ("%4ld", Node->Data);
Print_BinaryTree(Node->Left, l+1);
}
else cout << endl;
}
//вставка вершины в бинарное дерево
void Insert_Node_BinaryTree(BinaryTree** Node,int Data)
{
BinaryTree* New_Node = new BinaryTree;
New_Node->Data = Data;
New_Node->Left = NULL;
New_Node->Right = NULL;
BinaryTree** ptr = Node;//вспомогательный указатель
srand(time(NULL)*1000);
while (*ptr != NULL) {
double q = (double) rand()/RAND_MAX;
if ( q < 1/3.0) ptr = &((*ptr)->Left);
else if ( q > 2/3.0) ptr = &((*ptr)->Right);
else break;
}
if (*ptr != NULL) {
if ( (double) rand()/RAND_MAX < 0.5 )
New_Node->Left = *ptr;
else New_Node->Right = *ptr;
*ptr = New_Node;
}
else{
*ptr = New_Node;
}
}
//удаление вершины из бинарного дерева
void Delete_Node_BinaryTree(BinaryTree** Node,int Data)
{
if ( (*Node) != NULL ){
if ((*Node)->Data == Data){
BinaryTree* ptr = (*Node);
if ( (*Node)->Left == NULL && (*Node)->Right == NULL ) (*Node) = NULL;
else if ((*Node)->Left == NULL) (*Node) = ptr->Right;
else if ((*Node)->Right == NULL) (*Node) = ptr->Left;
else {
(*Node) = ptr->Right;
BinaryTree ** ptr1;
ptr1 = Node;
while (*ptr1 != NULL)
ptr1 = &((*ptr1)->Left);
(*ptr1) = ptr->Left;
}
delete(ptr);
Delete_Node_BinaryTree(Node,Data);
}
else {
Delete_Node_BinaryTree(&((*Node)->Left),Data);
Delete_Node_BinaryTree(&((*Node)->Right),Data);
}
}
}
//проверка пустоты бинарного дерева
bool Empty_BinaryTree(BinaryTree* Node)
{
return ( Node == NULL ? true : false );
}
//освобождение памяти, выделенной под бинарное дерево
void Delete_BinaryTree(BinaryTree* Node)
{
if (Node != NULL) {
Delete_BinaryTree(Node->Left);
Delete_BinaryTree(Node->Right);
delete(Node);
}
}
int main()
{
setlocale(LC_ALL, "RUS");
cout << "Введите размер дерева: ";
int TreeLen; cin >> TreeLen;
Make_Binary_Tree(&BTree, TreeLen);
cout << "\n~~~~~~~~~~~\nДерево:\n";
Print_BinaryTree(BTree, TreeLen);
system("pause");
return 0;
} |
|
(
