《数据结构》课程教学资源（参考资料）线索二叉树提高

提高：中序线索树中插入结点。 假设新结点*q是插入到指定结点*p和*p的右子树 之间的结点，插入后，*q作为*的右子树的根结点。 R L 空 R

提高：中序线索树中插入结点。 假设新结点*q是插入到指定结点*p和*p的右子树 之间的结点，插入后，*q作为*p的右子树的根结点。 P L R P L R Q p p q 空

插入*q后，和的左子树为 空，所以，*q是*p右子树中最左 下的结点。也就是说，*q是作为 和的中序后继插入的。 !注意：若*不是中序序列的 L 最后一个结点，则插入前其必 空 有一个中序后继结点*s,插入( R L 后，g将变成*s的前驱结点。 所以，在中序线索树中插入结点*a时，除需修改*a的两个 指针域和*和的右指针域外，还（可能）要修改*s的左线索域

P L R Q p q 空 插入*q后，*q的左子树为 空，所以，*q是*p右子树中最左 下的结点。也就是说，*q是作为 *p的中序后继插入的。 ！注意：若*p不是中序序列的 最后一个结点，则插入*q前其必 有一个中序后继结点*s，插入*q 后，*q将变成*s的前驱结点。 所以，在中序线索树中插入结点*q时，除需修改*q的两个 指针域和*p的右指针域外，还(可能)要修改*s的左线索域

第法片断8s=:InOrderNext(p): q->ltag=1(线索)；q->lchild=-p; q->rtag=p->rtag; q->rchild=p->rchild; R p->rtag=0(指针)；p->rchild-=q; ifs&&(s->ltag)s不空且莫左链是线察 s->Ichild=q; ☑

算法片断：s=InOrderNext(p); q->ltag=1(线索); q->lchild=p; q->rtag=p->rtag; q->rchild=p->rchild; p->rtag=0(指针); p->rchild=q; if(s&&(s->ltag)) //s不空且其左链是线索 s->lchild=q;