为什么在一棵度为 3 的树中,度为 2 的结点个数是 1,度为 0 的结点个数是 6,则度为 3 的结点个数是 4
时间: 2023-05-23 18:02:11 浏览: 487
根据树的性质可知,在一棵树中度数之和等于2(n-1),其中n为节点数。那么,度为2的节点所贡献的度数为2,度为0的节点所贡献的度数为0,所以可以列出方程: 2×1 + 0×6 + 3×x = 2(n-1)。解得:x = 4,因此度为 3 的结点个数是 4。
相关问题
在一棵度为3的树中,度为2的结点个数是1,度为0的结点个数是6,则度为3的结点个数是
2。
解释如下:
在一棵树中,所有结点的度数之和等于2×边数。对于度为 k 的结点个数为 n_k,则有:
n_0 + n_1 + n_2 + ··· + n_k = 总结点数
0×n_0 + 1×n_1 + 2×n_2 + ··· + k×n_k = 2×边数
其中总结点数和边数可由度数信息计算得出,具体可以参考树的基本概念。代入题目中的数据,可以得到:
n_0 = 6, n_1 = 0, n_2 = 1, k = 3
总结点数 = n_0 + n_1 + n_2 + n_3 = 6 + 0 + 1 + n_3
边数 = (0×n_0) + (1×n_1) + (2×n_2) + (3×n_3) = 2×(n_0 + n_1 + n_2 + n_3)
代入后得到:
n_3 = 2
因此,度为3的结点个数是2。
编写用层次顺序遍历二叉树的方法,统计树中度为1 的结点个数。
以下是用 Python 语言编写的代码:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def levelOrder(root: TreeNode) -> List[List[int]]:
if not root:
return []
queue = [root]
res = []
while queue:
level = []
level_size = len(queue)
for i in range(level_size):
node = queue.pop(0)
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
res.append(level)
return res
def countDegreeOne(root: TreeNode) -> int:
if not root:
return 0
count = 0
queue = [root]
while queue:
node = queue.pop(0)
if node.left and not node.right:
count += 1
queue.append(node.left)
elif node.right and not node.left:
count += 1
queue.append(node.right)
elif node.left and node.right:
queue.append(node.left)
queue.append(node.right)
return count
```
其中 `levelOrder` 方法是层次顺序遍历二叉树的实现,返回一个二维数组,表示每一层的结点值。`countDegreeOne` 方法统计树中度为1的结点个数,使用 BFS 遍历整个二叉树,遇到度为1的结点则计数并将其子结点加入队列中。
相关推荐
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)