-
Notifications
You must be signed in to change notification settings - Fork 0
/
BstUsADT.c
189 lines (173 loc) · 6.23 KB
/
BstUsADT.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
// Filename BstUsADT.c
/* ΥΛΟΠΟΙΗΣΗ ΔΔΑ ΔΥΝΑΜΙΚΑ ΜΕ ΔΕΙΚΤΕΣ
ΤΑ ΣΤΟΙΧΕΙΑ ΤΩΝ ΚΟΜΒΩΝ ΤΟΥ ΔΔΑ ΕΙΝΑΙ ΤΥΠΟΥ struct*
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "BstUsADT.h"
void CreateBST(BinTreePointer *Root)
/* Λειτουργία: Δημιουργεί ένα κενό ΔΔΑ.
Επιστρέφει: Τον μηδενικό δείκτη(NULL) Root
*/
{
*Root = NULL;
}
boolean EmptyBST(BinTreePointer Root)
/* Δέχεται: Ενα ΔΔα με το Root να δείχνει στη ρίζα του.
Λειτουργία: Ελέγχει αν το ΔΔΑ είναι κενό.
Επιστρέφει: TRUE αν το ΔΔΑ είναι κενό και FALSE διαφορετικά
*/
{ return (Root==NULL);
}
void BSTInsert(BinTreePointer *Root, BinTreeElementType Item)
/* Δέχεται: Ένα ΔΔΑ με το δείκτη Root να δείχνει στη ρίζα του και ένα στοιχείο Item.
Λειτουργία: Εισάγει το στοιχείο Item στο ΔΔΑ.
Επιστρέφει: Το τροποποιημένο ΔΔΑ με τον δείκτη Root να δείχνει στη ρίζα του
*/
{
BinTreePointer LocPtr, Parent;
boolean Found;
LocPtr = *Root;
Parent = NULL;
Found = FALSE;
while (!Found && LocPtr != NULL) {
Parent = LocPtr;
if (Item.id < LocPtr ->Data.id)
LocPtr = LocPtr ->LChild;
else if (Item.id > LocPtr ->Data.id)
LocPtr = LocPtr ->RChild;
else
Found = TRUE;
}
if (Found)
printf("To %c EINAI HDH STO DDA\n", Item);
else {
LocPtr = (BinTreePointer)malloc(sizeof (struct BinTreeNode));
// LocPtr ->Data = Item;
LocPtr ->Data.id = Item.id;
strcpy(LocPtr ->Data.password,Item.password);
LocPtr ->LChild = NULL;
LocPtr ->RChild = NULL;
if (Parent == NULL)
*Root = LocPtr;
else if (Item.id < Parent ->Data.id)
Parent ->LChild = LocPtr;
else
Parent ->RChild = LocPtr;
}
}
void BSTSearch(BinTreePointer Root, BinTreeElementType KeyValue, boolean *Found, BinTreePointer *LocPtr)
/* Δέχεται: Ένα ΔΔΑ με το δείκτη Root να δείχνει στη ρίζα του και μια τιμή KeyValue.
Λειτουργία: Αναζητά στο ΔΔΑ έναν κόμβο με τιμή KeyValue στο πεδίο κλειδί του.
Επιστρέφει: Η Found έχει τιμή TRUE και ο δείκτης LocPtr δείχνει στον κόμβο που
περιέχει την τιμή KeyValue, αν η αναζήτηση είναι επιτυχής.
Διαφορετικά η Found έχει τιμή FALSE
*/
{
boolean stop;
*LocPtr = Root;
stop = FALSE;
while (!stop && *LocPtr != NULL)
{
if (KeyValue.id < (*LocPtr)->Data.id)
*LocPtr = (*LocPtr)->LChild;
else
if (KeyValue.id > (*LocPtr)->Data.id)
*LocPtr = (*LocPtr)->RChild;
else stop = TRUE;
}
*Found=stop;
}
void BSTSearch2(BinTreePointer Root, BinTreeElementType KeyValue, boolean *Found,
BinTreePointer *LocPtr, BinTreePointer *Parent)
/* Δέχεται: Ένα ΔΔΑ με το δείκτη Root να δείχνει στη ρίζα του και μια τιμή KeyValue.
Λειτουργία: Αναζητά στο ΔΔΑ έναν κόμβο με τιμή KeyValue στο πεδίο κλειδί του
και τον πατέρα του κόμβου αυτού.
Επιστρέφει: Η Found έχει τιμή TRUE, ο δείκτης LocPtr δείχνει στον κόμβο που
περιέχει την τιμή KeyValue και ο Parent δείχνει στον πατέρα
αυτού του κόμβου, αν η αναζήτηση είναι επιτυχής.
Διαφορετικά η Found έχει τιμή FALSE.
*/
{
boolean stop;
BinTreePointer TempParent;
*LocPtr = Root;
TempParent=NULL;
stop = FALSE;
while (!stop && *LocPtr != NULL)
{
if (KeyValue.id < (*LocPtr)->Data.id) {
TempParent=*LocPtr;
*LocPtr = (*LocPtr)->LChild;
}
else
if (KeyValue.id > (*LocPtr)->Data.id) {
TempParent=*LocPtr;
*LocPtr = (*LocPtr)->RChild;
}
else stop = TRUE;
}
*Found=stop;
*Parent=TempParent;
}
void BSTDelete(BinTreePointer *Root, BinTreeElementType KeyValue)
/* Δέχεται: Ένα ΔΔΑ με το δείκτη Root να δείχνει στη ρίζα του και μια τιμή KeyValue.
Λειτουργία: Προσπαθεί να βρει έναν κόμβο στο ΔΔΑ που να περιέχει την τιμή
KeyValue στο πεδίο κλειδί του τμήματος δεδομένων του και,
αν τον βρει, τον διαγράφει από το ΔΔΑ.
Επιστρέφει: Το τροποποιημένο ΔΔΑ με τον δείκτη Root να δείχνει στη ρίζα του.
*/
{
BinTreePointer
R,
n, //δείχνει στον κόμβο που περιέχει την τιμή KeyValue *)
Parent, // πατέρας του n ή του nNext
nNext, // ενδοδιατεταγμένος επόμενος του n
SubTree; // δείκτης προς υποδέντρο του n
boolean Found; // TRUE AN TO ΣΤΟΙΧΕΙΟ KeyValue EINAI ΣΤΟΙΧΕΟ ΤΟΥ ΔΔΑ *)
R=*Root;
BSTSearch2(R, KeyValue, &Found , &n, &Parent);
if (!Found)
printf("TO STOIXEIO %d DEN EINAI STO DDA\n", KeyValue);
else {
if (n->LChild != NULL && n->RChild != NULL)
{ // κόμβος προς διαγραφή με δύο παιδιά
//Βρες τον ενδοδιατεταγμένο επόμενο και τον πατέρα του
nNext = n->RChild;
Parent = n;
while (nNext->LChild !=NULL) //* DIASXISH PROS TA ARISTERA *)
{
Parent = nNext;
nNext = nNext->LChild;
}
/* Αντιγραφή των περιεχομένων του nNext στον n και
αλλαγή του n ώστε να δείχνει στον επόμενο */
n->Data = nNext->Data;
n = nNext;
} //Συνεχίζουμε με την περίπτωση που ο κόμβος έχει το πολύ 1 παιδί
SubTree = n->LChild;
if (SubTree == NULL)
SubTree = n->RChild;
if (Parent == NULL) //* 8A DIAGRAFEI H RIZA *)
*Root = SubTree;
else if (Parent->LChild == n)
Parent->LChild = SubTree;
else
Parent->RChild = SubTree;
free(n);
}
}
void InorderTraversal(BinTreePointer Root)
/* Δέχεται: Ένα δυαδικό δέντρο με το δείκτη Root να δείχνει στην ρίζα του.
Λειτουργία: Εκτελεί ενδοδιατεταγμένη διάσχιση του δυαδικού δέντρου και
επεξεργάζεται κάθε κόμβο ακριβώς μια φορά.
Εμφανίζει: Το περιεχόμενο του κόμβου, και εξαρτάται από το είδος της επεξεργασίας
*/
{
if (Root!=NULL) {
InorderTraversal(Root->LChild);
printf("%d, %s\n",Root->Data.id,Root->Data.password);
InorderTraversal(Root->RChild);
}
}