473,403 Members | 2,354 Online

# Binary Search Tree Split() function

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* &gtr,
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;
}
Jul 22 '05 #1
0 4202

This thread has been closed and replies have been disabled. Please start a new discussion.

### Similar topics

 7 by: pembed2003 | last post by: Hi, I have a question about how to walk a binary tree. Suppose that I have this binary tree: 8 / \ 5 16 / \ / \ 3 7 9 22 / \ / \ / \ 4 by: Tarique Jawed | last post by: Alright I needed some help regarding a removal of a binary search tree. Yes its for a class, and yes I have tried working on it on my own, so no patronizing please. I have most of the code working,... 15 by: Foodbank | last post by: Hi all, I'm trying to do a binary search and collect some stats from a text file in order to compare the processing times of this program (binary searching) versus an old program using linked... 1 by: mathon | last post by: hi, now i facing a problem which i do not know how to solve it...:( My binary search tree structures stores a double number in every node, whereby a higher number is appended as right child... 4 by: BenCoo | last post by: Hello, In a Binary Search Tree I get the error : Object must be of type String if I run the form only with the "Dim bstLidnummer As New BinarySearchTree" it works fine. Thanks for any... 1 by: hn.ft.pris | last post by: I have the following code: Tree.h defines a simple binary search tree node structure ########## FILE Tree.h ################ #ifndef TREE_H #define TREE_H //using namespace std; template... 6 by: fdmfdmfdm | last post by: This might not be the best place to post this topic, but I assume most of the experts in C shall know this. This is an interview question. My answer is: hash table gives you O(1) searching but... 4 by: whitehatmiracle | last post by: Hello I have written a program for a binary tree. On compiling one has to first chose option 1 and then delete or search. Im having some trouble with the balancing function. It seems to be going... 2 by: Defected | last post by: Hi, How i can implement a main function with this Binary Search Tree. thanks for help. is this code corrected ? #include 0 by: Charles Arthur | last post by: How do i turn on java script on a villaon, callus and itel keypad mobile phone 0 by: BarryA | last post by: What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress... 1 by: nemocccc | last post by: hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions? 1 by: Sonnysonu | last post by: This is the data of csv file 1 2 3 1 2 3 1 2 3 1 2 3 2 3 2 3 3 the lengths should be different i have to store the data by column-wise with in the specific length. suppose the i have to... 0 by: Hystou | last post by: There are some requirements for setting up RAID: 1. The motherboard and BIOS support RAID configuration. 2. The motherboard has 2 or more available SATA protocol SSD/HDD slots (including MSATA, M.2... 0 by: marktang | last post by: ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However,... 0 by: Hystou | last post by: Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can... 0 by: jinu1996 | last post by: In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven... 0 by: agi2029 | last post by: Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing,...