数据结构题目56：线索二叉树的更新

题目：线索二叉树的更新
所谓线索二叉树的更新是指在线索二叉树中插入一个结点或者删除一个结点。一般情况下，这些操作有可能破坏原来已有的线索关系，因此，在修改指针的时候，还需要对线索进行相应的修改。一般来说，这个过程花费的代价几乎与重新进行线索化相同。这里讨论比较简单的情况，即在中序线索二叉树中插入一个结点p，使它成为结点s的右孩子。

解题思路：分两种情况来分析：

1. 若s的右子树为空，则插入结点p。在这种情况中，s的直接后继结点将成为p的中序直接后继结点，s成为p的中序直接前驱结点，而p成为s的右孩子。在下面给出的算法中，前几行用来实现这3步修改，其它部分的指针和线索不发生变化。
   2.若s的右子树非空，插入结点p。s原来的右子树变成了p的右子树，s成为p的中序直接前驱结点，p成为s的右孩子，s原来的直接后继结点成为p的直接后继结点（s原来的后继结点的左线索本来指向s，插入p以后应该指向p）。下面给出的算法依次实现这4步的修改，二叉树中其他结点的直接前驱结点和直接后继结点不发生变化。

具体算法如下：
这里使用到查找直接后继结点insucc(p)

function insert_right(s, p) {
    let w
    p.rchild = s.rchild
    p.rbit = s.rbit
    p.lchild = s
    p.lbit = 0
    s.rchild = p
    s.rbit = 1
    if ( p.rbit ==1 ) {
        w = insucc(p)
        w.lchild = p
    }
}

测试：考虑使用二叉树的线索化构造.