Question

在任意一颗二叉树中，度为0的叶子结点，总是比度为二的结点多一个。为什么?求解释，考计算机二级。

Answer 1

归纳法可证 一个结点的二叉树满足命题 若深度为k的二叉树满足命题,则深度为k+1的二叉树根结点的左右子树为深度为k的二叉树或空；若均为深度为k的二叉树则根结点度为2,左右子树度为0的结点比度为2的结点多2个,整棵树度为0的结点比度为2的结点多1个；否则根结点度为1,左右子树度为0的结点比度为2的结点多1个,整棵树度为0的结点比度为2的结点多1个；均满足命题.

追问

哦哦懂了

Answer 2

国内数据结构教材里的树结构中结点的度，和图论里有区别，指的是所拥有的子结点数。因此0度就指没有子结点的叶子结点。你的问题正如上面所言在严版教材P124页有完整证明。