线索二叉树

线索二叉树(Threaded BinaryTree)

中序线索化

/*中序遍历的构建*/
void inCreate(TreeNode *root, TreeNode *&prev)
{
    if(root)
    {
        inCreate(root->left, prev);
        if(root->left == NULL)
        {
            root->left_flag = CLUE;
            root->left = prev;
        }
        if(prev && prev->right == NULL)
        {
            prev->right_flag = CLUE;
            prev->right = root;
        }
        prev = root;
        inCreate(root->right, prev);
    }
}

/*中序线索下的遍历*/
void inOrder(TreeNode *root)
{
    while(root)
    {
        while(root->left_flag != CLUE)
            root = root->left;
        cout << root->value << " ";
        while(root->right_flag != LINK)
        {
            root = root->right;
            cout << root->value << " ";
        }
        root = root->right;
    }
    cout << endl;
}