C语言实现二叉树合并：代码详解及示例

C语言实现二叉树合并：代码详解及示例

本文将使用C语言实现二叉树合并，并提供详细代码注释和示例，帮助您理解二叉树合并的原理和实现方式。

代码实现

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

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

struct TreeNode* mergeTrees(struct TreeNode* t1, struct 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() {
    struct TreeNode* t1 = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    t1->val = 1;
    t1->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    t1->left->val = 3;
    t1->left->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    t1->left->left->val = 5;
    t1->left->left->left = NULL;
    t1->left->left->right = NULL;
    t1->left->right = NULL;
    t1->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    t1->right->val = 2;
    t1->right->left = NULL;
    t1->right->right = NULL;

    struct TreeNode* t2 = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    t2->val = 2;
    t2->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    t2->left->val = 1;
    t2->left->left = NULL;
    t2->left->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    t2->left->right->val = 4;
    t2->left->right->left = NULL;
    t2->left->right->right = NULL;
    t2->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    t2->right->val = 3;
    t2->right->left = NULL;
    t2->right->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    t2->right->right->val = 7;
    t2->right->right->left = NULL;
    t2->right->right->right = NULL;

    struct TreeNode* t = mergeTrees(t1, t2);
    printf("%d\n", t->val);
    printf("%d\n", t->left->val);
    printf("%d\n", t->left->left->val);
    printf("%d\n", t->left->right->val);
    printf("%d\n", t->right->val);
    printf("%d\n", t->right->right->val);

    return 0;
}

代码详解

1. mergeTrees(struct TreeNode* t1, struct TreeNode* t2)函数：

   • 接受两个二叉树 t1 和 t2 作为参数，返回合并后的二叉树。
   • 首先判断 t1 或 t2 是否为空，如果其中一个为空，则直接返回另一个二叉树。
   • 否则，将 t1 和 t2 的根节点的值相加，并将 t1 的左右子树分别与 t2 的左右子树合并。
   • 最后返回 t1，即合并后的二叉树。

2. main 函数：

   • 创建两个示例二叉树 t1 和 t2。
   • 使用 mergeTrees 函数合并 t1 和 t2，并将结果存储在 t 中。
   • 打印 t 的节点值，以验证合并是否正确。

总结

本文介绍了使用 C语言 实现二叉树合并的代码，并提供了详细的代码注释和示例。二叉树合并是一种常用的操作，能够将两个二叉树组合成一个新的二叉树，在数据结构和算法领域具有广泛应用。