For starters, I would like to apologize because I didn't know how to word the title appropriately. Here is the issue that I have. I'm having an issue while creating a tree from a file. The file looks like this:
0 1 3 4
0 1 4
0 2 3 3 4
0 2 3 4
And the tree that I need to create should look like this:
0
/ \
1 2
/ \ |
3 4 3
| / \
4 3 4
|
4
Using words to explain, in each row of the file I am given a new stack of data, and I should create a tree but if the sequence exists, I should follow it until there is a break in it.
While creating the tree, I used this method to check if there are sequences that already exist:
void Tree::addNewStack(const string& line) {
istringstream stack(line);
string token;
Node* currentNode = nullptr;
while (stack >> token) {
Node* newNode = new Node(token);
if (root == nullptr) {
root = newNode;
}
else {
// Checking for existing node.
Node* existingNode = nullptr;
currentNode = root;
while (existingNode == nullptr && currentNode != nullptr) {
if (currentNode->left != nullptr && current->left->data == token) {
existingNode = currentNode->left;
}
else if (currentNode->right != nullptr && current->right->data == token) {
existingNode = currentNode->right;
}
// ****
}
// If there is an existingNode move to it, otherwise make a new node.
if (existingNode != nullptr) {
currentNode = existingNode;
currentNode = newNode;
}
else {
currentNode = newNode;
}
}
}
}
I tried making a priority queue and then making a tree using a preorder traversal, but that seemed more complicated.
Inside the while loop where the comment with stars is, I can't figure out how to search through the whole loop. I need to find a way to update the currentNode so that I traverse through the whole tree. I tried with currentNode = currentNode->left, but that only checks one side of the tree. Also tried making 2 while loops, one to check the left and one to check the right side but that also didn't work. Any suggestions?
There is only 1 root in your tree.
The token corresponding to the root is indeed repeated several times in the file (once for each line) but judging from the parameter being named const string& line, the method will only have to treat it once for each call. It is not mentioned in your question but I have to assume in my answer that another method builds the line strings out of the file in a loop and pass them to Tree::addNewStack one by one.
Since currentNode needs to be initialized only once within each call, you should process the root before the while loop instead of inside it (it should make sense we do the initialization before entering the loop).
The rest should flow easily for a binary tree (not a binary search tree) as per your question; we will fill left before right at every level:
stack >> token;
if (!root)
root = new Node(token);
else if (root->data != token)
throw "The root specified in file does not match the root of the tree";
Node* currentNode = root;
while (stack >> token) {
if (!currentNode->left)
currentNode = currentNode->left = new Node(token);
else if (currentNode->left->data == token)
currentNode = currentNode->left;
else if (!currentNode->right)
currentNode = currentNode->right = new Node(token);
else if (currentNode->right->data == token)
currentNode = currentNode->right;
else
throw "Path is incompatible with tree";
}
If you want to generate a binary search tree, you need to add 1 layer of logic to treat:
if (token <= currentNode->data) -> Check only the left branch.else -> Check only the right branch.Again, the tree in your question is not a BST as the 2 nodes under 1 are bigger than 1 so your file should raise an exception on token 4 of the 2nd line of the file (for node 1, currentNode->right is alreay occupied by 3).