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语言，编写判断二叉树是否相似的递归算法

### 回答1：
好的，我来为你讲解如何用递归的方式来判断两棵二叉树是否相似。

首先，我们来确定一下“二叉树相似”的定义。在这里，我们定义两棵二叉树相似当且仅当它们的形状和节点的值相同。

具体来说，我们可以使用递归的方式来判断两棵二叉树是否相似。我们可以定义一个递归函数 `isSimilar(root1, root2)`，其中 `root1` 和 `root2` 分别表示两棵二叉树的根节点。

在递归函数中，我们需要先判断两棵二叉树的根节点是否为 `NULL`。如果都为 `NULL`，则返回 `true`，表示两棵二叉树相似。如果有一棵二叉树的根节点为 `NULL`，则返回 `false`，表示两棵二叉树不相似。

然后，我们比较两棵二叉树的根节点的值是否相等。如果不相等，则返回 `false`，表示两棵二叉树不相似。如果相等，则继续判断两棵二叉树的左子树和右子树是否相似。

为了判断两棵二叉树的左子树和右子树是否相似，我们可以递归调用 `isSimilar()` 函数，并将两棵二叉树的左子树和右子树的根节点作为参数传入

### 回答2：
二叉树相似是指两棵二叉树的结构相同，但节点的值可以不同。为了判断两棵二叉树是否相似，我们可以采用递归算法来遍历比较它们的节点。

首先，我们先定义一个二叉树的结构，每个节点包括一个整数值和左右孩子节点的指针。

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

接下来，我们可以编写一个递归函数来比较两棵二叉树是否相似。

int isSimilarTrees(TreeNode* root1, TreeNode* root2) {
    // 如果两个根节点都为空，则相似
    if (root1 == NULL && root2 == NULL) {
        return 1;
    }

    // 如果一个根节点为空，另一个根节点不为空，则不相似
    if (root1 == NULL || root2 == NULL) {
        return 0;
    }

    // 如果两个根节点的值不相等，则不相似
    if (root1->val != root2->val) {
        return 0;
    }

    // 递归判断左子树和右子树是否相似
    return isSimilarTrees(root1->left, root2->left) && isSimilarTrees(root1->right, root2->right);
}

在这个递归函数中，我们首先判断两个根节点是否都为空，如果是，则返回相似；如果一个根节点为空，另一个根节点不为空，或者两个根节点的值不相等，均返回不相似的结果。如果都不满足，则递归判断两个二叉树的左子树和右子树是否相似。

以上就是通过C语言编写判断两个二叉树是否相似的递归算法的答案，希望能够帮助到你！

### 回答3：
判断两个二叉树是否相似的递归算法可以分为以下几个步骤：
1. 首先，判断两个根节点是否为空，若均为空，则两个二叉树相似；若其中一个为空，另一个不为空，则两个二叉树不相似。
2. 若两个根节点均不为空，则比较两个根节点的值是否相等，若不相等，则两个二叉树不相似。
3. 若两个根节点的值相等，递归地判断它们的左子树和右子树是否相似，判断的方法是将两个左子树和右子树作为参数进行递归调用。
4. 如果所有的左子树和右子树都相似，则最后返回true；否则返回false。

以下是用C语言编写的判断二叉树是否相似的递归算法：

#include <stdio.h>
#include <stdbool.h>

