Ronzii's Blog

Just your average geek's blog

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