首页 > 试题广场 >

试讨论,能否在一棵中序全线索二叉树上查找给定结点*p在后序序

[问答题]
试讨论,能否在一棵中序全线索二叉树上查找给定结点*p在后序序列中的后继。
推荐
如果p是根结点,则其后继为空。否则需查找p的双亲结点。从p结点开始中序线索遍历,如果某结点的左指针域等于p,说明该结点是p的双亲结点,且p是它的左孩子;如果某结点的右指针域等于p,说明该结点是p的双亲结点,且p是它的右孩子;如此即可确定访问次序。若是右孩子,其后继是双亲结点;若是左孩子,其后继是其兄弟最左下的子孙,如果兄弟不存在,其后继是其双亲结点。
发表于 2018-03-25 10:03:44 回复(0)