1.设计一个求不带头结点的单链表L的所有data域(假设为int型)之和的递归算法。 分析二叉树的二叉链表存储结构的递归性,设计求二叉链表bt中所有结点值之和的递归算法,假设二叉链的data域为int型。用DevC++编写代码
时间: 2024-09-27 16:05:02 浏览: 42
树与二叉树
首先,我们来设计一个求单链表所有节点数据之和的递归算法。这个过程可以分为两个步骤:如果链表为空,则返回0;否则,返回当前节点的数据加上其下一个节点的和。
对于单链表的递归求和:
```cpp
struct ListNode {
int data;
ListNode* next;
};
int sumOfList(ListNode* head) {
// 空链表的情况
if (head == nullptr) {
return 0;
}
// 非空链表的情况,递归调用并累加当前节点值
else {
return head->data + sumOfList(head->next);
}
}
```
接下来是二叉链表(二叉搜索树的后序遍历实际上就是一个递归的过程)所有节点值之和的递归算法。在这个场景下,我们需要访问左子树、右子树以及根节点本身:
```cpp
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
};
int sumOfBinaryTree(TreeNode* root) {
// 空树的情况
if (root == nullptr) {
return 0;
}
// 递归地计算左子树、右子树的和,并加上根节点的值
else {
return sumOfBinaryTree(root->left) + sumOfBinaryTree(root->right) + root->val;
}
}
```
注意:DevC++是一种古老的C/C++集成开发环境,在现代开发环境中可能不再广泛使用。上面的代码片段可以直接复制到支持C++的IDE如Visual Studio Code、Code::Blocks等中编译运行。
阅读全文