根付き木を C++ で実装してみたメモ． RootedTree(int n) で index が 0, 1, ..., (n-1) までのノードを作成． AddChild(n,m) で n を m の子供に指定する．

RootedTree.cc

#include<iostream>
#include<cstdio>

class RootedTree {
  int** tree;
public:
  RootedTree(int s) {
    tree = new int*[3];
    tree[0] = new int[s](); // pointer to parent
    tree[1] = new int[s](); // pointer to first child
    tree[2] = new int[s](); // pointer to next brother
  }
  ~RootedTree() {
    delete [] tree;
  }
  void AddChild(int c, int p) {
    tree[0][c] = p;
    tree[2][c] = tree[1][p];
    tree[1][p] = c;
  }
  void ShowParent(int v) {
    printf("%02d's parent: %02d\n",v,tree[0][v]);
  }
  void ShowChildren(int v) {
    int c = tree[1][v];
    if (c==0) {
      printf("%02d has no child.\n",v);
      return;
    }
    do {
      printf("%02d is %02d's child.\n",c,v);
      c = tree[2][c];
    } while (c!=0);
  }
  void ShowAncestors(int v) {
    int p = tree[0][v];
    do {
      printf("%02d is %02d's ancestor.\n",p,v);
      p = tree[0][p];
    } while(p!=0);
    printf("%02d is %02d's ancestor.\n",p,v);  
  }
  void ShowDescendants(int v, int dps=0) {
    printf("%02d",v);
    if (tree[1][v] == 0) {
      printf("\n");
      return;
    } // no child
    printf("--");
    int c = tree[1][v];
    do {
      this->ShowDescendants(c,dps+1);
      if (tree[2][c]!=0) {
        for (int i=0; i<=dps; ++i) printf("    ");
      }
      c = tree[2][c];
    } while(c!=0);
  }
};

int main() {
  RootedTree rt(22);
  rt.AddChild(3,0);  rt.AddChild(2,0);  rt.AddChild(1,0);
  rt.AddChild(6,1);  rt.AddChild(5,1);  rt.AddChild(4,1);
  rt.AddChild(12,4); rt.AddChild(11,4);
  rt.AddChild(14,6); rt.AddChild(13,6);
  rt.AddChild(7,2);
  rt.AddChild(10,3); rt.AddChild(9,3);  rt.AddChild(8,3);
  rt.AddChild(17,8); rt.AddChild(16,8);  rt.AddChild(15,8);
  rt.AddChild(19,10); rt.AddChild(18,10);
  rt.AddChild(21,17);  rt.AddChild(20,17);
  rt.ShowDescendants(0);
  return 0;
}