一棵二叉树共有47个结点,其中有23个度为2的结点.假设根结点在第一层,则该二叉树的深度为多少?

问题描述:

一棵二叉树共有47个结点,其中有23个度为2的结点.假设根结点在第一层,则该二叉树的深度为多少?

计算方式是这样的:假设二叉树中度为0的结点数为n0,度为1的结点数为n1,度为2的结点数为n2,那么显然有:1.n0 + n1 + n2 = 47 (三种度数的节点之和为二叉树结点的总数)2.n1 + 2 × n2 + 1 = 47 (边的总和加1为二叉...不好意思 由于没有基础 还要接着问你(这个题的答案为6)为什么 n2为23,n0为24,n1为0这颗二叉树的最低层次(为完全二叉树时)就为6层?首先因为没有出现度为1的接点所以其可以是完全二叉树,且作为完全二叉树时肯定是最低层次的一种排布方法,即将非叶子节点按照顺序依次排布。这样的完全二叉树,47个结点只能排六层,因为按照完全二叉树的结点数公式,第n层满二叉树的结点总数T为T = 2^n - 1 因此 2^5 - 1