I have a general tree where the root's children are stored in a linked list as follows:
class node
{
int identifier;
node *parent;
std::vector<node *> children;
I am trying to implement a function that will search the tree and either return a pointer to the node whose int identifier matches the key to search for or nullptr if no match is found. Here is how I think it should work:
- If the current node -> identifier == identifier, return the current node.
- Otherwise, if the node has no children, return nullptr.
- Loop through the list of children, and recursively call and return find(int identifier) on each child.
- If no match is found, return nullptr.
Here is the tree being used for the unit test:
1-\
|-2-\
| |-3
| |-4
|
|-5-\
| |-6-\
| | |-7
| |-8
| |-9
It appears to be executing correctly for find(1), find(2), and find(3), however, find(4) is finishing at node 3 instead of stopping at 3, going back to 2, and then trying the "4" branch.
Looking for help figuring out what I need to do to get it to go to the next branch instead of finishing when the branch has no more children. Thanks for looking everyone.
Code:
node* node::find(int identifier)
{
cout << "FIND: " << identifier << endl;
cout << "this->identifier: " << this->identifier << endl;
if (this->identifier == identifier) return this;
if (this->children.empty()) return nullptr;
for (node* child : this->children) return child->find(identifier);
return nullptr;
}
Aucun commentaire:
Enregistrer un commentaire