求有根树所有子树大小

问题概述

给出一棵节点编号为1~n的有根树，计算它的所有子树的大小

输入格式：第一行为一个整数n；第二行是n个整数，依次表示编号为1到n的节点的父亲编号。特别的，父亲编号为0表示这个点是根。

输出格式：输出一行，n个整数，依次表示编号为1到n的节点为根的子树的大小。

思路整理

题目的特殊性在于树的构建：第一，这不是二叉树，而是多叉树；第二，输入的是每一个节点的父亲而非孩子。

解决方法在于，为每一个节点维护一个孩子链表（存储孩子节点的编号而非指向孩子的指针），同时为所有节点按照编号创建一个节点数组，以便按照编号访问节点。

在多叉树创建完毕后，就可以计算每个子树的大小了，无疑，采用递归策略。这里有一个小细节，可以用一个数组存储那些已经被计算出的子树大小，以免递归过程中重复计算（当然，这样会消耗空间，也算是以空间换时间吧）。

代码与注释

#include
   
    #include
    
     #include
     
      int hms[1000005] = {
    0 };struct ListNode {
    int data; struct ListNode* Next; struct ListNode* Last;};struct List {
    struct ListNode* header; struct ListNode* trailer; int _size;};void CreateList(struct List* l)//build the list{
    l->_size = 0; l->header = (struct ListNode*)malloc(sizeof(struct ListNode)); l->trailer = (struct ListNode*)malloc(sizeof(struct ListNode)); l->header->Next = l->trailer; l->header->Last = NULL; l->trailer->Last = l->header; l->trailer->Next = NULL;}void InsertList(struct List* l, int e)//空表，在尾节点前插入{
    struct ListNode* np = (struct ListNode*)malloc(sizeof(struct ListNode)); np->data = e; np->Next = l->trailer; np->Last = l->trailer->Last; l->trailer->Last->Next = np; l->trailer->Last = np; l->_size++;}

这里构建了队列数据结构，以及上文提到的用于存储已经计算出的子树大小的数组hms

int how_many_c(int c, struct List* tnodes){
    if (hms[c])  return hms[c];//避免重复计算 else {
     struct List now = tnodes[c];  if (now._size == 0)  {
      hms[c] = 1;   return 1;//边界情况，返回1  }  else  {
   //递归计算各个孩子的子树大小之和   struct ListNode* curr = now.header->Next;   int childnum = 0;   while (curr != now.trailer)   {
       childnum += how_many_c(curr->data, tnodes);    curr = curr->Next;   }   childnum++;   hms[c] = childnum;   return childnum;  } }}

这就是核心函数，递归计算子树大小。

int main(){
    int tnode_num; scanf("%d", &tnode_num); struct List* treenodes = (struct List*)calloc(tnode_num + 1, sizeof(struct List)); for (int i = 1; i <= tnode_num; i++)  CreateList(&(treenodes[i])); for (int i = 1; i <= tnode_num - 1; i++) {
     int tmp;  scanf("%d", &tmp);  if (tmp)   InsertList(&(treenodes[tmp]), i);  scanf(" "); } int fin; scanf("%d", &fin); if (fin)  InsertList(&(treenodes[fin]), tnode_num); for (int i = 1; i <= tnode_num; i++) {
     printf("%d", how_many_c(i, treenodes));  printf(" "); }}

主函数，对于输入的处理不够优雅，还请海涵。

完

转载地址：http://szwai.baihongyu.com/

你可能感兴趣的文章