cで木構造を書く1

c++ memo tree

http://serennz.sakura.ne.jp/sb/log/eid120.html
このページを参考に。
自分用に調べたことをまとめておきます。
院試が終わって時間が空けば自分で実装してみる予定。


実装にはポインターを用います。

struct node {
  struct node * parent;
  struct node * child;
  struct node * next;
  char *name;
  int depth;
};

nodeは自身と同じ型への３つのポインターparent,child,nextを持つ構造体として定義されます。
ここで,parentは今のnodeの一つ上のnodeを,nextはひとつ隣の,childはひとつ下のnodeを表します。
少し例を見てみましょう。

例えばroot以下、n1,n2,n1以下n3,n4が続くような構造を表したいのであれば、

- root
  - n1
    - n3
  - n2

まずrootを次の用に定義します。

node root, n1, n2, n3, n4;
root.parent = NULL;
root.child = &n1;
root.next = NULL;

rootは木構造の頂点に位置するのですからこれより上(parent)はありません(NULL)。
また今の例では頂点は一つですから同じ階層にこれに隣接するnodeもありません。(root.next = NULL)
rootの下にはn1が位置します(root.child = &n1）

次に,n1を定義します。

n1.parent = &root;
n1.child = &n3;
n1.next = &n2;

n1の上にはrootがあります。(n1.parent = &root)
n1の下にはn3が、同じ階層の隣にはn2があります。(n1.child = &n3, n1.next = &n2)

最後にn3,n2を定義しましょう。

n2.parent = &root;
n2.child = NULL;
n2.next = NULL;

n3.parent = &n1;
n3.child = NULL;
n3.next = NULL;

これで図の木構造を構成できたことになります。