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

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   5struct 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 来计算每一层的节点数，从而得到二叉树的宽度。