下列线索二叉树中(用虚线表示线索),符合后序线索树定义的是( )。
方法一:定义
若结点&nbs...
用户登录可进行刷题及查看答案
若结点 x 为根结点,则无后继;
若结点 x 为其父结点的右孩子结点,则其后继为其父结点;
若结点 x 为其父结点的左孩子结点,且父结点无右孩子结点,则其后继为其父结点;
若结点 x 为其父结点的左孩子结点,且双亲有右孩子结点,则其后继为其父结点的右子树中按后序遍历的第一个结点。
本题选D。
方法二:后序遍历
后序遍历序列与后序线索树有对应关系。
图中二叉树后序遍历序列为d, b, c, a,后序线索树中c的前驱为b,后继为a,只有D选项符合要求。
需要注意的是,结点c在后序线索树中的指向结点a的后继指针不能用二叉树原有的指针,因为这里采用的是孩子表示法,原有指针是从a指向c的。
登录后提交答案
暂无评论,来抢沙发