Help with (2,3,4)/2-4 trees
Hi everyone, I'm in need of some guidance again. I'm trying to create 2-4 tree, or what is sometimes called a (2,3,4) tree, I believe. Despite my utter lack of correct terminology, my implementation doesn't seem to be working that great either. Can someone please help me look over my code and find the problem. When I run my program through the debugger, the debugger actually finds a problem in my print function. That makes sense since my test driver doesn't print anything. The test driver just adds 3 employees and tries to print it out, but it can't.
Oh, some more clarification:
My header file has 3 classes, Employee, TreeNode, and Tree24. The employee class is a class which has employee information, ID, name, and salary. My TreeNode class has 3 slots and 4 pointers, like a 2-4 tree's node should contain. My Tree24 class has all my functions and also a pointer to a root.
I hope that's the only problem I have with my implementation but I'm fairly certain it's not. Are my traversals and insertions correct? I realize I haven't created code for all the splitting yet. But, since I'm only inserting 3 nodes, it shouldn't even split anything yet, but I don't think even THAT works. Or does it? Please help! :) My code is posted below. Thank you sooo much in advance for anyone who spots any problems. I cant thank you enough!
Code:
#include <iostream>
#include <iomanip>
#include <new>
#include <string>
#include "tree24.h"
using namespace std;
//Default constructor
Employee::Employee()
{
name = "John Doe";
ID = 00000000;
salary = 0;
}
// Constructor for the Employee class sets name, ID and salary
// to the users input
Employee::Employee(string temp, int number, double pay)
{
name = temp;
ID = number;
salary = pay;
}
//Prints a given employee's information onto the screen
void Employee::print() const
{
cout << "|" << name
<< setw( 31 - name.length()) << ID
<< setw(10) << salary << "|" << endl;
}
TreeNode::TreeNode() {
less = NULL;
betweenAB = NULL;
betweenBC = NULL;
greater = NULL;
counter = 0;
}
/*
bool TreeNode::isFilled() {
if (counter != 3)
return false;
else
return true;
}
*/
Tree24::Tree24() {
root = NULL;
}
TreeNode* Tree24::splitNode(TreeNode *point) {
TreeNode *newNode;
TreeNode *newNode2;
TreeNode *newNodeParent;
// Full node is the root
if (point == root) {
/*
split the node at the half, B's children are now A and C.
*/
// Create a parent node that has B.
newNodeParent = new TreeNode();
newNodeParent->A = point->B;
// Create a new less node
newNode = new TreeNode();
// new Node is A.
newNode->A = point->A;
// A's children are pointed to
newNode->less = point->less;
newNode->betweenAB = point->betweenAB;
// replace A with B.
point->A = point->B;
// Point new A's (B's) children to new node.
newNodeParent->less = newNode;
// Create a new betweenAB node
newNode2 = new TreeNode();
// new Node is C
newNode->A = point->C;
// C's children are now pointed to
newNode->betweenBC = point->betweenBC;
newNode->greater = point->greater;
// Point new A's children to new node
newNodeParent->betweenAB = newNode2;
// delete old Node
delete &point;
// point to new root
TreeNode *p = newNodeParent;
root = newNodeParent;
// return pointer
return p;
}
}
TreeNode* Tree24::traverse(TreeNode *ptr, int t) {
// Find the external node and split up any full nodes
while (ptr != NULL) {
// is p full?
if (ptr->counter == 3)
// yes, so split the node
ptr = splitNode(ptr);
if (ptr->counter == 2) {
if (t < ptr->A.ID) {
if (ptr->less != NULL)
ptr = ptr->less;
else
return ptr;
}
if (t > ptr->A.ID and t < ptr->B.ID) {
if (ptr->betweenAB != NULL)
ptr = ptr->betweenAB;
else
return ptr;
}
if (t > ptr->B.ID) {
if (ptr->betweenBC != NULL)
ptr = ptr->betweenBC;
else
return ptr;
}
}
if (ptr->counter == 1) {
if (t < ptr->A.ID) {
if (ptr->less != NULL)
ptr = ptr->less;
else
return ptr;
}
if (t > ptr->A.ID) {
if (ptr->betweenAB != NULL)
ptr = ptr->betweenAB;
else
return ptr;
}
}
}
return ptr;
}
void Tree24::insert(Employee v) {
// Initialize
TreeNode *p = root;
// if root is empty, create a node
if (p == NULL) {
p = new TreeNode();
p->A = v;
p->counter++;
}
else if (p != NULL) {
// TREE TRAVERSAL
p = traverse(p, v.ID);
if (p->counter == 0) {
p->A = v;
p->counter++;
}
if (p->counter == 1) {
if (v.ID < p->A.ID) {
p->B = v;
swap(p->A,p->B);
}
else
p->B = v;
p->counter++;
}
if (p->counter == 2) {
if (v.ID <= p->A.ID) {
p->C = v;
swap(p->A, p->C);
if (p->B.ID > p->C.ID)
swap(p->B, p->C);
}
if (v.ID > p->A.ID and v.ID < p->B.ID) {
p->C = v;
swap(p->B, p->C);
}
if (v.ID >= p->B.ID)
p->C = v;
p->counter++;
}
}
/*
// is p full?
if (p->isFilled())
// yes, so split the node
SplitNode(p);
else if (a == 1) {
// * There is 1 slot with two children.
// if inserted employee is less than p's ID, insert on the left pointer
if (p->ID > v.ID)
p = less;
// else insert on p's right pointer
else
p = betweenAB;
}
else if (a == 2) {
// * There are 2 slots with 3 children
}
// ADD closing brackets to while loop if you use this
*/
}
void Tree24::swap(Employee x, Employee y) {
Employee temp;
temp = x;
x = y;
y = temp;
}
// Recursive
void Tree24::print(TreeNode *&ptr) {
cout << endl;
if (ptr != NULL) {
if (ptr->counter == 1) {
cout << ptr->A.ID << "\n ";
print(ptr->less);
print(ptr->betweenAB);
}
else if (ptr->counter == 2) {
cout << ptr->A.ID << endl;
cout << ptr->B.ID << "\n ";
print(ptr->less);
print(ptr->betweenAB);
print(ptr->betweenBC);
}
else if (ptr->counter == 3) {
cout << ptr->A.ID << endl;
cout << ptr->B.ID << endl;
cout << ptr->C.ID << "\n ";
print(ptr->less);
print(ptr->betweenAB);
print(ptr->betweenBC);
print(ptr->greater);
}
}
}
