【数据结构】树的繁荣度计算

整棵树全部遍历一遍必须访问所有节点不管二叉树、普通树不管递归还是非递归 时间复杂度\(\boldsymbol{O(n)}\)空间复杂度递归要看树高最坏单链树是 \(O(n)\)平衡二叉树是 \(O(\log n)\)。只访问某固定少数几个节点不随 n 变大而增加访问次数比如只取根节点或者只取根的左孩子不管这棵树总共有多少个节点 n永远只访问 2 个点 这才是常数时间 O (1)繁荣度 树的宽度某一层拥有的节点的最大数量方案先 DFS 收集所有节点深度 → 统计每层节点个数 → 取最大值纯 C 语言可直接编译运行。#include stdio.h #include stdlib.h // 多叉树节点 typedef struct Node { int data; struct Node** children; int child_cnt; } Node; // 创建节点 Node* createNode(int val) { Node* p (Node*)malloc(sizeof(Node)); p-data val; p-child_cnt 0; p-children NULL; return p; } // 添加子节点 void addChild(Node* parent, Node* child) { parent-child_cnt; parent-children (Node**)realloc(parent-children, sizeof(Node*) * parent-child_cnt); parent-children[parent-child_cnt - 1] child; } // dfs收集深度把每个节点的深度存入depthArr*len返回总节点数 void dfs(Node* root, int curDepth, int* depthArr, int* len) { if (root NULL) return; depthArr[(*len)] curDepth; for (int i 0; i root-child_cnt; i) { dfs(root-children[i], curDepth 1, depthArr, len); } } // 计算繁荣度最大层节点数 int calcProsperity(Node* root) { if (root NULL) return 0; // 最坏情况n个节点一条链我们开足够大数组这里演示最多1000个节点 const int MAX_N 1000; int depthArr[MAX_N]; int n 0; dfs(root, 1, depthArr, n); // 找最大深度 int maxDepth 0; for (int i 0; i n; i) { if (depthArr[i] maxDepth) { maxDepth depthArr[i]; } } // cnt[d] 深度d的节点数量 int* cnt (int*)calloc(maxDepth 1, sizeof(int)); for (int i 0; i n; i) { int d depthArr[i]; cnt[d]; } // 找最大值就是繁荣度 int prosper 0; for (int d 1; d maxDepth; d) { if (cnt[d] prosper) { prosper cnt[d]; } } free(cnt); return prosper; } int main(void) { // 构造样例树 /* A(1,深度1) / \ B C (深度2) | D (深度3) */ Node* A createNode(1); Node* B createNode(2); Node* C createNode(3); Node* D createNode(4); addChild(A, B); addChild(A, C); addChild(C, D); int ans calcProsperity(A); printf(繁荣度最大层节点数%d\n); // 预期输出2第2层有B、C两个节点 return 0; }深度优化思路前置计算树的最大深度最大深度斜树\(\boldsymbol{n}\)一条链最小深度尽量填满\(\boldsymbol{\lfloor \log_2 n \rfloor1}\)满二叉树\(\boldsymbol{n2^h-1}\)最终版本#include stdio.h #include stdlib.h typedef struct BNode { int data; struct BNode *left, *right; } BNode; BNode* createNode(int val) { BNode* p (BNode*)malloc(sizeof(BNode)); p-data val; p-left p-right NULL; return p; } /* 参数说明 root当前节点 curDepth当前节点的深度 depthArr保存每个节点的深度 len已经记录了多少个节点 返回值以root为根的子树的**最大深度** 这样一趟DFS**同时做两件事** 1把每个节点深度填进 depthArr 2返回这个子树最深是多少也就是maxDepth不需要事后遍历查找 */ int dfsCollectAndGetMaxDepth(BNode* root, int curDepth, int depthArr[], int* len) { if (root NULL) { return 0; } // 记录当前节点的深度 depthArr[(*len)] curDepth; int leftMax dfsCollectAndGetMaxDepth(root-left, curDepth 1, depthArr, len); int rightMax dfsCollectAndGetMaxDepth(root-right, curDepth 1, depthArr, len); // 当前子树最深深度 curDepth 和左右子树最大值里取大的 int myMaxDepth curDepth; if(leftMax myMaxDepth) myMaxDepth leftMax; if(rightMax myMaxDepth) myMaxDepth rightMax; return myMaxDepth; } int calcProsperity(BNode* root) { if(root NULL) return 0; const int MAX_N 1000; int depthArr[MAX_N]; int n 0; // ✅一次调用maxDepth直接拿到不用再for循环扫depthArr int maxDepth dfsCollectAndGetMaxDepth(root, 1, depthArr, n); int* cnt (int*)calloc(maxDepth 1, sizeof(int)); for(int i 0; i n; i) { int d depthArr[i]; cnt[d]; } int prosper 0; for(int d 1; d maxDepth; d) { if(cnt[d] prosper) { prosper cnt[d]; } } free(cnt); return prosper; } int main(void) { /* 1(深度1) / \ 2 3(深度2) / 4(深度3) */ BNode* A createNode(1); BNode* B createNode(2); BNode* C createNode(3); BNode* D createNode(4); A-left B; A-right C; C-left D; int ans calcProsperity(A); printf(繁荣度 %d\n); // 第2层有2、3两个节点 → 输出2 return 0; }