数据结构–树的度和结点数的关系
1： ⼆叉树叶⼦节点与度为⼆的节点有什么关系？
叶⼦结点就是没有孩⼦的结点，其度为0，度为⼆的结点是指有两个⼦数的结点。⽐如⼀棵完全⼆叉树有三层，叶⼦结点就是最下⾯那⼀层的结点数，没有孩⼦结点，就是4，度为⼆的结点有3个。
⼀、概念
与图论中的“度”不同，树的度是如下定义的：有根树T中，结点x的⼦⼥数⽬称为x的度。也就是：在树中，结点有⼏个分叉，度就是⼏。 ⼀个有⽤的⼩公式：树中结点数 = 总分叉数 +1。(这⾥的分叉数就是所有结点的度之和)二叉树公式
⼆、度的计算
1.设树T的度为4，其中度为1，2，3，4的节点个数分别为4，2，1，1，则T中的叶⼦数为？
解：
叶⼦的度数为0；那么设叶⼦数为x，则此树的总分叉数为1*4+2*2+3*1+4*1=15；此树的节点个数为16（
此处涉及到⼀个公式；节点 数=分叉数+1，由图形便可以观察出来）。⼜根据题⽬可以知道顶点数⽬还可以列出⼀个式⼦：4+2+1+1+x便可以得到等 式：
4+2+1+1+x=16；x=8为叶⼦数。
因为此题是数据结构中的问题：⼀般情况下都是有向树，所以叶⼦节点的度数为0，要区分于离散数学中的⽆向树叶⼦节点度为⼀。在数据结构中⼀般常⽤的 公式为：⼆叉树：度为0的节点数=度为2的节点数+1（n0=n2+1）此公式可由上述计算思想推导（⼀般在⼆叉树那⾥的公式多⼀些，树中只要你明确定 义，画出图来，便可以根据图形寻出规律来）
==================
⼀棵⽆向树T有3个2度结点，2个3度结点，2个4度结点，其余为叶。则T共有多少个结点，多少⽚叶？
解答：⼀共是21个结点，叶⼦结点为14个，简单的⽅法是你随意照着条件画⼀个就⾏，要算也简单，叶⼦结点=3*2+2*3+2*4-3-2-
2+1=14，也就是等于总度数-节点数+1
按理不是说先设树总结点数为N，然后3x2+2x3+2x4+(N-2-3-4)x1=(N-1)x2 这样解出来的N为13 总结点

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。