完全正则二叉树内点

---

舟话15652699327问： 一棵二叉树共有47个结点,其中有23个度为2的结点,假设根节点在第1层,则该二叉树点深度为多少 - ？
临沂市贝乐回答： 按照二叉树的性质,该二叉树中度为0结点个数为23 + 1 = 24,因此该二叉树中度为0结点个数为47-23-24 = 0,这个就是所谓的正则二叉树,因此,有47个结点二叉树的最小深度就是47个结点完全二叉树的深度:6 最大深度就是(47 +1)/2 = 24

舟话15652699327问： 每个结点的度为0或者为2的二叉树称为正则二叉树,对于 n 个结点的正则二叉树来说,它的最大高度是多少? - ？
临沂市贝乐回答： 根据二叉树的性质n0 = n2 + 1以及完全二叉树中度为1的结点个数最多为1,可以推出如下结论 如果完全二叉树中结点个数n是偶数: 度为0的结点个数n0 = n / 2,度为1的结点个数n1 = 1,度为2结点个数为n / 2 - 1 如果完全二叉树中结点个数n是奇数: 度为0的结点个数n0 = (n + 1)/ 2,度为1的结点个数n1 = 1,度为2结点个数为(n - 1) / 2

舟话15652699327问： 一棵二叉树共有47个结点,其中有23个度为2的结点.假设根结点在第一层,则该二叉树的深度为多少? - ？
临沂市贝乐回答： 由于度为2的结点个数为23个,因此度为0的叶子个数为23 + 1 = 24 所以度为1的结点个数为47-23-24=0,也就是一棵正则二叉树 因此其最小高度为log2(47) + 1 = 6,最大高度为(47 + 1) / 2 = 24

舟话15652699327问： 设一棵完全二叉树共有700个结点,求该二叉树有几个叶子结点? - ？
临沂市贝乐回答： 350个 如果是满二叉树,深度为m,则会有2^m-1个节点. 先判断二叉树的深度,700介于2^9-1和2^10-1之间,所以这个完全二叉树的深度为10. 第九层以上的二叉树为满二叉树,共有2^9-1=511个节点. 第十层上的叶子节点的个数为700-511=189,这些叶子节点的双亲个数为189div2=95. 第九层的节点个数为2^(9-1)=256,第九层上的叶子节点的个数为256-95=161. 所以共有叶子节点个数189+161=350

舟话15652699327问： 一棵二叉树只知道度为0的节点 ,能求出总结点嘛? - ？
临沂市贝乐回答： 一般二叉树不能,因为不知道度为1结点个数,但是正则二叉树(或者叫正规二叉树,也就是只有度为0和度为2的结点),由于度为0的个数n0= n2 + 1,(n2为度为2结点个数),就可以推出结点总数了

舟话15652699327问： 高度为h的正则二叉树至少有_____结点 - 上学吧普法考试？
临沂市贝乐回答： 对于二叉树而言: 正则二叉树就是严格二叉树,也就是二叉树中只有度为0和度为2的结点 终端结点也就是叶子结点,用的词不一样

舟话15652699327问： 对于一棵具有n个结点的完全二叉树,若一个结点的编号为i(1≤i≤n),则它的双亲结点的编号为 - -------左孩子 - ？
临沂市贝乐回答： 具有n个结点的完全二叉树,根节点为1,那么它的左孩子为2,右孩子为3,依次类推;若该结点不是根结点则编号为i的结点的父结点为(i/2向下取整);若该2*i

舟话15652699327问： n个结点的正则二叉树中有几个叶子 - ？
临沂市贝乐回答： 设二叉树中度为0、1、2的结点个数分别为n0,n1,n2 由于正则二叉树中没有度为1 的结点,因此n1 = 0 因此n0 + n2 = n 按照二叉树的性质n0 = n2 + 1,代入得 2n0 - 1 = n 所以叶子结点个数n0 = (n + 1)/2

---