问答题
写出在中序线索二叉树中找指定结点在后序下的前驱结点的算法。【河海大学1998七(10分)】
【正确答案】正确答案:在后序序列中,若结点P有右子女,则右子女是其前驱,若无右子女而有左子女,则左子女是其前驱。若结点P左右子女均无,设其中序左线索指向某祖先结点f(p是厂右子树中按中序遍历的第一个结点),若f有左子女,则其左子女是结点P在后序下的前驱;若厂无左子女,则顺其前驱找双亲的双亲,一直继续到双亲有左子女(这时左子女是P的前驱)。还有一种情况,若P是中序遍历的第一个结点,结点P在中序和后序下均无前驱。
【答案解析】