递归方法来计算二叉树的双分支节点个数

1.递归方法来计算二叉树的双分支节点个数

首先，你需要定义二叉树的节点结构，然后编写递归函数

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

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

// 创建新节点的函数
struct TreeNode* createNode(int value) {
    struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    newNode->value = value;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 递归求解二叉树双分支节点个数的函数
int countDoubleBranchNodes(struct TreeNode* root) {
    if (root == NULL) {
        return 0;
    }

    // 判断当前节点是否为双分支节点
    int isDoubleBranch = (root->left != NULL && root->right != NULL);

    // 递归计算左右子树的双分支节点个数
    int leftCount = countDoubleBranchNodes(root->left);
    int rightCount = countDoubleBranchNodes(root->right);

    // 返回左右子树的双分支节点个数之和，加上当前节点的贡献
    return leftCount + rightCount + (isDoubleBranch ? 1 : 0);
}

// 主函数
int main() {
    // 构建一个二叉树
    //        1
    //       / \
    //      2   3
    //     / \
    //    4   5
    struct TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);

    // 计算双分支节点个数
    int result = countDoubleBranchNodes(root);
    printf("双分支节点个数: %d\n", result);

    // 释放动态分配的内存
    // 在实际应用中，确保释放分配的内存是很重要的
    // 此处为简化示例，没有包含详细的内存释放操作
    return 0;
}

2.C语言递归计算二叉树是否含有值为x的结点

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

// 定义二叉树节点结构
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// 创建新节点
struct Node* newNode(int data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 递归搜索二叉树中是否包含值为x的节点
int containsNode(struct Node* root, int x) {
    // 如果当前节点为空，返回0（未找到）
    if (root == NULL) {
        return 0;
    }

    // 如果当前节点的值等于x，返回1（找到了）
    if (root->data == x) {
        return 1;
    }

    // 递归搜索左子树和右子树
    int leftResult = containsNode(root->left, x);
    int rightResult = containsNode(root->right, x);

    // 返回左子树或右子树中是否找到了值为x的节点
    return leftResult || rightResult;
}

int main() {
    // 创建二叉树
    struct Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);

    // 搜索值为x的节点
    int x = 3;
    if (containsNode(root, x)) {
        printf("二叉树中包含值为 %d 的节点。\n", x);
    } else {
        printf("二叉树中不包含值为 %d 的节点。\n", x);
    }

    return 0;
}

3.计算二叉树的高度

计算二叉树的高度和宽度可以通过递归的方式来实现。高度表示从根节点到最远叶子节点的最长路径长度，而宽度表示二叉树每一层的节点数的最大值。

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

// 定义二叉树节点结构
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// 创建新节点
struct Node* newNode(int data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 计算二叉树的高度（最大深度）
int getHeight(struct Node* root) {
    if (root == NULL) {
        return 0;
    } else {
        int leftHeight = getHeight(root->left);
        int rightHeight = getHeight(root->right);

        // 返回左右子树中的最大高度并加上根节点
        return (leftHeight > rightHeight) ? (leftHeight + 1) : (rightHeight + 1);
    }
}

int main() {
    // 创建二叉树
    struct Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->left = newNode(6);
    root->right->right = newNode(7);

    // 计算二叉树的高度
    int height = getHeight(root);
    printf("二叉树的高度是: %d\n", height);

    return 0;
}

4.计算二叉树的宽度

要计算二叉树的宽度，可以通过层序遍历（广度优先搜索）的方式，记录每一层节点的数量，并找到最大的层的节点数。

这里提供一个计算二叉树宽度的函数：

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

// 定义二叉树节点结构
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// 创建新节点
struct Node* newNode(int data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 获取二叉树的高度
int getHeight(struct Node* root) {
    if (root == NULL) {
        return 0;
    } else {
        int leftHeight = getHeight(root->left);
        int rightHeight = getHeight(root->right);
        return (leftHeight > rightHeight) ? (leftHeight + 1) : (rightHeight + 1);
    }
}

// 辅助函数：递归地计算每一层的节点数
void getWidthRecursive(struct Node* root, int level, int* count) {
    if (root == NULL) {
        return;
    }

    if (level == 1) {
        (*count)++;
    } else if (level > 1) {
        getWidthRecursive(root->left, level - 1, count);
        getWidthRecursive(root->right, level - 1, count);
    }
}

// 计算二叉树的宽度
int getWidth(struct Node* root) {
    int maxWidth = 0;
    int height = getHeight(root);
    for (int i = 1; i <= height; i++) {
        int count = 0;
        getWidthRecursive(root, i, &count);
        if (count > maxWidth) {
            maxWidth = count;
        }
    }
    return maxWidth;
}

int main() {
    // 创建二叉树
    struct Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->left = newNode(6);
    root->right->right = newNode(7);

    // 计算二叉树的宽度
    int width = getWidth(root);
    printf("二叉树的宽度是: %d\n", width);

    return 0;
}

 这两个示例展示了如何使用递归方法计算二叉树的高度和宽度。函数 getHeight 用于计算二叉树的高度，而 getWidth 函数则使用辅助函数 getWidthRecursive 来计算每一层的节点数，从而得到二叉树的宽度。