c语言比较二叉树是否相同

在 C 语言中，比较两个二叉树是否相同的算法通常涉及深度优先搜索 (DFS) 或广度优先搜索 (BFS)，其中节点值和左右子树结构都需匹配。这里有一个简单的思路：

1. 定义一个递归函数，比如 `isSameTree`，它接受两个树的根节点作为输入。
2. 如果两个节点同时为空，则它们代表的树是相同的，返回 `true`。
3. 如果其中一个节点为空，而另一个不为空，则树不同，返回 `false`。
4. 比较当前节点的值是否相等，如果不等则返回 `false`。
5. 对于非空的节点，分别递归地检查其左子树和右子树是否相同。

以下是这个算法的一个伪代码实现：

bool isSameTree(TreeNode* p, TreeNode* q) {
    if (!p && !q) return true; // 都为空，相同
    if (!p || !q) return false; // 其中一个为空，不同
    if (p->val != q->val) return false; // 节点值不等，不同
    
    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right); // 递归比较子树
}

相关问题

c语言代码 二叉树是否相似

在C语言中，判断两个二叉树是否相似通常是指判断它们的结构是否完全相同，即每个节点的值和左右子树是否对应相等。你可以通过递归的方式来实现这个功能：

首先，对于两个二叉树的根节点，如果它们的值相等并且其左子树和右子树分别与对方的左子树和右子树匹配，那么这两个二叉树被认为是相似的；如果不匹配，则返回false。

下面是一个简单的示例函数，用于比较两个二叉树是否相等：

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

int isSameTree(TreeNode* p, TreeNode* q) {
    if (p == NULL && q == NULL)
        return 1; // 都为空，认为相等
    else if (p == NULL || q == NULL)
        return 0; // 其中一个为空，认为不相等
    else if (p->val != q->val)
        return 0; // 如果值不同，直接返回 false

    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

C语言复制二叉树

复制二叉树可以采用递归的方式，对每个节点进行复制，并递归复制其左右子树。以下是一个用 C 语言实现的例子：

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

// 定义二叉树结构体
typedef struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

// 复制二叉树
TreeNode* copyTree(TreeNode* root) {
    if (root == NULL) {
        return NULL;
    }
    TreeNode* new_root = (TreeNode*)malloc(sizeof(TreeNode));
    new_root->val = root->val;
    new_root->left = copyTree(root->left);
    new_root->right = copyTree(root->right);
    return new_root;
}

// 中序遍历二叉树
void inorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    inorderTraversal(root->left);
    printf("%d ", root->val);
    inorderTraversal(root->right);
}

int main() {
    // 创建二叉树
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    root->val = 1;
    root->left = (TreeNode*)malloc(sizeof(TreeNode));
    root->left->val = 2;
    root->right = (TreeNode*)malloc(sizeof(TreeNode));
    root->right->val = 3;
    root->left->left = NULL;
    root->left->right = NULL;
    root->right->left = (TreeNode*)malloc(sizeof(TreeNode));
    root->right->left->val = 4;
    root->right->right = NULL;
    root->right->left->left = NULL;
    root->right->left->right = NULL;

    // 复制二叉树
    TreeNode* new_root = copyTree(root);

    // 中序遍历原二叉树和复制后的二叉树
    printf("Original tree: ");
    inorderTraversal(root);
    printf("\n");
    printf("Copied tree: ");
    inorderTraversal(new_root);
    printf("\n");

    return 0;
}

输出结果为：

Original tree: 2 1 4 3 
Copied tree: 2 1 4 3 

可以看到，复制后的二叉树与原二叉树结构相同，并且输出的中序遍历结果也相同。