首页 > 代码库 > PAT 1004. Counting Leaves (30) C#实现
PAT 1004. Counting Leaves (30) C#实现
A family hierarchy is usually presented by a pedigree tree. Your job is to count those family members who have no child.
Input
Each input file contains one test case. Each case starts with a line containing 0 < N < 100, the number of nodes in a tree, and M (< N), the number of non-leaf nodes. Then M lines follow, each in the format:
ID K ID[1] ID[2] ... ID[K]
where ID is a two-digit number representing a given non-leaf node, K is the number of its children, followed by a sequence of two-digit ID‘s of its children. For the sake of simplicity, let us fix the root ID to be 01.
Output
For each test case, you are supposed to count those family members who have no child for every seniority level starting from the root. The numbers must be printed in a line, separated by a space, and there must be no extra space at the end of each line.
The sample case represents a tree with only 2 nodes, where 01 is the root and 02 is its only child. Hence on the root 01 level, there is 0 leaf node; and on the next level, there is 1 leaf node. Then we should output "0 1" in a line.
Sample Input
2 101 1 02
Sample Output
0 1
//------------------------------------------------------------------------------------------------------------------------------------------------------
采用C#编写，代码如下：
1 public struct Node 2 { 3 public int level; 4 public int K; 5 public int Parent; 6 public List<int> children; 7 }; 8 9 static Node[] node; 10 11 static void Main(string[] args) 12 { 13 string[] str; 14 int N, M; 15 int i, j; 16 List<Node>[] LEVEL; 17 18 do 19 { 20 str = Console.ReadLine().Split(new Char[] { ‘ ‘ }); 21 N = Convert.ToInt32(str[0]);//总节点数 22 M = Convert.ToInt32(str[1]);//非叶子节点数 23 } while (N >= 100 && N <= 0); 24 25 //用于存放N个节点的信息（，深度、孩子数、母节点、孩子节点数组） 26 //并且该节点ID和其在node[]中的索引号对应：index=ID-1 27 node = new Node[N]; 28 29 LEVEL = new List<Node>[N];//List数组，每一个List存放对应深度的所有Node节点 30 31 int id = 0; 32 33 //将非叶子节点数据存进相应的数据结构中 34 35 for (i = 0; i < M; i++) 36 { 37 str = Console.ReadLine().Split(new Char[] { ‘ ‘ }); 38 id = Convert.ToInt32(str[0]); 39 node[id - 1].level = 1;//初始化所有节点的深度，皆置为1； 40 node[id - 1].K = Convert.ToInt32(str[1]);//获取每一个节点对应的孩子数 41 42 //生成一个List<int>类型的实例，用来存放该节点对应的孩子节点 43 node[id - 1].children = new List<int>(); 44 45 for (j = 0; j < node[id - 1].K; j++) 46 { 47 //将该节点所有的孩子节点存进结构中 48 node[id - 1].children.Add(Convert.ToInt32(str[j + 2])); 49 //为每个子女设置parent的ID，parent在进行遍历设置每一个节点的深度level时至关重要 50 node[Convert.ToInt32(str[j + 2]) - 1].Parent = id; 51 } 52 } 53 node[0].Parent = 0;//设根节点的父母节点为0； 54 55 //将叶子节点数据存进相应的数据结构中 56 for (i = 0; i < N; i++) 57 { 58 if (node[i].level != 1) 59 { 60 node[i].level = 1; 61 node[i].K = 0;//孩子数为0 62 node[i].children = new List<int>();//有实例，但是没有孩子内容 63 } 64 } 65 66 67 arrangelevel(1);//从根节点（ID=1）遍历设置所有树节点深度level值 68 69 int MaxLevel = 0;//最大深度值 70 foreach (Node p in node) 71 { 72 if (p.level > MaxLevel) 73 MaxLevel = p.level; 74 } 75 76 77 for (i = 0; i < MaxLevel; i++)//按照不同深度，将所有的节点归类，放入对应深度的list中 78 { 79 LEVEL[i] = new List<Node>(); 80 foreach (Node n in node) 81 { 82 if (n.level == i + 1) 83 LEVEL[i].Add(n); 84 } 85 } 86 87 int count;//同一深度的叶子节点数 88 //获得每一层次叶子节点数，并输出 89 for (i = 0; i < MaxLevel; i++) 90 { 91 count = 0; 92 foreach (Node n in LEVEL[i]) 93 { 94 if (n.K == 0) 95 count++; 96 } 97 Console.Write(count); 98 99 if (i != MaxLevel - 1)100 {101 //当不是最后一个时，作为输出的两个值之间的间隔符，确保最后没有空格102 Console.Write(" ");103 }104 }105 Console.ReadKey();//使得控制台不至于一闪而过106 107 }108 109 //对每一个节点进行层次level确定110 //对于每一个访问到的节点，设置其深度level值为其母节点level+1；111 public static void arrangelevel(int ID)112 {113 foreach (int childid in node[ID - 1].children)114 {115 if (node[childid - 1].K > 0)116 {117 //遍历到的节点的level值等于其母节点level值加1118 node[childid - 1].level = node[node[childid - 1].Parent - 1].level + 1;119 120 arrangelevel(childid);//进一步深度遍历121 }122 else123 {124 node[childid - 1].level = node[node[childid - 1].Parent - 1].level + 1;125 }126 }127 return;128 }
测试用例：
10 5
01 2 02 03
02 2 04 05
03 2 06 07
05 1 08
07 2 09 10
输出：
0 0 2 3
PAT 1004. Counting Leaves (30) C#实现