6-1 二叉树统计指定取值元素节点的个数
时间: 2024-06-12 20:11:05 浏览: 57
在二叉树中统计指定取值元素节点的个数,可以使用递归的方法进行实现。具体实现方法如下:
```
int NodeCount(BiTree T, ElemType x) {
if (T == NULL) {
return 0;
}
int count = 0;
if (T->data == x) {
count++;
相关问题
6-1 二叉树的遍历 (50 分)
好的,我知道了。这是一道关于二叉树遍历的问题。二叉树的遍历有三种方式:前序遍历、中序遍历和后序遍历。其中,前序遍历的顺序是先访问根节点,再访问左子树,最后访问右子树;中序遍历的顺序是先访问左子树,再访问根节点,最后访问右子树;后序遍历的顺序是先访问左子树,再访问右子树,最后访问根节点。
下面是一个二叉树的例子:
```
1
/ \
2 3
/ \ / \
4 5 6 7
```
对于这个二叉树,它的前序遍历结果为:1 2 4 5 3 6 7;中序遍历结果为:4 2 5 1 6 3 7;后序遍历结果为:4 5 2 6 7 3 1。
你可以使用递归或者迭代的方式实现二叉树的遍历。下面是一个使用递归实现前序遍历的示例代码:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return []
res = [root.val]
res += self.preorderTraversal(root.left)
res += self.preorderTraversal(root.right)
return res
```
R6-1 二叉树 - 10. 求结点数
要求二叉树的结点数,可以使用递归的方式,分别求出左子树和右子树的结点数,然后将它们加起来再加上根节点的数量即可。
具体实现如下:
```c
int count_nodes(TreeNode* root) {
if (root == NULL) { // 如果根节点为空,返回 0
return 0;
}
int left_count = count_nodes(root->left); // 左子树结点数
int right_count = count_nodes(root->right); // 右子树结点数
return left_count + right_count + 1; // 返回左子树结点数、右子树结点数和根节点的数量之和
}
```
其中,`count_nodes` 函数接受一个指向根节点的指针 `root`,返回整个二叉树的结点数。
如果 `root` 为空,说明该二叉树为空,直接返回 0。
否则,递归求出左子树和右子树的结点数,分别保存在变量 `left_count` 和 `right_count` 中。
最后,返回左子树结点数、右子树结点数和根节点的数量之和,即为整个二叉树的结点数。
可以通过如下代码进行测试:
```c
int main() {
// 构造一棵二叉树
TreeNode* root = create_tree();
// 求结点数
int count = count_nodes(root);
// 输出结果
printf("The number of nodes is: %d\n", count);
// 释放内存
destroy_tree(root);
return 0;
}
```