为什么任意的二叉树中叶子节点都比度为2的节点多一个呢？

大虾们来帮帮忙啊。我正学C语言呢，9月考二级。我的QQ号是464698543，谢谢大家了！！

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

　　假设一个二叉树有 a个度为2的节点， b个度为1的节点， c个叶节点，则这个二叉树的边数是 2a + b 。
　　另一方面，由于共有a+b+c个节点，
　　所以
　　边数= a+b+c-1 。
　　所以
　　2a+b = a+b+c-1
　　所以
　　a = c-1
　　二叉树简介：在计算机科学中，二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。

vbtraz · 2018-4-30 02:32:46

假设一个二叉树有 a个度为2的节点， b个度为1的节点， c个叶节点，则这个二叉树的边数是 2a + b 。另一方面，由于共有a+b+c个节点，所以边数等于 a+b+c-1 （这个对所有的树都是这样的，有定理的）。所以 2a+b = a+b+c-1 所以 a = c-1 就是你要的结论

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

归纳法可证：

一个结点的二叉树满足命题若深度为k的二叉树满足命题,则深度为k+1的二叉树根结点的左右子树为深度为k的二叉树或空；
若均为深度为k的二叉树则根结点度为2,左右子树度为0的结点比度为2的结点多2个,整棵树度为0的结点比度为2的结点多1个；否则根结点度为1,左右子树度为0的结点比度为2的结点多1个,整棵树度为0的结点比度为2的结点多1个；均满足命题.

为什么任意的二叉树中叶子节点都比度为2的节点多一个呢？

3 个回复