【2分木】に関する知恵袋
【質問】
C言語のプログラミングで困っています。分木の知恵袋についてだが、レンタルサーバの説明をすると、葉以外の点が2個ずつの個を持つ２分木をデータを入力して作成し、分木の知恵袋に関する説明をすると、データの最後に１が入力されたらpreorderデータの最後に２が入力されたらinorderデータの最後に3が入力されたらpostorderでそれぞれデータを出力せよという問題がわからなくて困っています。preorderだけならば下記のように作成し、実行できたので後半部分を変えれば他２つもできると思うのですが、問題のようにするにはどうしたらいいでしょうか？レンタルサーバを理解したいのであれば、#include <stdio.h> #include <stdlib.h> struct btree{ int element; struct btree *left; struct btree *right;};struct btree *input(int node){ int lc,rc; struct btree *p; if (node == 0){ printf("Enter Root :"); scanf("%d",&node); if (node<0) exit(1); } printf("Enter Left and Right child of %d :",node); scanf("%d %d",&lc,&rc); p=(struct btree *)malloc(sizeof(struct btree)); p->element=node; if(lc >= 0 && rc >= 0){ p->left=input(lc); p->right=input(rc); } else{ p->left=NULL; p->right=NULL; } return(p);}void disp_tree(struct btree *p, int depth, int dire){ int i; if (p!=NULL){ disp_tree(p->right,depth+1,2); if (dire == 0) printf(" "); else{ for(i=1;i<=depth;++i) printf(" "); if (dire == 2) printf("/"); if (dire == 1) printf("-"); } printf(" %d\¥n",p->element); disp_tree(p->left,depth+1,1); }}void preorder(struct btree *p) { struct btree *q; q=p; if (q != NULL){ printf(" %d", q->element); preorder(q->left); preorder(q->right); }}int main(void) { struct btree *root; root=input(0); disp_tree(root,0,0); printf("preorder="); preorder(root); printf("\¥n"); return(0);}
【解答】
/*最後のデータの取り出しには、disp_tree()を変形して使うことにしました。元の disp_tree()では right優先表示だったのを left優先表示に変えました。そうすれば入力時の最後のデータが最後に表示されるからです。また、right のデータが表示されるたびに、そのときのポインタの値を static領域に上書きして控えることにしました。呼んだ main()側でその控えのポインタの指す値を使うことにより、レンタルサーバであれば、分木の知恵袋に関する解説をすると、データの最後の値による振り分けをするようにしました。レンタルサーバを見ると、disp_tree()を元のままにするなら、return で値を二つ戻すことはできないので、input()で int型へのポインタ引数を1つふやし、入力する値の控えを取っておき、main()側で、その値を使うようにすればいいですが、少々面倒です。>データの最後に１が入力されたらpreorder>データの最後に２が入力されたらinorder>データの最後に3が入力されたらpostorderでは、分木の知恵袋をいうと、1,2,3以外の値が最後のデータだったらどうするかが示されていないのと、入力の自由度がなくなるのが嫌なので、拡大解釈して、最後のデータが3の倍数+n (n=0～2)のときで振り分けることにしました。それなら1,2,3 については、一応上の条件は満たすからです。（3 のときは、3で割った余りが 0 なので、n=0 です。）preorder, inorder, postorder の処理における並び順は、どれも if(p-> left != NULL) XXXorder(p->left); if(p->right != NULL) XXXorder(p->right);という形になります。（XXX は pre, in, post のいずれか） printf(" %d", p->element); をどの段階で表示するかだけの違いです。。つまり、最初のif文に入る前にやるか、二つのif文の間でやるか,最後のif文の後でやるかだけの違いです。参考になれば幸いです。*/#include <stdio.h> #include <stdlib.h> struct btree{ int element; struct btree *left; struct btree *right;};struct btree *input(int node){ int lc,rc; struct btree *p; if (node == 0){ printf("Enter Root :"); scanf("%d",&node); if (node<0) exit(1); } printf("Enter Left and Right child of %d :",node); scanf("%d %d",&lc,&rc); p=(struct btree *)malloc(sizeof(struct btree)); p->element=node; if(lc >= 0 && rc >= 0){ p->left=input(lc); p->right=input(rc); } else{ p->left=NULL; p->right=NULL; } return p;}// 元のかんすうで right と left を入れ換えて left優先の探索表示に変えた// 必然的に作成時の最後のデータが最後に表示される// - で表示されるデータのポインタを pp に控えておく。// pp は static 領域に取られるので、変化する場合は上書き更新されるstruct btree* disp_tree(struct btree *p, int depth, int dire){static struct btree *pp; int i; if (p!=NULL){ disp_tree(p->left,depth+1,2); if (dire == 0) putchar(' '); else{ for(i=1;i<=depth;++i) putchar(' '); if (dire == 2) putchar('/'); if (dire == 1){ putchar('-'); pp=p; } } printf(" %d\¥n",p->element); disp_tree(p->right,depth+1,1); } return pp;}void preorder(struct btree *p) // 元の関数でもいいですが、他のorderとの形を合わせたほうがすっきりします。{ printf(" %d", p->element); if(p-> left != NULL) preorder(p->left); if(p->right != NULL) preorder(p->right);}void inorder(struct btree *p) { if(p-> left != NULL) inorder(p->left); printf(" %d", p->element); if(p->right != NULL) inorder(p->right);}void postorder(struct btree *p) { if(p-> left != NULL) postorder(p->left); if(p->right != NULL) postorder(p->right); printf(" %d", p->element); }int main(void) { struct btree *root, *p; p=root=input(0); printf("最後に表示されたデータ：p->element=%d\¥n", p->element); p=disp_tree(root,0,0); // printf("最後に表示されたデータ：p->element=%d\¥n", p->element); switch(p->element % 3){ // 3で割った余りにより振り分ける case 0: printf("postorder="); postorder(root); putchar('\¥n'); break; case 1: printf("preorder="); preorder(root); putchar('\¥n'); break; case 2: printf("inorder="); inorder(root); putchar('\¥n'); break; } return 0;} /*実行例Enter Root :1Enter Left and Right child of 1 :2 3Enter Left and Right child of 2 :4 5Enter Left and Right child of 4 :-1 -1Enter Left and Right child of 5 :6 7Enter Left and Right child of 6 :-1 -1Enter Left and Right child of 7 :-1 -1Enter Left and Right child of 3 :8 9Enter Left and Right child of 8 :-1 -1Enter Left and Right child of 9 :-1 -1__/ 4_/ 2___/ 6__- 5___- 7__1__/ 8_- 3__- 9postorder= 4 6 7 5 2 8 9 3 1*/
