C++

Forum

 
Creating a BTree(Binary tree)

anash21 (8)
In class we were asked to create a C++ BTree program that would allow a user to input the following data types and then store said data in a .txt file:
0. ID 8 bytes

1. First name 30 char

2. Last Name 30 char

3. Street Address one 30 char

4. Street Adress two 30 char

5. City 30 char

6. State 20 char

7. Zip 10 char

8. Country 30 char

Any help would be greatly appreciated (I'm not particularly asking for full code, pseudo code would also be great). I had a great deal of my work done, unfortunately, the computer I was working on crashed, corrupting my files. My professor wants this code by the end of today, so whatever help you could offer would be amazing.
writetonsharma (1461)
people here help on already written code. They help in specific problems. So, if you have some code, we can help in fixing that and making that work.
If you have anything, even not working, post it and we can try to make it work.
anash21 (8)
Unfortunately, I lost all my code, this is all I have managed to rebuild (as a short cut a friend suggested I try to make it more like a linked list): 
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
 
#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;

struct Data
{
    int leftChildBlockNo;  // 8 bytes
    int rightChildBlockNo; // 8 bytes
    int id[10]; // 8 bytes
    char firstName[30]; // 30 bytes
    char lastName[30]; // 30 bytes
    char streetOne[30]; // 30 bytes
    char streetTwo[30]; // 30 bytes
    char city[30]; // 30 bytes
    char state[20]; // 20 bytes
    char zip[10]; // 10 bytes
    char country[30]; // 30 bytes
    char filler[22]; // 22 bytes
};

struct FileData
{
    int rootBlockNo;
    int lastBlockNoWritten;
};

struct Data *GetProfile() {
    struct Data newProfile;
    char instr[256];

    cout << "Enter data: ";
    cin >> instr;

    if (strlen(instr) == 0) {// If profilestring is empty
        return 0;
    } else {
        // Split the string...
        newProfile.id = 3;
        strcpy(newProfile.firstName,"Jon");
    }

    return &newProfile;
}

int main(void) {
    struct Data rootNode;
    struct Data *newProfile;

    newProfile = GetProfile();

    while (newProfile != NULL) {

        newProfile = GetProfile();
    }
}


plus this:

1. Choose a block size of 256 from ->
1. 7 times 30 = 210
2. 8 for the ID
3. 8 for the two children using block numbers

2. So we need a function that will get a block of 256 bytes using block number

3. Use block 0 as the root.

4. All numbers will be store as text using hexadecimals. So must have a function to convert from text to int and int to text.

5. Now we can make a struct that can contain the data and not worry about 32 bit verses 64 bit.

6. So
struct Data
{
int64_t leftChildBlockNo; // 8 bytes
int64_t rightChildBlockNo; // 8 bytes
int64_t id[10]; // 8 bytes
char firstName[30]; // 30 bytes
char lastName[30]; // 30 bytes
char streetOne[30]; // 30 bytes
char streetTwo[30]; // 30 bytes
char city[30]; // 30 bytes
char state[20]; // 20 bytes
char zip[10]; // 10 bytes
char country[30]; // 30 bytes
char filler[22]; // 22 bytes
};

7. You need to keep tract of the last block no that you have written. For this reason it might be better to reserve block 0 to store

8.struct FileData
{
int64_t rootBlockNo;
int64_t lastBlockNoWritten;
}

9. You will need to update the 0 block everytime you add a block so that lastBlockNoWritten is updated.
anash21 (8)
Update
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
 
#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;

struct Data
{
    int leftChildBlockNo;  // 8 bytes
    int rightChildBlockNo; // 8 bytes
    int id[10]; // 8 bytes
    char firstName[30]; // 30 bytes
    char lastName[30]; // 30 bytes
    char streetOne[30]; // 30 bytes
    char streetTwo[30]; // 30 bytes
    char city[30]; // 30 bytes
    char state[20]; // 20 bytes
    char zip[10]; // 10 bytes
    char country[30]; // 30 bytes
    char filler[22]; // 22 bytes
};

struct FileData
{
    int rootBlockNo;
    int lastBlockNoWritten;
};

struct Data *GetProfile()
{
    struct Data newProfile;
    char instr[256];

    cout << "Enter data: ";
    cin >> instr;

    if (strlen(instr) == 0)
	{
		// If profilestring is empty
        return 0;
    } 
	else
	{
        // Split the string...
        newProfile.id = 3;
        strcpy(newProfile.firstName,"Jon");
    }

    return &newProfile;
}

void AppendProfile(struct Data *newProfile, struct Data *rootNode)
{
	struct Data *child;

	if(rootNode == nullptr)
	{
		rootNode = newProfile;
	}

	else
	{
		if(newProfile-> id<rootNode-> id)
		{
			child=rootNode->leftChildBlockNo;
		}
		else
		{
			child=rootNode->rightChildBlockNo;
		}
	}
}

int main(void)
{
    struct Data *rootNode;
    struct Data *newProfile;

	rootNode = nullptr;
	newProfile = nullptr;

    newProfile = GetProfile();

    while (newProfile != NULL)
	{
		AppendProfile(newProfile, rootNode);

        newProfile = GetProfile();
    }
}
anash21 (8)
This is what I have managed to rebuild:
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
 
#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;

struct Data
{
    int leftChildBlockNo;  // 8 bytes
    int rightChildBlockNo; // 8 bytes
    int id[10]; // 8 bytes
    char firstName[30]; // 30 bytes
    char lastName[30]; // 30 bytes
    char streetOne[30]; // 30 bytes
    char streetTwo[30]; // 30 bytes
    char city[30]; // 30 bytes
    char state[20]; // 20 bytes
    char zip[10]; // 10 bytes
    char country[30]; // 30 bytes
    char filler[22]; // 22 bytes
};

struct FileData
{
    int rootBlockNo;
    int lastBlockNoWritten;
};

struct Data *GetProfile() {
    struct Data newProfile;
    char instr[256];

    cout << "Enter data: ";
    cin >> instr;

    if (strlen(instr) == 0) {// If profilestring is empty
        return 0;
    } else {
        // Split the string...
        newProfile.id = 3;
        strcpy(newProfile.firstName,"Jon");
    }

    return &newProfile;
}

void AppendProfile(struct Data *newProfile, struct Data *rootNode) {
    struct Data *child;
    struct Data *parent;

    if(rootNode == nullptr) {
        rootNode = newProfile;
        return;
    } else {
        parent = rootNode;

        while (parent != nullptr) {
            if(newProfile->id == parent->id) {
                // This ID is already in the tree
                return;
            }

            if(newProfile->id < parent->id) {
                child = (struct Data *)parent->leftChildBlockNo;

                if(child == nullptr) {
                    parent->leftChildBlockNo = newProfile;
                    return;
                }
            } else {
                child = (struct Data *)parent->rightChildBlockNo;

                if(child == nullptr) {
                    parent->rightChildBlockNo = newProfile;
                    return;
                }
            }

            parent = child;
        }
    }
}

struct Data *FindProfile(int id, struct Data *rootNode) {
    struct Data *child;
    struct Data *parent;

    if(rootNode == nullptr) {
        return nullptr;
    } else {
        parent = rootNode;

        while (parent != nullptr) {
            if(id == parent->id) {
                return parent;
            }

            if(id < parent->id) {
                child = (struct Data *)parent->leftChildBlockNo;

                if(child == nullptr) {
                    return nullptr;
                }
            } else {
                child = (struct Data *)parent->rightChildBlockNo;

                if(child == nullptr) {
                    return nullptr;
                }
            }

            parent = child;
        }
    }

    return nullptr;
}

void DisplayProfile(struct Data *profile) {
    if (profile == nullptr) {
        cout << "This is a NULL record" << endl;
    } else {
        cout << "Name: " << profile->firstName << " " <<
profile->lastName << endl;
        //...
    }
}


int main() {
    struct Data *rootNode;
    struct Data *newProfile;
    int id = -1;

    rootNode = nullptr;
    newProfile = nullptr;

    newProfile = GetProfile();

    // Build the tree
    while (newProfile != NULL) {
        AppendProfile(newProfile, rootNode);

        newProfile = GetProfile();
    }

    // Search the tree
    while (id != 0) {
        cout << "Enter an ID number to search or zero (0) to end: ";
        cin >> id;

        if(id > 0) {
            newProfile = FindProfile(id, rootNode);

            DisplayProfile(newProfile);
        }
    }

}
Topic archived. No new replies allowed.