先建立结点数据类型为正int类型的用二叉链表存储的二叉树,再求这棵二叉树的结点值和。
时间: 2024-02-06 17:12:02 浏览: 63
好的,我可以帮你解决这个问题。
首先,我们需要定义二叉树的结点数据类型,如下所示:
```c++
typedef struct Node {
int data;
struct Node* left_child;
struct Node* right_child;
} Node;
```
其中,`data` 表示结点的数据,`left_child` 和 `right_child` 分别指向左子树和右子树的根结点。
接下来,我们可以使用二叉链表来存储二叉树。我们定义一个指向根结点的指针 `root`,然后通过动态内存分配来创建结点。具体实现如下:
```c++
Node* create_node(int data) {
Node* node = (Node*)malloc(sizeof(Node));
node->data = data;
node->left_child = NULL;
node->right_child = NULL;
return node;
}
Node* create_tree() {
Node* root = create_node(1);
root->left_child = create_node(2);
root->right_child = create_node(3);
root->left_child->left_child = create_node(4);
root->left_child->right_child = create_node(5);
root->right_child->left_child = create_node(6);
root->right_child->right_child = create_node(7);
return root;
}
```
这里我们创建了一个如下所示的二叉树:
```
1
/ \
2 3
/ \ / \
4 5 6 7
```
最后,我们可以通过递归遍历整棵二叉树,将每个结点的值相加,即可求出二叉树的结点值和。具体实现如下:
```c++
int get_sum(Node* root) {
if (root == NULL) {
return 0;
}
int left_sum = get_sum(root->left_child);
int right_sum = get_sum(root->right_child);
return root->data + left_sum + right_sum;
}
```
这里的 `get_sum` 函数使用递归实现,如果当前结点为空,则返回 0;否则,递归计算左右子树的结点值和,并将当前结点的值加上左右子树的结点值和返回。
最终,我们可以调用 `get_sum` 函数来求出二叉树的结点值和,如下所示:
```c++
Node* root = create_tree();
int sum = get_sum(root);
printf("The sum of the binary tree is: %d\n", sum);
```
输出结果为:
```
The sum of the binary tree is: 28
```
这说明二叉树的结点值和为 28。
阅读全文