Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
#include <iostream>
#include <string>
struct {
int parent;
int child;
int sibling;
} typedef node;
using namespace std;
const int NIL = -1;
node tree[10000];
int D[10000];
// Calculate depth of nodes
void depth(int u, int p)
{
D[u] = p;
if (tree[u].sibling != NIL)
depth(tree[u].sibling, p);
if (tree[u].child != NIL)
depth(tree[u].child, ++p);
}
// MAIN FUNCTION
int main(int argc, char** argv)
{
// Input
int n;
cin >> n;
for (int i = 0; i < n; i++) {
tree[i].child = tree[i].parent = tree[i].sibling = NIL;
}
int degree;
int v;
int s;
int pre;
for (int i = 0; i < n; i++) {
cin >> v >> degree;
for (int j = 0; j < degree; j++) {
cin >> s;
if (j == 0)
tree[v].child = s;
else
tree[pre].sibling = s;
pre = s;
tree[s].parent = v;
}
}
int r = 0;
while (tree[r].parent != NIL)
r = tree[r].parent;
depth(r, 0);
// Output
for (int i = 0; i < n; i++) {
cout << "node " << i << ":" << " parent = " << tree[i].parent << ", depth = " << D[i] << ", ";
if (tree[i].parent == NIL)
cout << "root, [";
else if (tree[i].child == NIL)
cout << "leaf, [";
else
cout << "internal node, [";
r = tree[i].child;
if (tree[i].child != NIL)
cout << tree[i].child;
while (tree[r].sibling != NIL && tree[i].child != NIL) {
cout << ", " << tree[r].sibling;
r = tree[r].sibling;
}
cout << "]" << endl;
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment