Reputation: 236
I need to add an item to a binary tree given only the item to be added.
Here is the code I'm given:
void BinaryTree::add(Data * data) {
if (root == NULL) {
root = new BinaryTreeNode(data);
}
else {
root->add(data);
}
}
where root
is a private variable of a BinaryTree
defined as a BinaryTreeNode
.
I need to implement a method:
void BinaryTreeNode::add(Data * data);
where a BinaryTreeNode
is:
class BinaryTreeNode {
public:
Data * nodeData;
BinaryTreeNode * left;
BinaryTreeNode * right;
/**
* Constructor
*/
BinaryTreeNode(
Data * data,
BinaryTreeNode * left = NULL,
BinaryTreeNode *right = NULL
)
: nodeData(data), left(left), right(right)
{ }
// ...
I want to do this recursively, but I'm not positive how when you're only passed the data to be added.
My idea that doesn't work is:
void BinaryTreeNode::add(Data * newData) {
BinaryTreeNode * temp = this;
if (temp == NULL) {
temp->nodeData = newData;
} else {
if (newData->compareTo(nodeData) < 0) {
temp->left->add(newData);
} else {
temp->right->add(newData);
}
}
}
Upvotes: 0
Views: 520
Reputation: 864
Well a binary tree, atleast how I know how to implement involves something like the following with two objects, one containing the the treenode object, and the other acting as an interface for the whole tree.
class cBinaryTree {
public:
bool insert(int inData);
//Other operations
private:
cBinaryTreeNode* root;
bool leftInsertion;
cBinaryTreeNode* getRoot() { return root; }
As you are comparing the actually value of the input data and placing it accordingly, this qualifies as a binary search tree. Then the insertion function can be written as
bool cBinaryTree::insert(int inData) {
//handle case if its first node.
cBinaryTreeNode *Parent = getInsertionNodePosition(getRoot(), inData);
cBinaryTreeNode *newNode = createNewNode(inData);
if(leftInsertion) //insert into left. add return statement
Parent->setLeftChild() = newNode;
else //insert into right
}
The recursive lookup function will be something like
cBinaryTreeNode* getInsertionNodePosition(cBinaryTreeNode* node,int inData) {
//Check left subtree and proceed from there.
if(inData < node->getData()) {
if(node->getLeftChild() == NULL) {
leftInsertion = true;
return node;
}
else {
node = node->getLeftChild();
return getInsertionNodePosition(node, inData);
}
}
//Similarly Check right subtree.
Hope this helps.
Upvotes: 0
Reputation: 64308
You are setting temp to this and then comparing it to NULL. this should never be NULL. You need to check if the left and right are NULL.
Upvotes: 2