// 定义二叉树的结点
typedef struct TreeNode {
    int value;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

// 判断两个二叉树是否相似
bool isSimilar(TreeNode* root1, TreeNode* root2) {
    // 若两个根节点均为空，则相似
    if (root1 == NULL && root2 == NULL) {
        return true;
    }
    // 若其中一个根节点为空，另一个不为空，则不相似
    if (root1 == NULL || root2 == NULL) {
        return false;
    }
    // 若两个根节点的值不相等，则不相似
    if (root1->value != root2->value) {
        return false;
    }
    // 递归判断两个左子树和右子树是否相似
    bool leftSimilar = isSimilar(root1->left, root2->left);
    bool rightSimilar = isSimilar(root1->right, root2->right);
    // 若所有的左子树和右子树都相似，则返回true；否则返回false
    return leftSimilar && rightSimilar;
}

int main() {
    // 创建两个二叉树
    TreeNode node1 = {1, NULL, NULL};
    TreeNode node2 = {2, NULL, NULL};
    TreeNode node3 = {3, &node1, &node2};

    TreeNode node4 = {1, NULL, NULL};
    TreeNode node5 = {2, NULL, NULL};
    TreeNode node6 = {3, &node4, &node5};

    // 判断两个二叉树是否相似
    bool similar = isSimilar(&node3, &node6);
    
    // 输出结果
    if (similar) {
        printf("两个二叉树相似\n");
    } else {
        printf("两个二叉树不相似\n");
    }
    
    return 0;
}

以上是一个简单的判断二叉树相似的递归算法的C代码，根据实际需要可以进行适当的修改和扩展。

给定二叉树T（树深度不超过H<=10，深度从1开始，节点个数N<1024，节点编号1~N）的层序和中序遍历，输出T从左向右叶子节点以及树先序和后序遍历序列,用C语言写出完整代码

好的，我来给你提供一份C语言的完整代码，实现上述功能。代码如下：

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

#define MAXN 1024

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

int n;
int levelOrder[MAXN];
int inorder[MAXN];

TreeNode* buildTree(int levelStart, int levelEnd, int inStart, int inEnd) {
    if (levelStart > levelEnd) return NULL;
    TreeNode *root = (TreeNode*)malloc(sizeof(TreeNode));
    root->val = levelOrder[levelStart];
    int idx;
    for (idx = inStart; idx <= inEnd; ++idx) {
        if (inorder[idx] == root->val) break;
    }
    int leftLen = idx - inStart;
    root->left = buildTree(levelStart + 1, levelStart + leftLen, inStart, idx - 1);
    root->right = buildTree(levelStart + leftLen + 1, levelEnd, idx + 1, inEnd);
    return root;
}

void getLeaves(TreeNode *root, int *leaves, int *cnt) {
    if (!root) return;
    if (!root->left && !root->right) {
        leaves[(*cnt)++] = root->val;
    }
    getLeaves(root->left, leaves, cnt);
    getLeaves(root->right, leaves, cnt);
}

void preorder(TreeNode *root, int *pre, int *cnt) {
    if (!root) return;
    pre[(*cnt)++] = root->val;
    preorder(root->left, pre, cnt);
    preorder(root->right, pre, cnt);
}

void postorder(TreeNode *root, int *post, int *cnt) {
    if (!root) return;
    postorder(root->left, post, cnt);
    postorder(root->right, post, cnt);
    post[(*cnt)++] = root->val;
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) scanf("%d", &levelOrder[i]);
    for (int i = 0; i < n; ++i) scanf("%d", &inorder[i]);
    TreeNode *root = buildTree(0, n - 1, 0, n - 1);
    int leaves[MAXN], cnt = 0;
    getLeaves(root, leaves, &cnt);
    int pre[MAXN], preCnt = 0;
    preorder(root, pre, &preCnt);
    int post[MAXN], postCnt = 0;
    postorder(root, post, &postCnt);
    printf("Leaves: ");
    for (int i = 0; i < cnt; ++i) {
        printf("%d ", leaves[i]);
    }
    printf("\n");
    printf("Preorder: ");
    for (int i = 0; i < preCnt; ++i) {
        printf("%d ", pre[i]);
    }
    printf("\n");
    printf("Postorder: ");
    for (int i = 0; i < postCnt; ++i) {
        printf("%d ", post[i]);
    }
    printf("\n");
    return 0;
}

具体实现方法与Python版本相似，主要分为三个部分：

1. 构建二叉树，采用递归方法实现。
2. 找出二叉树T从左向右的叶子节点，同样采用递归方法实现。
3. 分别输出二叉树T的先序遍历和后序遍历序列，同样采用递归方法实现。

需要注意的是，C语言中的数组需要预先指定大小，因此代码中定义了一个最大节点个数MAXN，来限制数组的大小。同时，为了避免数组越界，需要在函数参数中指定数组的实际大小，而不能直接使用数组。

最后，通过读入层序遍历和中序遍历，构建二叉树，找出叶子节点以及输出先序遍历和后序遍历序列。完整的输出结果与Python版本相同。