473,403 Members | 2,354 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,403 software developers and data experts.

Binary Search Tree Split() function

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* &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<iostream>
0
by: Charles Arthur | last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
0
BarryA
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
marktang
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
jinu1996
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
agi2029
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,...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.