Hi,

Anyone out there with binary search tree experience. Working on a

project due tomorrow and really stuck. We need a function that splits

a binary tree into a bigger one and smaller one(for a random binary

search tree. We've tried everything but are in the land of pointer

hell. If someone could help it would be a huge help. our code follows.

We've tried 2 diff methods the split() and splitter() functions

#include <iostream>

#include <stdlib.h>

#ifndef BINTREE_H

#define BINTREE_H

using namespace std;

class binTreeNode{

public:

int data; //stored value

int treeSize; //the size of the key at the current node

binTreeNode *leftchild; //pointer to left node

binTreeNode *rightchild; //pointer to right node

binTreeNode(int a, binTreeNode* L, binTreeNode* R,int treeSize){

data = a; //set the key value

leftchild = L; //set the children to ptrs passed

rightchild = R;

//treeSize=1; //set the size of this "tree" to be 1

this->treeSize = treeSize;

}

binTreeNode(int a){

data = a; //set the key value

leftchild = NULL; //set the children to NULL

rightchild = NULL;

treeSize = 1; //set the size of this "tree" to be 1

}

binTreeNode(){}

//binTreeNode & operator=(binTreeNode &node){

friend class binTree;

};

class binTree{

public:

binTree(int key); //constructor

//~binTree(void); //deconstructor

binTreeNode* copyNode(binTreeNode* n);

void print();

//void printNode(binTreeNode *node);

void printTree(binTreeNode *node);

int cRand(int treeSize); //generate a random number between 0 and

the height of the tree

void insert(int key); //public function that will call insert(int

key, binTreeNode* t)

void insert(int key, binTreeNode* &t); //insert a new node into the

tree

bool search(int key); //public version of the search function

binTreeNode* search(int key, binTreeNode *t); //return a pointer to

the node containing value of key

binTreeNode* searchMin(binTreeNode *t); //returns the smallest value

in a subtree

//binTreeNode* splitter(binTreeNode* &less, binTreeNode* >r,

binTreeNode *r, int key);

binTreeNode* splitter(int key, binTreeNode *t, binTreeNode* s,

binTreeNode* g);

binTreeNode insertRoot(int key, binTreeNode* &t);

void split(int key, binTreeNode* &t, binTreeNode *s, binTreeNode

*g); //function used by insertRoot() to split the tree

void deleteNode(int key); //remove public function

void deleteNode(int key, binTreeNode* &t);

int smallest();

private:

binTreeNode *root; //pointer to root node

//int m_height; //height of tree

};

#endif

AND NOW THE IMPLEMENTATION---------------------------------------------------

binTreeNode* binTree::splitter(int key, binTreeNode *t, binTreeNode*

s, binTreeNode* g){

//binTreeNode root;

if(t == NULL){

//less = gtr = NULL;

return NULL;

}

root = new binTreeNode(t->data, t->leftchild, t->rightchild,

t->treeSize);

if(t->data < key) {

//*less = copyNoderoot;

//binTreeNode* temp;

//temp = &(copyNode(root));

//s = temp;//&(copyNode(root));

s = copyNode(root);

return splitter(key, t->leftchild, s, g->leftchild);

//splitter(key, t->leftchild, s, g->leftchild);

//less = copyNode(root);

//return splitter(root->rightchild, gtr, r->rightchild, key);

}else if(t->data > key) {

g = copyNode(root);

return splitter(key, t->rightchild, s->rightchild, g);

//return splitter(less, root->leftchild, r->leftchild, key);

}else{

s = t->leftchild;

g = t->rightchild;

return root;

}

}

binTreeNode binTree::insertRoot(int key, binTreeNode* &t){

binTreeNode s;

binTreeNode g;

//s = NULL;

//g = NULL;

cout << "calling split" << endl;

//splitter(s, g, t, key);

splitter(key, t, &s, &g);

cout << "returning from split" << endl;

t = new binTreeNode();

t->data = key;

//t->rightchild = s;

//t->leftchild = g;

return *t;

}