求助：哪个计算机高手能帮我解释一下为什么说在任意一棵二叉树中，度为0的结点总比度为2的结点多一个？

热心网友 · 2018-4-30 02:32:47

明白满二叉树度为0的结点总比度为2的结点多一个吧满二叉树是二叉树的特殊情况非满二叉树只是满二叉树少了一些分支每当减少两个度为0的结点就会减少一个度为2的结点于此同时又有一个度为0的结点产生所以度为0的结点的减少和度为2的结点减少的一样多既然满二叉树度为0的结点总比度为2的结点多一个那减少了相同度为0和2的结点后二叉树度为0的结点还是比度为2的结点多一个明白了吧

佳期如梦540 · 2018-4-30 02:32:48

想象一个最简单的情况，一棵满二叉树只有两层，也就是三个节点（一个根节点，两个叶节点），此时度为0的节点即两个，度为2的节点只有一个，所以多一个，再扩展，有三层，一共有7个节点，三个度为2的节点，四个度为0的节点，就可以发现规律，可以用数学归纳法证明的。普通的树也可以自己举几个简单例子画一下就明白了。

热心网友 · 2018-4-30 02:32:49

度为0的节点是叶节点，度为2的节点是内部节点。
一高度为h(从0开始)的二叉树共含有2^(h+1)-1个节点，其中叶节点有2^h个，内部节点就有[2^(h+1)-1]-[2^h]=2^h-1个。
那么很显然，叶节点总比内部节点多1个。

热心网友 · 2018-4-30 02:32:50

在二叉树中，度数为0的节点就是外部节点，度数为2的节点就是内部节点。根据二叉树的性质：N个内部节点的二叉树，它的外部节点为N+1个。该性质可以用数学归纳证明：（1）对于空树，内部节点为0，外部节点为1，成立。（2）对于内部节点为k，外部节点为k+1的二叉树，每当将一个外部节点改为内部节点，并接上2个外部节点时，外部节点和内部节点同时增加1。此时该树的内部节点为k+1，外部节点为k+2，同样成立。通过数学归纳得证。

求助：哪个计算机高手能帮我解释一下为什么说在任意一棵二叉树中，度为0的结点总比度为2的结点多一个？

4 个回复

浏览过的版块