证明：树中结点u是结点v的祖先，当且仅当在先序序列中u在v之

[问答题]

证明：树中结点u是结点v的祖先，当且仅当在先序序列中u在v之前，且在后序序列中u在v之后。

推荐

赞花婆

证明：命题等价于遍历时u在v之前的充要条件是遍历序列为先序序列，u在v之后的充要条件是遍历序列为后序遍历。

由于u是v的祖先，故若以u为根结点，v必在u的左子树或右子树上。考虑三种遍历次序，先序遍历是根结点-左子树-右子树，中序遍历是左子树-根结点-右子树，后序遍历是左子树-右子树-根结点。

（1）充分性：

要保证u在v之前，必须保证根结点的访问先于子树，即采用先序遍历。相反，要保证u在v之后，必须保证根结点的访问迟于子树，即采用后序遍历。

（2）必要性：

若采用先序遍历，必然先访问根结点，后访问其子树，故u的访问必先于v。若采用后序序列，则根结点在最后被访问，因而u的访问必在v之后。

综上分析，原命题成立。

发表于 2018-03-25 10:05:40 回复(0)

提交观点

问题信息

树

上传者：赞花婆

难度：

1条回答 2收藏 2227浏览

扫一扫，把题目装进口袋