设计C++程序,实现将两棵二叉树合并为一棵新的二叉树.合并必须从两棵二叉树的根结点开始,合并函数为:binaryNode* mergeTree(binaryNode* t1, binaryNode* &t2),带注释。并请解释:为什么参数t2要采用引用&方式?
时间: 2024-02-15 10:05:22 浏览: 87
好的,以下是将两棵二叉树合并为一棵新的二叉树的 C++ 代码,注释已经添加在代码中:
```c++
#include <iostream>
using namespace std;
struct binaryNode {
int val;
binaryNode* left;
binaryNode* right;
binaryNode(int x) : val(x), left(NULL), right(NULL) {}
};
binaryNode* mergeTree(binaryNode* t1, binaryNode* &t2) {
if (t1 == NULL) return t2; // 如果t1为空,直接返回t2
if (t2 == NULL) return t1; // 如果t2为空,直接返回t1
t1->val += t2->val; // 将t2的值加到t1上
t1->left = mergeTree(t1->left, t2->left); // 递归合并t1和t2的左子树
t1->right = mergeTree(t1->right, t2->right); // 递归合并t1和t2的右子树
return t1; // 返回合并后的二叉树
}
int main() {
// 构建两棵二叉树t1和t2,省略
binaryNode* t3 = mergeTree(t1, t2); // 合并t1和t2为t3
return 0;
}
```
参数t2要采用引用&方式,是因为合并后t2的值将不再被使用,而使用传值方式会额外生成一个t2的副本,浪费空间。采用引用&方式,则可以直接修改t2的值,避免了额外的空间开销。另外,由于t2的值可能被修改,因此需要使用引用&方式。
阅读全文