数据结构考研分类复习真题 第六章 答案 (五)[47]

数据结构考研分类复习真题 第六章 答案 (五)[47]  

　　 ．BiThrTree InSucc(BiThrTree T p)  //在对称序穿线树T中 查找给定结点p的中序后继　　{if（p >rtag== ）q=p >rchild;   //若p的右标志为 用其右指针指向后继　　else {q=p >rchild; while(q >ltag== ) q=q >lchild; }//p的后继为其右子树中最左下的结点　　return (q);　　}//结束InSucc

　　 ．[题目分析]在后序序列中 若结点p有右子女 则右子女是其前驱 若无右子女而有左子女 则左子女是其前驱 若结点p左右子女均无 设其中序左线索指向某祖先结点f（p是f右子树中按中序遍历的第一个结点） 若f有左子女 则其左子女是结点p在后序下的前驱 若f无左子女 则顺其前驱找双亲的双亲 一直继续到双亲有左子女（这时左子女是p的前驱） 还有一种情况 若p是中序遍历的第一个结点 结点p在中序和后序下均无前驱

　　BiThrTree InPostPre (BiThrTree t p)　　//在中序线索二叉树t中 求指定结点p在后序下的前驱结点q　　{BiThrTree q;　　if (p >rtag== ) q=p >rchild;       //若p有右子女 则右子女是其后序前驱　　else if (p >ltag== ) q=p >lchild;  //若p无右子女而有左子女 左子女是其后序前驱 　　else  if(p >lchild==null) q=null;//p是中序序列第一结点 无后序前驱　　else //顺左线索向上找p的祖先 若存在 再找祖先的左子女　　{while(p >ltag== && p >lchild!=null) p=p >lchild;　　if(p >ltag== ) q=p >lchild;  //p结点的祖先的左子女是其后序前驱　　else  q=null;    //仅右单枝树（p是叶子） 已上到根结点 p结点无后序前驱　　}　　return(q); }//结束InPostPre