【c++】计算树的深度和节点数

您所在的位置：网站首页 › 独立节点数怎么求 › 【c++】计算树的深度和节点数

【c++】计算树的深度和节点数

2024-07-11 08:07| 来源: 网络整理| 查看: 265

在C语言中，计算给定树的层数（深度）和节点总数通常需要使用递归方法。首先，我们需要定义树的节点结构。这里假设我们处理的是一棵二叉树，每个节点有两个子节点（左子节点和右子节点）。

下面是一个简单的二叉树节点的结构定义以及计算树的层数（深度）和节点总数的函数实现：

#include #include // 定义二叉树节点结构体 typedef struct TreeNode { int value; // 节点存储的值，根据实际情况可以改变类型 struct TreeNode *left; // 指向左子节点的指针 struct TreeNode *right; // 指向右子节点的指针 } TreeNode; // 函数声明 int maxDepth(TreeNode* root); int countNodes(TreeNode* root); // 计算树的最大深度（层数） int maxDepth(TreeNode* root) { if (root == NULL) { return 0; // 空树的深度为0 } int leftDepth = maxDepth(root->left); // 计算左子树的深度 int rightDepth = maxDepth(root->right); // 计算右子树的深度 return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1; // 当前树的深度为较大的子树深度加1 } // 计算树的节点总数 int countNodes(TreeNode* root) { if (root == NULL) { return 0; // 空树没有节点 } return countNodes(root->left) + countNodes(root->right) + 1; // 总数等于左子树节点数加右子树节点数再加1（当前节点） } // 创建新节点 TreeNode* createNode(int value) { TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode)); if (!newNode) { return NULL; } newNode->value = value; newNode->left = NULL; newNode->right = NULL; return newNode; } // 函数声明 void freeTree(TreeNode* root); // 释放树的内存 void freeTree(TreeNode* root) { if (root == NULL) { return; // 空指针不需要处理 } freeTree(root->left); // 递归释放左子树 freeTree(root->right); // 递归释放右子树 free(root); // 释放当前节点 } // 主函数示例 int main() { // 创建示例树 // 1 // / \ // 2 3 // / \ / // 4 5 6 TreeNode* root = createNode(1); root->left = createNode(2); root->right = createNode(3); root->left->left = createNode(4); root->left->right = createNode(5); root->right->left = createNode(6); printf("Tree Depth: %d\n", maxDepth(root)); printf("Total Nodes: %d\n", countNodes(root)); // 释放内存 freeTree(root); return 0; }

这段代码首先定义了二叉树节点的结构体TreeNode，然后实现了两个关键函数：maxDepth用于计算树的最大深度（层数），而countNodes用于计算树的节点总数。这两个函数都采用了递归的方式来进行计算。

要将计算树深度和总节点数的功能合并到一个函数中，我们可以定义一个辅助结构来同时存储这两个值首先，定义一个结构体来存储树的深度和节点总数：

#include #include typedef struct TreeNode { int value; struct TreeNode *left, *right; } TreeNode; typedef struct TreeInfo { int depth; int numNodes; } TreeInfo;

然后，实现一个递归函数来计算深度和节点总数：

TreeInfo calculateTreeInfo(TreeNode* root) { TreeInfo info = {0, 0}; // 初始化深度和节点数为0 if (root == NULL) { return info; // 如果当前节点为空，返回深度和节点数都为0的结构 } // 递归计算左右子树的信息 TreeInfo leftInfo = calculateTreeInfo(root->left); TreeInfo rightInfo = calculateTreeInfo(root->right); // 当前节点的深度是左右子树深度的最大值加1 info.depth = (leftInfo.depth > rightInfo.depth ? leftInfo.depth : rightInfo.depth) + 1; // 节点总数是左右子树节点数之和加上当前节点（1） info.numNodes = leftInfo.numNodes + rightInfo.numNodes + 1; return info; // 返回包含当前节点信息的结构 }

【本文地址】

【c++】计算树的深度和节点数

【c++】计算树的深度和节点数

今日新闻

推荐新闻