数据结构 – 树的度和结点数的关系
·
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 总结点
旨在为数千万中国开发者提供一个无缝且高效的云端环境，以支持学习、使用和贡献开源项目。
更多推荐
21
0- 0
已为社区贡献1条内容
所有评论(0)