用于查找二叉树中叶节点数的数学函数

Question

存在未知深度的不平衡二叉树.具有两个子节点的节点的数量由表示T2.仅具有一个子T1节点的节点由叶节点表示,并且叶节点由表示L.如果考虑到T1 = m和T2 = n节点,那么你可以定义一个数学函数f(m, n),其给出的叶节点L个？

例如,在下面的树T2中m = 3,总T1节点数和总节点数是n = 2.叶节点的数量L = f(m,n) = 4.你能找到一个数学函数f(m,n),它给出了所有树的叶子节点数量吗？

Answer 1

这很简单.在完全二叉树(即每个非叶子有2 m个子节点)的内部节点中,确实存在m+1叶子节点.可以删除只有一个子节点的每个节点,并且您仍然拥有二叉树.因此,叶节点的数量L很简单m+1.或者回答这个问题:f(m, n) = m + 1.

通过"删除T1节点" 来举例说明我的意思可能是有用的.考虑你的例子.右边5只有一个孩子.如果我们去掉5,并把9下2直接,叶子的数量不会改变.

如果我们为9(4直接放在2)下面做同样的事情,我们有一个完整的二叉树,也就是说,所有非叶子都有2个孩子.

有关如何在T1 不更改叶节点数的情况下删除所有类型节点的图形说明,请参见图片.

剩下的就是证明在m内部节点的树中,每个非叶子正好有2个子节点,叶子节点的数量是m+1:

通过归纳证明.归纳假设:|L| = |T2|+1

基础:树由单个节点组成.显然,|L|=1并且|T2|=0,它持有.

步骤:考虑一棵树根不是叶子.根据假设,它有两个孩子,左和右.通过归纳假设:|Lleft|=|T2left| + 1和|Lright| = |T2right| + 1.对于总树,我们有|T2| = |T2left| + |T2right| + 1和|L| = |Lleft| + |Lright|.因此,|L| = |T2left| + 1 + |T2right| + 1 = |T2| + 1.

替代证明

该属性也可以直接证明,没有删除T1节点的handwaving参数.再次,通过归纳,与归纳假设|L| = |T2| + 1.

• 基数:树是单个节点,所以|L| = 1和|T2| = 0.
• 步骤1的情况下:树有根,只有1名儿童X,然后|L| = |LX|和|T2| = |T2X|,因此|L| = |T2| + 1被归纳假设.
• 第二种情况:树的根有两个孩子,左边和右边.通过归纳假设:|Lleft|=|T2left| + 1和|Lright| = |T2right| + 1.对于总树,我们有|T2| = |T2left| + |T2right| + 1和|L| = |Lleft| + |Lright|.因此,|L| = |T2left| + 1 + |T2right| + 1 = |T2| + 1.

因此,|L| = |T2| + 1换句话说f(m, n) = m + 1.