Ronzii's Blog

Just your average geek's blog

Iterative Traversal in a BST

void iterativeInorder(TreeNode* root)
{
    stack<TreeNode*> nodeStack;
    TreeNode* current = root;
    while (1)
    {
        while (current != NULL)
        {
            nodeStack.push(current);
            current = current->left;
        }
        if (nodeStack.size() == 0)
            return;
        current = nodeStack.top();
        nodeStack.pop();
        cout << current->value << " ";
        current = current->right;
    }
}
void iterativePreorder(TreeNode* root)
{
    stack<TreeNode*> nodeStack;
    TreeNode* current;
    nodeStack.push(root);
    while(!nodeStack.empty())
    {
        current = nodeStack.top();
        nodeStack.pop();
        if(current->right)
            nodeStack.push(current->right);
        if(current->left)
            nodeStack.push(current->left);
        cout<<current->value<<" ";
    }
}
void iterativePostorder(TreeNode* root)
{
    stack<TreeNode*> nodeStack;
    TreeNode* current = root;
    while(true)
    {
        while(current)
        {
            if(current->right)
            {
                nodeStack.push(current->right);
            }
            nodeStack.push(current);
            current = current->left;
        }
        if(nodeStack.empty())
        {
            return;
        }
        current = nodeStack.top();
        nodeStack.pop();
        if(current->right && !nodeStack.empty() && current->right==nodeStack.top())
        {
            nodeStack.pop();
            nodeStack.push(current);
            current = current->right;
        }
        else
        {
            cout<<current->value<<" ";
            current = NULL;
        }
    }
}
Advertisements

March 16, 2012 Posted by | C++ | , , | Leave a comment

Morris Traversal

void MorrisTraversal(TreeNode *root)
{
    TreeNode* current = root;
    while(current!=NULL)
    {
        if(current->left==NULL)
        {
            cout<<current->value<<" ";
            current = current->right;
        }
        else
        {
            TreeNode* pre = current->left;
            while(pre->right!=NULL && pre->right!=current)
            {
                pre = pre->right;
            }
            if(pre->right==NULL)
            {
                pre->right = current;
                current = current->left;
            }
            else
            {
                pre->right =NULL;
                cout<<current->value<<" ";
                current = current->right;
            }
        }
    }
}

March 1, 2012 Posted by | C++ | , , , , | Leave a comment