J
j
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;
}
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;
}