有根树的表达 Aizu - ALDS1_7_A: Rooted Trees

佚名 7年前 (2019-06-07) 算法 1551人围观抢沙发百度已收录

有根树的表达

题目：Rooted Trees Aizu - ALDS1_7_A

A graph G = (V, E) is a data structure where V is a finite set of vertices and E is a binary relation on V represented by a set of edges. Fig. 1 illustrates an example of a graph (or graphs).

Fig. 1

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

A free tree is a connnected, acyclic, undirected graph. A rooted tree is a free tree in which one of the vertices is distinguished from the others. A vertex of a rooted tree is called "node."

Your task is to write a program which reports the following information for each node u of a given rooted tree T:

node ID of u
parent of u
depth of u
node type (root, internal node or leaf)
a list of chidlren of u

If the last edge on the path from the root r of a tree T to a node x is (p, x), then p is the parent of x, and x is a child of p. The root is the only node in T with no parent.

A node with no children is an external node or leaf. A nonleaf node is an internal node

The number of children of a node x in a rooted tree T is called the degree of x.

The length of the path from the root r to a node x is the depth of x in T.

Here, the given tree consists of n nodes and evey node has a unique ID from 0 to n-1.

Fig. 2 shows an example of rooted trees where ID of each node is indicated by a number in a circle (node). The example corresponds to the first sample input.

Fig. 2

Input

The first line of the input includes an integer n, the number of nodes of the tree.

In the next n lines, the information of each node u is given in the following format:

id k c₁ c₂ ... c_k

where id is the node ID of u, k is the degree of u, c₁ ... c_k are node IDs of 1st, ... kth child of u. If the node does not have a child, the k is 0.

Output

Print the information of each node in the following format ordered by IDs:

node id: parent = p , depth = d, type, [c₁...c_k]

p is ID of its parent. If the node does not have a parent, print -1.

d is depth of the node.

type is a type of nodes represented by a string (root, internal node or leaf). If the root can be considered as a leaf or an internal node, print root.

c₁...c_k is the list of children as a ordered tree.

Please follow the format presented in a sample output below.

Constraints

1 ≤ n ≤ 100000

Sample Input 1

0 3 1 4 10

1 2 2 3

2 0

3 0

4 3 5 6 7

5 0

6 0

7 2 8 9

8 0

9 0

10 2 11 12

11 0

12 0

Sample Output 1

node 0: parent = -1, depth = 0, root, [1, 4, 10]

node 1: parent = 0, depth = 1, internal node, [2, 3]

node 2: parent = 1, depth = 2, leaf, []

node 3: parent = 1, depth = 2, leaf, []

node 4: parent = 0, depth = 1, internal node, [5, 6, 7]

node 5: parent = 4, depth = 2, leaf, []

node 6: parent = 4, depth = 2, leaf, []

node 7: parent = 4, depth = 2, internal node, [8, 9]

node 8: parent = 7, depth = 3, leaf, []

node 9: parent = 7, depth = 3, leaf, []

node 10: parent = 0, depth = 1, internal node, [11, 12]

node 11: parent = 10, depth = 2, leaf, []

node 12: parent = 10, depth = 2, leaf, []

Sample Input 2

1 3 3 2 0

0 0

3 0

2 0

Sample Output 2

node 0: parent = 1, depth = 1, leaf, []

node 1: parent = -1, depth = 0, root, [3, 2, 0]

node 2: parent = 1, depth = 1, leaf, []

node 3: parent = 1, depth = 1, leaf, []

Note

You can use a left-child, right-sibling representation to implement a tree which has the following data:

the parent of u
the leftmost child of u
the immediate right sibling of u

Reference

Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. The MIT Press.

思路：

在写这个代码的时候，我其实是想用一个struct直接将这个树中的节点的信息全部包起来的（父节点，子节点，深度，节点类型）。但是，在敲的过程中发现，这是不可能的。或者说这会导致大量的空间的浪费，或许可以用vector试试，但是暂时没什么时间，就不去试试了。在看了挑战程序设计书上的思路之后，才发现原来这个树是可以用左子右兄弟表示法来表示。这样子，不仅可以非常便捷地将树表示出来，满足题目要求的输出也不会占用太长的代码，真是一个好的常规有根树的表示方法。

