So I have been working this for a few days now, approaching deadline really soon, within 24 hours, and the only thing that's not working is the remove function, I can't seem to figure out how to arrange it, or how to make it to work for the code. Any help would be great, and explanations of how to do it are welcome.
I know my code is super messy, and I should have done several things different ways, but I think it's little too late to go back now.
This is part of the code where the problem is the
bool BST::remove(const char* key) and
void BST::deleteNodeItem(Item *items) section, I honestly don't know how to call to certain elements.
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
|
#include "BST.h"
#include <iostream>
#include <iomanip>
using namespace std;
BST::BST(int capacity) :
items(new Item[capacity]),
size(0),
maxSize(capacity)
{
items->empty = true;
}
BST::~BST()
{
delete [] items;
}
void BST::insert(const Data& data)
{
int tempIndex = 0;
while (!items[tempIndex].empty)
{
if (data < items[tempIndex].instanceData.getName())
{
tempIndex = (2*tempIndex)+1;
}
else // indicates we want this to be the right child.
{
tempIndex = (2*tempIndex)+2;
}
}
if ( tempIndex >= maxSize )
{
this->reallocate();
}
items[tempIndex].instanceData = data;
items[tempIndex].empty = false;
size++;
}
void BST::reallocate()
{
Item *swap = new Item[2*maxSize+1];
for ( int index = 0; index < maxSize+1; index++ )
{
if ( ! items[index].empty )
{
swap[index].instanceData = items[index].instanceData;
swap[index].empty = false;
}
}
maxSize += maxSize;
delete [] items;
items = NULL;
items = swap;
}
bool BST::retrieve(const char *key, Data const *& data) const
{
for(int index=0; index < maxSize/2; index++)
{
if (!items[index].empty)
{
if ( items[index].instanceData == key )
{
data = &items[index].instanceData;
return true;
}
}
}
return false;
}
bool BST::remove(const char* key)
{
int tempIndex = 0;
while (!items[tempIndex].empty)
{
if (key == NULL)
{
cout << "Not Deleted" << endl;
}
else if (key == items[tempIndex].instanceData.getName())
{
// if item in root, delete
deleteNodeItem(items);
}
else if(key < items[tempIndex].instanceData.getName())
{
// search left subtree
items[2*tempIndex+1].instanceData = key;
remove(key);
}
else
{
// search right subtree
items[2*tempIndex+2].instanceData = key;
remove(key);
}
}
return true;
}
void BST::deleteNodeItem(Item *items)
{
item *delitems;
int tempindex = 0;
data replacementdata;
// test for a leaf
if ( (items[2*tempindex+1].instancedata == null) && (items[2*tempindex+2].instancedata == null) )
{
delete items;
items = null;
} // end if leaf
// test for no left child
else if (items[tempindex].empty == null)
{
delitems = items;
items = items[2*tempindex+2].instancedata;
delitems->items[2*tempindex+2].instancedata = null;
delete delitems;
} // end if no left child
// test for no right child
else if (items[2*tempindex+2].instancedata == null)
{
delitems = items;
items = items[2*tempindex+1].instancedata;
delitems->items[2*tempindex+1].instancedata = null;
delete delitems;
} // end if no right child
// there are two children:
// retrieve and delete the inorder successor
else
{
processleftmost(items[2*tempindex+2].instancedata, replacementdata);
items->data = replacementdata;
} // end if two children
}
|
And this is the header file for it:
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
|
// do not change this file except within the private section of the BST class
#pragma once
#include "data.h"
class BST
{
public:
BST(int capacity = 5);
~BST();
void insert(const Data& data);
bool remove(const char *key);
bool retrieve(const char *key, Data const *& data) const;
int getSize(void) const;
void displayArrayOrder(ostream& out) const;
void displayPreOrder(ostream& out) const;
void displayInOrder(ostream& out) const;
void displayPostOrder(ostream& out) const;
private:
int size;
int maxSize;
struct Item
{
bool empty;
Data instanceData;
bool isLeaf;
};
void BST::reallocate();
void BST::deleteNodeItem(Item *items);
// pointer to the array
Item *items;
};
|
I will really appreciate the help, been reading the book about it, but without seeing actual implementation of the examples, it's really hard for me to understand it. Sorry if I posted this in the wrong section, this is my first post here, but plan on coming back.
