首页 > 试题广场 >

对于后序线索二叉树进行遍历是否需要栈的支持?为什么?

[问答题]
对于后序线索二叉树进行遍历是否需要栈的支持?为什么?
(摘自牛客444334号)在后序线索二叉树中查找结点*p的后继:若结点*p为根,则无后继;若结点*p为其双亲的右孩子,则其后继为其双亲;若结点*p为其双亲的左孩子,且双亲无右子女,则其后继为其双亲;若结点*p为其双亲的左孩子,且双亲有右子女,则结点*p的后继是其双亲的右子树中按后序遍历的第一个结点。所以,求后序线索二叉树中结点的后继要知道其双亲的信息,要使用栈,所以说后序线索二叉树是不完善的。
编辑于 2020-04-16 10:02:41 回复(0)