填空题
C++
题号 #397580
设一棵完全二叉树共有839个结点,则在该二叉树中有_______个叶子结点。
参考答案
暂无
答案解析
【答案】420
【解析】一般二叉树有一个性质:在任意一棵二叉树中,度为O的结点(即叶子结点)总是比度为2的结点多一个。 在根据完全二叉树的定义,在一棵完全二叉树中,最多有1个度为1的结点。 综合以上两点可以得到如下结论: 没一棵完全二叉树具有n个结点。如果n为偶数,则在该二叉树中有n/2个叶子结点以及n/2—1个度为2的结点。还有1个是度为1的结点;如果n为奇数,则在该二叉树中有[n/2]+1个叶子结点 以及[n/2]个度为2的结点。没有度为1的结点。 在本题中,完全二又树共有839个结点。839是奇数,因此,在该二叉树中有420个叶子结点以及419个度为2的结点。没有度为1的结点。
【解析】一般二叉树有一个性质:在任意一棵二叉树中,度为O的结点(即叶子结点)总是比度为2的结点多一个。 在根据完全二叉树的定义,在一棵完全二叉树中,最多有1个度为1的结点。 综合以上两点可以得到如下结论: 没一棵完全二叉树具有n个结点。如果n为偶数,则在该二叉树中有n/2个叶子结点以及n/2—1个度为2的结点。还有1个是度为1的结点;如果n为奇数,则在该二叉树中有[n/2]+1个叶子结点 以及[n/2]个度为2的结点。没有度为1的结点。 在本题中,完全二又树共有839个结点。839是奇数,因此,在该二叉树中有420个叶子结点以及419个度为2的结点。没有度为1的结点。