cで木構造を書く2

memo c++ tree

http://serennz.sakura.ne.jp/sb/log/eid120.html
を読んだまとめ２。

前回作った木構造に作用する関数を書いてみます。
具体的には、
1. 自分の階層とその下の階層そのさらに下の階層と再帰的に作用する関数。
2. 自分の階層とその上の階層そのさらに上の階層と再帰的に作用する関数。
を作ります。

ここでは各nodeに作用する関数を、hogeとしましょう。
実装には再帰を用います。

まず1.の場合は

void re_hoge1 (node *n) {
  if(n == NULL) return;
  hoge(&n);
  re_hoge1(n->next); 
  re_hoge1(n->child);
  return;
}

この場合の終了条件は二行目 

if(n==NULL) return;

で、引数がNULLになることです。
３行目４行目では自分自身を呼び出しています。

 re_hoge1(n->next); 
 re_hoge1(n->child);

前回例で出した構造の場合にどのように動くのかを考えてみます。
re_hoge1(&root);
とすると、これはNULLではないので、一行目はスルー。
二行目でrootにhogeが作用します。
３行目のre_hoge1には,root.next=NULLなのでNULLが入ります。
しかしここで呼び出された関数は、一行目の条件を満たすので、何もしないで終了します。
4行目のre_hoge1には,root.child = n1が入ります。
以下n1.nextからn2,n1.childからn3に作用してと再帰的にhogeが作用して行きます。

2.の場合は

void re_hoge2 (node *n) {
  if(n == NULL) return;
  hoge(%n);
  re_hoge2(n->next);
  re_hoge2(n->parent);
  return;
}

とします。