木の走査
木の走査法 木の走査には次の種類がある 先行順 中央順 後行順 ※レベル順(ここでは扱わないことにする)
演算木 ＋ ５ ＊ ３ ４
先行順(考え方) ノード、左の子、右の子の順に訪れる。 数式だと、(+ 5 (* 3 4) )のように演算子が 左に来て、その後被演算子が2つ並ぶ形となる。 １ ５ ２ ６ ７ ３ ４
後行順(考え方） 左の子、右の子、ノードの順に訪れる。 数式だと (5 (3 4 *) +)のように被演算子が 2つ続いた後で演算子が来る形となる。 ７ ６ ３ ４ ５ １ ２
中央順（考え方） 左の子、ノード、右の子の順に訪れる。 数式だと 5+(3*4)のように演算子が2つの 被演算子に挟まれる形となる。 ４ ６ ２ ５ ７ １ ３
プログラム例（宣言部） #include <stdio.h> #include <stdlib.h> static int intarray[]={4,7,3,2,1,8,9}; #define MINTS (sizeof(intarray)/sizeof(intarray[0])) typedef struct INTTREE { int node; struct INTTREE *L,*R; }INTTREE;
プログラム例(木の作成１） INTTREE* MakeTree(int n,INTTREE* root) {//２分探索木の作成 if (root==NULL) { root=(INTTREE *)malloc(sizeof(INTTREE)); root->node=n; root->L=root->R=NULL; }
プログラム例(木の作成２） else if (n<(root->node)) root->L=MakeTree(n,root->L); else if (n>(root->node)) root->R=MakeTree(n,root->R); else return NULL; return root;
プログラム例（木の要素の表示） void printint(INTTREE* root) { while (root!=NULL) { printint(root->L); printf("% *d\n",root->node); printint(root->R); }
main関数 void main(void) { INTTREE *head=NULL; int i; int key=0; for (i=0;i<MINTS;i++) head=MakeTree(intarray[i],head); printint(head); }
実行結果
実習 前述のプログラム例を書き直して 中央順、後行順を実現するプログラム にしてください。