}//结束 ThrTreeInsert
2．答案：[题目分析]在后序序列中，若结点p有右子女，则右子女是其前驱，若无右子女而有左子女，则左子女是其前驱。若结点p左右子女均无，设其中序左线索指向某祖先结点f（p是f右子树中按中序遍历的第一个结点），若f有左子女，则其左子女是结点p在后序下的前驱；若f无左子女，则顺其前驱找双亲的双亲，一直继续到双亲有左子女（这时左子女是p的前驱）。还有一种情况，若p是中序遍历的第一个结点，结点p在中序和后序下均无前驱。
BiThrTree InPostPre (BiThrTree t,p)
//在中序线索二叉树t中，求指定结点p在后序下的前驱结点q {BiThrTree q;
if (p->rtag==0) q=p->rchild; //若p有右子女，则右子女是其后序前驱 else if (p->ltag==0) q=p->lchild; //若p无右子女而有左子女，左子女是其后序前驱。
else if(p->lchild==null) q=null;//p是中序序列第一结点，无后序前驱 else //顺左线索向上找p的祖先，若存在，再找祖先的左子女 {while(p->ltag==1 && p->lchild!=null) p=p->lchild;
if(p->ltag==0) q=p->lchild; //p结点的祖先的左子女是其后序前驱 else q=null; //仅右单枝树（p是叶子），已上到根结点，p结点无后序前驱
}
return(q); }//结束InPostPre
百度搜索“70edu”或“70教育网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，70教育网，提供经典综合文库山东大学网络教育《数据结构》( C 卷)(2)在线全文阅读。
相关推荐：
