结构推理
请证明:一棵二叉树的所有终端结点(叶结点),在先根序列、对称序序列及后根序列中都按相同的相对位置出现。
【正确答案】此命题为真,采用归纳法证明如下。
对二叉树结点个数n做归纳;
当n=0,n=1时,结论显然成立;
假设当n=k时结论也成立;
当n=k+1时,可把二叉树分成左子树和右子树(均可为空);并且左、右子树结点个数均小于k。由归纳假设,左、右子树终端结点在3种序列中按相同相对位置出现;而原二叉树所有终端结点就是其左、右子树的终端结点;又由3种序列的定义,有左子树终端结点总比右子树终端结点先出现。于是可得二叉树所有终端结点在3种序列中,都按相同相对次序出现。
【答案解析】