/* 
  <数据结构>

  Page: 137  exercise:3

  description:
   编写一个函数insert_left,在线索二叉树中,插入一个新节点child,作为节点parent的左儿子.节点parent的左儿子指针变为节点child的左儿子指针
*/

void insert_right(tree_node *parent,tree_node *child)
{
    tree_node *temp;

    child->left = parent->left;
    child->right = parent;
    parent->left = child;
    child->left_thread = parent->left_thread;
    child->right_thread = true;
    parent->left_thread = false;

    if ( ! child->left_thread)
    {
        temp = insucc(child);
        temp->right = child;
    }
} 

tree_node *insucc(tree_node *tree)   //返回tree下的最右节点
{
    tree_node *temp;
    temp = tree_>left;
    
    if (! tree->left_thread)
        while ( !temp->right_thread)
            temp = temp->right;
    return temp;
}

评论