C语言实现二叉树合并算法

以下是用C语言实现二叉树合并的代码：

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

// 创建一个新的二叉树节点
TreeNode* createNode(int val) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 合并两个二叉树
TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
    if (t1 == NULL) {
        return t2;
    }
    if (t2 == NULL) {
        return t1;
    }
    t1->val += t2->val;
    t1->left = mergeTrees(t1->left, t2->left);
    t1->right = mergeTrees(t1->right, t2->right);
    return t1;
}

int main() {
    // 创建两个二叉树
    TreeNode* t1 = createNode(1);
    t1->left = createNode(3);
    t1->right = createNode(2);
    t1->left->left = createNode(5);
    TreeNode* t2 = createNode(2);
    t2->left = createNode(1);
    t2->right = createNode(3);
    t2->left->right = createNode(4);
    t2->right->right = createNode(7);
    
    // 合并两个二叉树
    TreeNode* mergedTree = mergeTrees(t1, t2);
    
    // 输出合并后的二叉树
    printf("The merged binary tree is:\n");
    printf("%d\n", mergedTree->val);
    printf("%d %d\n", mergedTree->left->val, mergedTree->right->val);
    printf("%d %d %d\n", mergedTree->left->left->val, mergedTree->left->right->val, mergedTree->right->right->val);
    return 0;
}

在这个代码中，我们首先定义了一个二叉树的结构体，包含节点的值以及左右子节点。然后我们创建了一个函数用于创建一个新的二叉树节点。接下来，我们定义了一个函数用于合并两个二叉树。在这个函数中，我们首先判断两个二叉树是否为空，如果其中一个为空，则返回另一个二叉树。否则，我们将两个二叉树的节点值相加，并递归合并它们的左右子树。最后，我们返回合并后的二叉树。在主函数中，我们创建了两个二叉树，并将它们合并到一个新的二叉树中。然后我们输出合并后的二叉树的节点值，以验证合并是否正确。

阅读代码，我们可以发现，这个合并函数的实现非常简洁且易于理解。它的时间复杂度为O(n)，其中n为二叉树节点的数量。在合并两个二叉树时，我们只需要递归遍历每个节点，并将它们的值相加，然后递归合并它们的左右子树即可。

需要注意的是，在合并两个二叉树时，我们需要判断每个节点是否为空，以避免出现空指针异常。另外，如果两个二叉树的节点数量不相同，则合并后的二叉树节点数量也会不同。

总的来说，二叉树合并是一道经典的算法问题，它涉及到二叉树的遍历、递归等基本操作，对于提高算法能力和编程能力都非常有帮助。