今回は木 （アルゴリズムＣ 第１巻 p.41） についてです。木の構造や、辿り方について理解してください。
(1) 次の木の名称が、図のどの節点（ノード）に該当するかを答えなさい。
根（root）：
G の親（parent）：
B の子（child）：
H の兄弟（sibling）：
外部節点（external node）：
内部節点（internal node）：
高さ（height）：
Ｃのレベル（level）：
道長（path length）：
(2) 次の中置記法で書かれた式の解析木を書きなさい。
4*(3+2)+1
(3) (2) で作成した木を、preorder、inorder、postorder でトラバースした結果を書きなさい。
(1) は用語 （アルゴリズムＣ 第１巻 p.42） に関する問題です。木は用語が多いので、 教科書で用語の意味をよく確認して答えてください。
(2) は解析木
（アルゴリズムＣ 第１巻 p.47）
を作る問題です。例えば、1+2*3 の解析木は
このようになります。
左側の木は間違いです。この木で計算すると答えが 9 になってしまいます。
演算の優先順位に気をつけて気を作ってください。
(3) はトラバース （アルゴリズムＣ 第１巻 p.51） する問題です。三種類の辿り方によって、ノードを通る順番が 変わります。先程の解析木の例では、このようになります。
preorder: +1*23 inorder: 1+2*3 postorder: 123*+
preorder、inorder、postorder の結果はそれぞれ、 前置記法、（括弧のない）中置記法、後置記法になります。
ノードの中身を表示しながらトラバースする関数
void preorder(NodePointer node); void inorder(NodePointer node); void postorder(NodePointer node);
を再帰を使って書きなさい。ファイルは ex06-2-skel.c を使用すること。
実行例： % ./a.out preorder: + 1 * 2 3 inorder: 1 + 2 * 3 postorder: 1 2 3 * +
演習第２回のリストを応用して、木を作ります。 ex06-2-skel.c をよく読んでから、 関数を作成してください。
まず構造体 node は次のようになっています。
struct node {
struct node *right;
char key;
struct node *left;
};
right が右のノードへのポインタ、 left が左のノードへのポインタ、 key がノードの持つ値です。 実際にノードを作るのは makenode 関数で、malloc をして、左右には tail ノード （何も繋っていない状態）を代入しています。
main 関数の前半で 1+2*3 の解析木を作成しています。
どのように木が繋がっているかをよく確認してください。
通常はこのような木の作り方はせず、演習第７回でやるように、
木に繋ぐ関数を作って繋いでいきます。
トラバースする関数は再帰を用いて作成します。 左右に辿るときに tail かどうかを調べて、 tail でなければ再帰して木を辿ります。
後置記法から解析木を作成するプログラムを書きなさい。 必要であれば、演習第３回 で使用した関数などを 用いても良い。
実行例： % ./a.out Input data by Reverse Polish Notation: 123*+ preorder: + 1 * 2 3 inorder: 1 + 2 * 3 postorder: 1 2 3 * +
解析木を作るには、演習第３回でやったスタック を使います。処理の流れはほぼ同じです。計算を行なう代わりに木として 繋げていきます。
演習第３回の問題２ と大きく異なるのはスタックの扱うデータの型です。演習第３回ではスタックには int 型を入れていましたが、ここでは NodePointer 型を入れることになります。 配列を宣言するときの型や、push 関数や pop 関数の引数や返り値の型に 気を付けてください。