二叉树C语言问题（数据结构）

问题描述：

 void InThread(TBTNode *p, TBTNode *&pre)
{
    if(p ! = NULL)
    {
        InThread(p -> lchild, pre);
        if(p -> lchild == NULL)
        {
            p -> lchild = pre;
            p -> ltag = 1;
        }
        if(pre != NULL && pre -> rchild == NULL)
        {
            pre -> rchild = p;
            pre -> rtag = 1;
        }
        pre = p;
        p = p -> rchild;
        InThread(p, pre);
    }
}

这是通过中序遍历对二叉树线索化的递归算法。这个程序会递归到二叉树最左下第一个结点，若此结点没有右孩子，那么执行p = p -> rchild;后左边的p指向什么，是NULL吗？若是，如何执行下一句InThread(p, pre); ?

答

p指向的是最左下结点的右儿子，不一定为空，没有右儿子，则为NULL，表示该子树遍历结束，回退到上一层，执行if（p->lchild==NULL）注意这是一个递归调用

二叉树C语言问题（数据结构）

相关推荐