关于树的深度的判断，我是采用了递归的方法。首先，一定要找到这个树的根节点是哪一个节点，然后，在进入递归函数findde（int po,int h）。函数中的h一定是当前节点po的的深度，记录在de数组中。之后通过节点的右指针指向该节点的相邻的右兄弟的定义递归遍历树的这一层，最后递归遍历节点的子节点，深度加1。

 1 void findde(int po,int h)
 2 {
 3     de[po]=h;
 4     int ri=point[po].right;
 5     int le=point[po].left;
 6     if(ri!=-1)
 7         findde(ri,h);
 8     if(le!=-1)
 9         findde(le,h+1);
10 }

关于输出的话，其实就是注重一些格式的问题。不过有一点我想提一下，其实也是在敲代码的时候就出现的一点点问题。我一开始的时候用的是while循环来遍历这个节点的孩子。但是，会出现一些的格式问题，例如多了一点“, ”之类的，后来是用了两次判断l是否为-1来解决的问题，虽然是AC了，但是在while循环中其实是判断了两次的l是否为-1。这不是我希望的简洁的代码。于是我去看了一下书上的代码。惊为天人，原来还可以这样！他利用了for循环的特点完美地解决了我的问题，果然大佬就是大佬啊！

 1 //我的子节点的遍历输出
 2         int l=point[i].left;
 3         while(l!=-1)
 4         {
 5             cout<<l;
 6             l=point[l].right;
 7             if(l!=-1)
 8                 cout<<", ";
 9         }
10         cout<<"]"<<endl;
11         //大佬的子节点的遍历输出
12         for(int j=0,c=point[i].left;c!=-1;j++,c=point[c].right)
13         {
14             if(j) cout<<", ";
15             cout<<c;
16         }
17         cout<<"]"<<endl;

AC代码：

有根树的表达 Aizu - ALDS1_7_A: Rooted Trees 算法第1张

 1 #include <iostream>
 2 #include <string>
 3 #include <cstring>
 4 
 5 using namespace std;
 6 
 7 struct Node
 8 {
 9     int pa;
10     int left; //表示的是该节点的左子节点
11     int right; //表示的是该节点的第一个右兄弟
12 };
13 Node point[100005];
14 int de[100005];
15 int n;
16 
17 void findde(int po,int h)
18 {
19     de[po]=h;
20     int ri=point[po].right;
21     int le=point[po].left;
22     if(ri!=-1)
23         findde(ri,h);
24     if(le!=-1)
25         findde(le,h+1);
26 }
27 
28 void print()
29 {
30     for(int i=0; i<n; i++)
31     {
32         cout<<"node "<<i<<": parent = "<<point[i].pa<<", depth = "<<de[i]<<", ";
33         if(point[i].pa==-1)
34             cout<<"root, [";
35         else if(point[i].left==-1)
36             cout<<"leaf, [";
37         else
38             cout<<"internal node, [";
39         //我的子节点的遍历输出
40 //        int l=point[i].left;
41 //        while(l!=-1)
42 //        {
43 //            cout<<l;
44 //            l=point[l].right;
45 //            if(l!=-1)
46 //                cout<<", ";
47 //        }
48 //        cout<<"]"<<endl;
49         //大佬的子节点的遍历输出
50         for(int j=0,c=point[i].left;c!=-1;j++,c=point[c].right)
51         {
52             if(j) cout<<", ";
53             cout<<c;
54         }
55         cout<<"]"<<endl;
56     }
57 }
58 void init()
59 {
60     for(int i=0;i<n;i++)
61     {
62         point[i].pa=-1;
63         point[i].left=-1;
64         point[i].right=-1;
65     }
66 }
67 int main()
68 {
69     cin>>n;
70     memset(de,0,100005);
71     init();
72     for(int i=0; i<n; i++)
73     {
74         int a,num,l;
75         cin>>a>>num;
76         if(num)
77         {
78             cin>>l;
79             point[a].left=l;
80             point[l].pa=a;
81         }
82         for(int j=1; j<num; j++)
83         {
84             int x;
85             cin>>x;
86             point[l].right=x;
87             point[x].pa=a;
88             l=x;
89         }
90     }
91     int root=-1;
92     for(int i=0; i<n; i++)
93         if(point[i].pa==-1)
94             root=i;
95     findde(root,0);
96     print();
97     return 0;
98 }

View Code

总结：

这一次敲的代码反映了我的一些问题，如：敲代码之前总是不先想清楚需要的空间/定义的变量，导致写着写着忽然发现自己的想法好像不能实现，之后修改思路，这非常浪费时间。在一些细节方面，总是容易忽略，这就会导致我总是WA在细节上（虽然这一次没有），但是也在输入时候设置节点的双亲节点，子节点，兄弟节点的地方卡住了好一会。也可能是我自己的逻辑思维还是不够严密吧！加油呀！