设一棵完全2叉树共有699个结点，则该2叉树中叶子结点的个数是多少

显示全部楼层 · 2010-8-13 14:46:49

因为二叉树中除了根节点外，其余每一个节点都有唯一的一个分支引出该节点，所以二叉树中的分支数比总的节点数少一个！因此这棵有699个节点的完全二叉树有698个分支，698为偶数。所以这棵完全二叉树中度为1的节点数为0！进而得到有698/2=349个度为2的节点。又因为在任意一棵二叉树中，度为0的节点（即叶子节点）总是比度为2的节点多一个。所以叶子节点的个数为350个！如有疑惑的地方可以在线交谈！

千问 · 2010-8-13 14:46:49

性质3对于一棵非空的二叉树，如果叶子结点数为n0，度数为2的结点数为n2，则有
n0＝n2＋1。完全二叉树由度数为2的结点和度数为0的结点（也就是叶子结点构成）当然最后可能余一个（自己想）。所以设叶子结点为n，则有n+n-1=699 所以n=355.如果除不尽当然取整数部分（想想）。呵呵一楼的啥意思？？怎么看不懂，我感觉

千问 · 2010-8-13 14:46:49

答案是350699是奇数所以该树的一度节点数为零，所以2*N2+1=699N2=349N0=350

千问 · 2010-8-13 14:46:49

高度为h的二叉树至多有2的h次方-1个结点，所以该树中叶子结点为：699+1-512（2^9）=188个