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);
    }
  }

}