线索二叉树的程序实现

Question

把缺少的代码补充完整
二叉树的括号表示法为: A(B(,C(D,E)),F(,G))
A的前驱为E
A的后继为F
中序序列:B D C E A F G
程序功能：使用括号表示法建立二叉树的二叉链表，中序线索化二叉树并找出结点的前驱和后继。

private void Thread(ThNode p)            //对以p为根结点的二叉树进行中序线索化
    {
        if (p!=null)
        {
            Thread(p.lchild);                //左子树线索化
            if (p.lchild==null)                //前驱线索
            {    p.lchild=_____1_____;        //给结点p添加前驱线索
                p.ltag=_____2_____;
            }
            else p.ltag=0;
            if (pre.rchild==null)
            {    pre.rchild=_____3_____;    //给结点pre添加后继线索
                pre.rtag=_____4_____;
            }
            else pre.rtag=0;
            pre=p;
            Thread(p.rchild);                //右子树线索化
        }
    }
    /* 在中序线索二叉树中查找p的中序前驱, 并用pre指针返回结果 */
     ThNode InPre(ThNode p)
    {  
        ThNode q;
        if(p.ltag==1)
            pre = _____5_____;  /*填空5：直接利用线索找前驱*/
        else 
        { /* 填空6-7：在p的左子树中查找"最右下端"结点 */
            for(q= p.lchild; q.rtag == _____6_____; q = _____7_____);
            pre=q;
        }
        return pre;
    }

    /*在中序线索二叉树中查找p的中序后继结点，并用next指针返回结果*/
    ThNode InNext(ThNode p)
    { 
        ThNode Next;
        ThNode q;
        if (p.rtag==1)  
            Next = _____8_____;  /*填空8：直接利用线索*/
        else
        { /*填空9-10： 在p的右子树中查找"最左下端"结点*/
            for(q=p.rchild; q.ltag== _____9_____; q = _____10_____);
            Next=q; 
        } 
        return Next;
    }

Answer 1

填充完的代码如下，望采纳

private void Thread(ThNode p) //对以p为根结点的二叉树进行中序线索化
{
    if (p!=null)
    {
        Thread(p.lchild);
        //左子树线索化
        if (p.lchild==null) //前驱线索
        {
            p.lchild=pre;
            //给结点p添加前驱线索
            p.ltag=1;
        } else p.ltag=0;
        if (pre.rchild==null)
        {
            pre.rchild=p;
            //给结点pre添加后继线索
            pre.rtag=1;
        } else pre.rtag=0;
        pre=p;
        Thread(p.rchild);
        //右子树线索化
    }
}
/* 在中序线索二叉树中查找p的中序前驱, 并用pre指针返回结果 */
ThNode InPre(ThNode p)
{
    ThNode q;
    if(p.ltag==1)
    pre = p.lchild;
    //直接利用线索找前驱 else
    {
        //在p的左子树中查找"最右下端"结点
        for (q= p.lchild; q.rtag == 1; q = q.rchild);
        pre=q;
    }
    return pre;
}
/*在中序线索二叉树中查找p的中序后继结点，并用next指针返回结果*/
ThNode InNext(ThNode p)
{
    ThNode Next;
    ThNode q;
    if (p.rtag==1)
    Next = p.rchild;
    //直接利用线索 else
    {
        //在p的右子树中查找"最左下端"结点
        for (q=p.rchild; q.ltag==1; q = q.lchild);
        Next=q;
    }
    return Next;
}