Post date: Mar 16, 2016 11:42:50 AM
Assuming the following are available in the struct
struct node {
node* Left;
node* Right;
node* Parent;
bool checked;
} ;
initializing the checked to false, the following code iterates through the binary tree.
while (true)
{
if ((current == NULL)
break;
if ((current->Left != NULL) && (!current->Left->checked))
current = current->Left;
else if ((current->Right != NULL) && (!current->Right->checked))
current = current->Right;
else if (!current->checked)
{
current->checked = true;
count += 1;
}
else
current = current->Parent;
}
The problem with this algorithm is how are you going to clear the checked flags?
A suggestion is instead of using this algorithm, implement a std::queue that holds pointers to the nodes that need to be worked.
Then after they are worked, use the queue to reset the node.