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