木の走査.

Presentation on theme: "木の走査."— Presentation transcript:

1 木の走査

2 木の走査法 木の走査には次の種類がある 先行順 中央順 後行順 ※レベル順(ここでは扱わないことにする)

3 演算木 ＋ ５ ＊ ３ ４

4 先行順(考え方) ノード、左の子、右の子の順に訪れる。 数式だと、(+ 5 (* 3 4) )のように演算子が
左に来て、その後被演算子が2つ並ぶ形となる。 １ ５ ２ ６ ７ ３ ４

5 後行順(考え方） 左の子、右の子、ノードの順に訪れる。 数式だと (5 (3 4 *) +)のように被演算子が
2つ続いた後で演算子が来る形となる。 ７ ６ ３ ４ ５ １ ２

6 中央順（考え方） 左の子、ノード、右の子の順に訪れる。 数式だと 5+(3*4)のように演算子が2つの 被演算子に挟まれる形となる。 ４ ６
２ ５ ７ １ ３

7 プログラム例（宣言部） #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;

8 プログラム例(木の作成１） INTTREE* MakeTree(int n,INTTREE* root) {//２分探索木の作成
if (root==NULL) { root=(INTTREE *)malloc(sizeof(INTTREE)); root->node=n; root->L=root->R=NULL; }

9 プログラム例(木の作成２） 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;

10 プログラム例（木の要素の表示） void printint(INTTREE* root) { while (root!=NULL) {
printint(root->L); printf("% *d\n",root->node); printint(root->R); }

11 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); }

12 実行結果

13 実習 前述のプログラム例を書き直して 中央順、後行順を実現するプログラム にしてください。