• ベストアンサー

二分木のなぞり

ノードにデータが与えられているものとして帰りがけで二分木をなぞり、ノードに立ち寄った順にデータを書き出すときにそのデータが大きい順に並んでいるか判定するプログラムを作りたいです。 typedef struct node Node; struct node{ int data; Node* left; Node* right; }; int flag; void postorder(Node * p) { int kakunou; if( p == NULL ){ return 0 ; } postorder( p->left ); postorder( p->right ); 　　　　　kakunou=p->data; 　　　　　if(kakunou<p->data){ 　　　　　flag=1; } printf( "%2d ", p->data ); } そこで上のようにkakunouにひとつ前に出力したp->dataを格納し、kakunouとp->dataを比べた時にkakunouの方が小さければflag（グローバル変数）を1にしmain関数でflagが1なら、"大きい順ではない"と出力しようと思うのですが、kakunouとp->dataの値が同じになってしまいます。 どのタイミングでkakunou=p->data;を入れればよいのか、また根本的に考え方がおかしいなら方針を教えていただきたいです。よろしくお願いします。

質問者が選んだベストアンサー

  • ベストアンサー
回答No.3

　　　　　kakunou=p->data; 　　　　　if(kakunou<p->data){ って、代入したあと比較したら同じなのは当然ですね。 kakunouをグローバル変数にして(初期値は一番小さい値か何か？) 比較したあとkakounouを更新してはどうでしょう。。

chan-fu
質問者

お礼

グローバルにして比較した後に更新したらいけました！ありがとうございます。

その他の回答 (2)

  • asuncion
  • ベストアンサー率33% (2126/6288)
回答No.2

No.1の者です。 二分木を帰りがけ順に探索したとき、データの大小順はくずれます。 そういった状況で、「ノードに立ち寄った順にデータを書き出すときに そのデータが大きい順に並んでいるか判定するプログラム」を 作る意味合いがどの程度あるのかはよくわかりません。

  • asuncion
  • ベストアンサー率33% (2126/6288)
回答No.1

> 帰りがけで二分木をなぞり、ノードに立ち寄った順にデータを書き出すときにそのデータが大きい順に並んでいるか判定するプログラム 二分木を正しく作っていれば、「通りがけ順」に探索すると データの「大小順は保証」されています。 判定の必要はありません。

chan-fu
質問者

補足

二分探索木ではないので「左部分木の要素の方が小さくて、右部分木の要素の方が大きくなる」というようにはデータは与えていません。 テキトーにデータを与えたときに大きい順に整列しているか否かを見るだけのプログラムです。 これで捕捉になっているでしょうか…

  1. カテゴリ
  2. [技術者向] コンピューター
  3. プログラミング・開発
  4. C・C++・C#

関連するQ&A

  • 2分木のノードの指定方法を変えたい

    下のプログラムはコマンドライン引数できまった形で入力した数を2分木にしてそれを表示させるc言語のプログラムです。 きまった形というのは 短縮形は　[ 8 [ 7 2 5 ] [ 3 1 _ ] ] 短縮形でないのは　[ 8 [ 7 [ 2 _ _ ] [ 5 _ _ ] ] [ 3 [ 1 _ _ ] _ ] ] ] のような形で、実行結果はそれぞれ a.exe [ 8 [ 7 2 5 ] [ 3 1 _ ] ] 入力データ [ 8 [ 7 2 5 ] [ 3 1 _ ] ] a.exe [ 8 [ 7 [ 2 _ _ ] [ 5 _ _ ] ] [ 3 [ 1 _ _ ] _ ] ] ] 入力データ [ 8 [ 7 2 5 ] [ 3 1 _ ] ] のようになります。 これをこのような形ではなくコマンドラインで 8 7 3 2 5 1 と入力するだけで2分木になるように 下のプログラムを変えたいのです。 よろしくお願いします。 #include <stdio.h> #include <stdlib.h> #include <string.h> typedef int BITREE_TYPE; /* 格納データの型 */ struct node { BITREE_TYPE value; /* ノードの値 */ struct node *left; /* 左ノードのアドレス */ struct node *right; /* 右ノードのアドレス */ }; typedef struct node BITREE_NODE; void error(char *msg); BITREE_NODE *createNode(BITREE_TYPE x); void destroyBITree(BITREE_NODE *p); int isLeafNode(BITREE_NODE *p); void printBITree(BITREE_NODE *p, int tabs, int brief); BITREE_NODE *inputBITree(char *str[], int len, int *end); int gShortFormat = 1; /*１ならば短縮形で出力する*/ void error(char *msg){ fflush(stdout); fprintf(stderr,"%s\n", msg); exit(1); } BITREE_NODE *createNode(BITREE_TYPE x){ BITREE_NODE *new; new = malloc(sizeof(struct node)); if(new == NULL) error("createNode: メモリがありません"); new->value = x; new->left = NULL; new->right = NULL; return new; } void destroyBITree(BITREE_NODE *p){ if(p == NULL) return; destroyBITree(p->left); destroyBITree(p->right); memset(p, 0, sizeof(struct node)); free(p); } int isLeafNode(BITREE_NODE *p){ return(p->left == NULL) && (p->right == NULL); } void printSubtree(BITREE_NODE *p){ if(p == NULL){ printf("_"); return; } if(gShortFormat != 0 && isLeafNode(p)){ printf("%d", p->value); } else{ printf("[ "); printf("%d ", p->value); printSubtree(p->left); printf(" "); printSubtree(p->right); printf(" ]"); } } void printBITree(BITREE_NODE *p, int tabs, int brief){ int i; gShortFormat = brief; for (i = 0; i<tabs; i++) printf("\t"); printSubtree(p); printf("\n");fflush(stdout); } BITREE_NODE *inputBITree(char *str[], int len, int *end){ BITREE_NODE *p; int i =0; if(len < 1) error("inputBITree:データがありません"); /*短縮形の処理*/ if(strcmp(str[0], "[") != 0){ if(strcmp(str[0], "_") == 0) error("inputBTITree:値に＿は指定できません"); *end =1; return createNode(atoi(str[0])); } p = createNode(atoi(str[1])); i = 2; if(strcmp(str[i], "_") != 0){ p->left = inputBITree(&str[i], len -i, end); i+= *end; } else{ i++; } if(strcmp(str[i], "_") != 0){ p->right = inputBITree(&str[i], len -i, end); i+= *end; } else{ i++; } if(strcmp(str[i], "]") != 0) error("inputBITree: 入力データが]で終わっていません"); *end = i + 1; return p; } int main(int argc, char *argv[]){ BITREE_NODE *p; int end = 0; p = inputBITree(argv+1, argc-1, &end); printf("入力データ "); printBITree(p,0,1); destroyBITree(p); return 0; }

  • 2分木

    実行すると 「トップノードの値を入力してください。20 ノード[20:深さ0]の左の子の値を入れてください。15 ノード[20:深さ0]の右の子の値を入れてください。40 ノード[15:深さ1]の左の子の値を入れてください。11 ノード[15:深さ1]の右の子の値を入れてください。18 ノード[11:深さ2]の左の子の値を入れてください。/ ノード[18:深さ2]の左の子の値を入れてください。17 ノード[18:深さ2]の右の子の値を入れてください。/ 　　　　　　　　　　・ が表示されて2分木のデータを作成するプログラムを作りたいのです。絵で表すと、 　　　　　 20 ／ ＼ 　　　　15 40 ／ ＼ ／＼ 11 18 30 55 ／ ／＼ ＼ 17 25 33 61 のようになります(なんか絵がずれて表示される）。 一応、自分で考えてみたのですが #include<stdio.h> #include<malloc.h> struct data { int kazu; struct data *left; struct data *right; }; main() { struct data *root,*p; root=(struct data *)malloc(sizeof(struct data)); printf("トップノードの値を入れてください:"); scanf("%d",root->kazu); root->left=root->right=NULL; while(1){ p=(struct data *)malloc(sizeof(struct data)); printf("ノード%d,深さ%dの左の子の値を入れてください",root->kazu, scanf("%d", ); printf("ノード%d,深さ%dの右の子の値を入れてください",root->kazu, scanf("%d", ); if( break; なんか全然良くわからないのです。アルゴリズムの本を見て勉強していて、データ構造は理解できたのですが、２分木(グラフ)で詰まってしまいました。 小さい順に数を表示させるとか、そういうのじゃなくて、単にデータを格納するだけです。どうかよろしくお願いします。

  • c言語で2分探索木のを2分木に変えたい

    2分木のプログラムを書いているのですが、ある数列を2分木にしたいのです。 2分探索木のプログラムを参考に書いていて、その一部が typedef int BSTREE_K_TYPE; typedef int BSTREE_V_TYPE; struct bsnode { BSTREE_K_TYPE key; BSTREE_V_TYPE value; struct bsnode *left; struct bsnode *right; }; typedef struct bsnode BSTREE_NODE; int gShortFormat = 1; void error(char *msg){ fflush(stdout); fprintf(stderr, "%s\n", msg); exit(1); } BSTREE_NODE *createNode(BSTREE_K_TYPE x){ BSTREE_NODE *new; new = malloc(sizeof(BSTREE_NODE)); if(new == NULL) error("createNode:　メモがありません"); new->key = x; new->value = 0; new->left = NULL; new->right = NULL; return new; } BSTREE_NODE *insertNode(BSTREE_NODE *p, BSTREE_K_TYPE x){ if (p == NULL){ } else if (p->key == x){ error("insertNode: 指定キーのノードが含まれています"); } else if (p->key > x){ p->left = insertNode(p->left, x); } else { p->right = insertNode(p->right, x); } return p; } BSTREE_NODE *inputBSTree(BSTREE_NODE *btree, char *str[], int len, int *end){ BSTREE_K_TYPE x; int i, n = 0; for(i = 0; i < len; i++){ if(!strcmp(str[i], "--")) break; x = atoi(str[i]); if(btree == NULL) btree = createNode(x); else btree = insertNode(btree, x); n++; } *end = n; return btree; } このinsertNodeのifの条件を変えればいいのかと思い、いろいろ試してみたのですが、 左部分木には左側にしか葉がなく、右部分木には右にしか葉がないようなものしかできませんでした もう何時間も悩んだのですが自分の知識では手づまりです どうかよろしくお願いします。

  • 解析木

    ノードの中身を表示しながらトラバースする関数 void preorder(NodePointer node); void inorder(NodePointer node); void postorder(NodePointer node); を再帰を使って書きなさい。 という問題がとけません。どなたかアドバイスをください。 ちなみに、この関数以外は下のように作りました。 #include <stdio.h> #include <stdlib.h> struct node { struct node *right; char key; struct node *left; }; typedef struct node * NodePointer; void treeinitialize(void); NodePointer makenode(char c); void preorder(NodePointer node); void inorder(NodePointer node); void postorder(NodePointer node); NodePointer head, tail; int main(){ treeinitialize(); //テスト用の木を作成 head->right=makenode('+'); head->right->left=makenode('1'); head->right->right=makenode('*'); head->right->right->left=makenode('2'); head->right->right->right=makenode('3'); //トラバース printf("preorder: "); preorder(head->right); printf("\n"); printf("inorder: "); inorder(head->right); printf("\n"); printf("postorder: "); postorder(head->right); printf("\n"); return 0; } void treeinitialize(void){ head=makenode(-1); tail=makenode(-1); head->right=tail; head->left=tail; } //ノードを作成し、そのノードへのポインタを返す。 NodePointer makenode(char c){ NodePointer x; x=malloc(sizeof(struct node)); x->key=c; x->right=tail; x->left=tail; return x; } void preorder(NodePointer node){ } void inorder(NodePointer node){ } void postorder(NodePointer node){ }

  • 二分探索木のプログラム

    ２分探索木のプログラムを作っているのですが、実行するとセグメテーション違反がでます。何が間違っているんでしょうか？ #include<stdlib.h> struct node{ struct node *left,*right; int datum; }; struct bintree{ struct node *root; }; /*空木を作成*/ void InitTree(struct bintree *p) { p->root=NULL; } /*木全体を削除*/ void ClearTree(struct bintree *p) { struct bintree *q,*r; if(p->root!=NULL){ q->root=p->root->left; ClearTree(q); r->root=p->root->right; ClearTree(r); free(p->root); } } /*第二引数で指定された値が木の節点のラベルに存在すれば、その節点へのポインタを返す。なければ、NULLを返す。*/ struct node * SearchNode(struct bintree *p,int x) { struct bintree *q,*r; struct node *a=p->root; int cond=x-(a->datum); if(a==NULL) return NULL; else if(cond==0) return a; else if(cond<0){ q->root=p->root->left; SearchNode(q,x); } else{ r->root=p->root->right; SearchNode(r,x); } } /*第二引数で指定された値が木の節点のラベルに存在すれば、NULLを返す。なければ、追加して、新たに作成された節点へのポインタを返す。*/ struct node * InsertNode(struct bintree *p,int x) { struct bintree *q,*r; struct node *a=p->root; int cond=x-(a->datum); if(a==NULL){ a=(struct node *)malloc(sizeof(struct node)); a->datum=x; a->left=a->right=NULL; return a; } else if(cond==0) return NULL; else if(cond<0){ q->root=p->root->left; a->left=InsertNode(q,x); } else{ r->root=p->root->right; a->right=InsertNode(r,x); } } int main() { struct bintree *p; struct node *a; InitTree(p); a=InsertNode(p,5); InsertNode(p,3); InsertNode(p,0); InsertNode(p,10); SearchNode(p,5); ClearTree(p); return 0; }

  • 二分木のデータ入力について

    C言語についての質問です。 キューと再起関数を使って2分木にデータを入れようとしたところ、以下のようなエラーが発生いたしました。 ddd.c: 関数 ‘dequeue’ 内: ddd.c:80:9: 警告: 戻りでポインタからキャスト無しに整数を作成しています [-Wint-conversion] return x; ^ ddd.c: 関数 ‘growTree’ 内: ddd.c:100:14: エラー: assignment to expression with array type x->sentence = dequeue(); なんとか解消しようとするのですが、どうしてもエラーが増えるばかりで、うまくいきませんでした。 どの部分をどのように直せばいいのか大変お手数ですが、教えていただけると助かります。 よろしくお願いいたします。 以下が実行したプログラムになっております。 #include <stdio.h> #include <stdlib.h> #include <string.h> #define QUEUE_SIZE 100 /*キューの大きさ*/ /*配列でキューを表現する*/ int front, rear; char queue[3][50] = {"0b", "Ab", "Bb"}; char dequeue();/*キューからデータを取り出す*/ int next(int val);/*キューを配列で表現するとき、現在の次の配列のindexを返す*/ struct node{ char sentence[50];//値 struct node *left; //次のセルへのポインタ(左の子) struct node *right; //次のセルへのポインタ(右の子) }; int Gcount=0; void error(char *s);/*エラーを出力する*/ struct node* make_node();/*nodeをつくって返す*/ //void set_value_of_node(struct node* node,int a);/*nodeに値をセットする*/ struct node* growTree(int i, int k);/*深さiまで木を成長させ、そのルートを返す*/ void displayTree(struct node *node);/*node以下の部分木を表示する*/ int main(void){ struct node *root; int total=2 ; front = 0; rear = front + total + 1; root=growTree(total, 0); printf("\n\n\n前 順 表 示\n"); displayTree(root); return 0; } struct node* make_node(){/*nodeをつくって返す*/ struct node *p; if((p=(struct node*)malloc(sizeof(struct node ))) == NULL) error("メモリが足りません\n"); p->left =NULL; p->right =NULL; return(p); } //id set_value_of_node(struct node* node, int a)/*nodeに値をセットする*/ // //f(node == NULL)error("nodeが空です\n"); //ode->value=a; //rintf("%d ", node->value); // // void error(char *s){/*エラーを出力する*/ fprintf(stderr, s); exit(1); } /*キューからデータを取り出す*/ char dequeue(){ char *x; if(front == rear){ error("\nqueue is empty!!\n"); } x = queue[front]; front = next(front); return x; } /*キューを配列で表現するとき、現在の次の配列のindexを返す*/ int next(int val){ int next; next=(val+1)%QUEUE_SIZE; return(next); } struct node* growTree(int i, int k){/*深さiまで木を成長させ、そのルートを返す*/ /*課題1はここを書く*/ if(i == k) return NULL; k++; struct node *x; x = make_node(); x->sentence = dequeue(); x->left = growTree(i, k); x->right = growTree(i, k); return x; } void displayTree(struct node *node){/*node以下の部分木を表示する*/ /*課題2はここを書く*/ if(node == NULL) return; printf("%s\n", node->sentence); displayTree(node->left); displayTree(node->right); }

  • 二分探索木への挿入

    今学校で二分探索木を勉強しています。二分探索木に要素を挿入したいのですが、うまくいかないのでアドバイスをいただけないでしょうか。ファイル中の英文を単語に分けてその出現頻度をカウントするプログラムです。とりあえず二分探索木を作るところまではなんとか完成させたいです。 #include <stdio.h> #include <stdlib.h> #include<string.h> #include <ctype.h> typedef struct node Node; struct node{ char *word; int count; Node *left,*right; }; Node *root=NULL; Node *compose(FILE *fp); void inorder(Node *p); int main(int argc, char *argv[]) { FILE *fp; Node *new; fp=fopen(argv[1],"r"); if(fp==NULL){ puts("ファイルを開けません"); return(-1); } new=(Node *)malloc(sizeof(Node *)); new=compose(fp); inorder(new); return (0); } Node *compose(FILE *fp) { Node **p,*new; char buf[20]; p=&root; while(fscanf(fp,"%[-a-z-A-Z0-9_]",buf)!=EOF){ while(*p!=NULL){ (*p)->count=0;　　/*countを０で初期化したいけどwhileの外にこの1行を出すとエラーが出る*/ buf[0]=tolower(buf[0]); strdup(buf); if(strcasecmp(buf,(*p)->word)==0){　　　/*if文にしかはいらない…*/ (*p)->count++; printf("%d\n",(*p)->count); }else if(strcasecmp(buf,(*p)->word)<0){ p=&(*p)->left; }else{ p=&(*p)->right; } } new=(Node *)malloc(sizeof(Node *)); new->left=NULL; new->right=NULL; new->word=buf; *p=new; fscanf(fp,"%*[^-a-z-A-Z0-9_]"); } return(new); } void inorder(Node *p) { if(p==NULL) return; printf("%s",p->word); if(p->count!=0){ printf("%d",p->count); } inorder(p->right); inorder(p->left); }

  • 二進検索木

    下記のプラグラムで二進検索木を作りたいのですが、うまくいきません(２つまでしか保存ができない)。 たぶん、ポインタがおかしいと思うのですが・・・。お願いします。 入力 年齢 1 名前 a メアド a@ 年齢 2 名前 b メアド b@ 年齢 3 名前 c メアド c@ 年齢 -1 出力 ｂ 　× 　ｃ 　　× 　　× 歳 2 名前 b メアド b@ 歳 3 名前 c メアド c@ #include<stdio.h> #include<stdlib.h> struct node{ char *name; char *email; int age; struct node *left; struct node *right; }; void getline(char *s,int n){ int c; while(--n>0&&((c=getchar())!=EOF && c!='\n')) *s++=c; *s='\0'; } char* dupstr(char* strg){ char* newstr; newstr = (char*)malloc(sizeof(char)*strlen(strg)); strcpy(newstr,strg); return newstr; } struct node *new(int n,char *na,char *em){ struct node *p; p=malloc(sizeof(struct node)); p->age=n; p->name=na; p->email=em; p->left=NULL; p->right=NULL; return p; } void print(struct node *p){ if(p==NULL)return; else{ print(p->left); printf("\n歳:%d ", p->age); printf("\n名前:%s ", p->name); printf("\nメアド:%s ", p->email); print(p->right); } } void print_tree(struct node *p,int level){ int i; for(i=0;i<level;i++)printf(" "); if(p==NULL)printf("×\n"); else{ printf("%s\n",p->name); print_tree(p->left,level+1); print_tree(p->right,level+1); } } void *insert(struct node *p,int n,char *na,char *em){ int c; c=strcmp(p->name,na); if(c==0); else if(c>0){ if(p->left==NULL) {p->left=new(n,na,em); return p;} else insert(p->left,n,na,em); } else{ if(p->right==NULL){ p->right=new(n,na,em); return p;} else insert(p->right,n,na,em); } } main() { int age,g; char buf[80],a[80],b[80],*email,*name; struct node *root=NULL; g=1; printf("\n歳を入力:"); getline(buf,sizeof(buf)); printf("\n名前入力:"); getline(a,sizeof(a)); name=dupstr(a); age=atoi(dupstr(buf)); printf("\nメアド入力:"); getline(b,sizeof(b)); email=dupstr(b); root=new(age,name,email); while(g==1){ printf("\n歳を入力:"); getline(buf,sizeof(buf)); age=atoi(dupstr(buf)); if(age==-1) break; printf("\n名前入力:"); getline(a,sizeof(a)); name=dupstr(a); printf("\nメアド入力:"); getline(b,sizeof(b)); email=dupstr(b); root=insert(root,age,name,email); } print_tree(root,0); print(root); }

  • (構造体)双方向連結リストの作成！

    ダミーノードを先頭に、双方向連結リストを作成したいのですがなかなかうまくできません。とりあえず、ダミーノード無しのものはなんとか出来ましたが、循環連結がうまくいっていない次第です。 どうかお力添え願います。 #include<stdio.h> #include<malloc.h> #include<process.h> typedef struct node{ struct node *left; char name[20]; int age; struct node *right; }NODE; NODE *memalloc(void); void main(void) { NODE *head, *tail, *p; tail = NULL; while(p = memalloc(), printf("名前 年齢入力(Ctrl + Zで終了)＞"), scanf("%s %d", p -> name, &p -> age) != EOF){ p -> left = tail; tail = p; } p = tail; head = NULL; while(p != NULL){ p -> right = head; head = p; p = p -> left; } head -> left = tail; p = head; printf("リスト表示\n"); while(p != NULL){ printf("名前:%20s 年齢:%5d\n", p -> name, p -> age); p = p -> right; } } NODE *memalloc(void) { NODE *ptr; if((ptr = (NODE *)malloc(sizeof(NODE))) != NULL){ return ptr; } printf("\n動的メモリ割当に失敗しました。\n"); exit(1); return 0; }

  • データ数を増やすとエラーになる

    typedef struct DATA{ int data; struct DATA *left; struct DATA *right; }node,*tree; tree makenode(int data) { 　　　　tree q; 　　　　if((q=(tree)malloc(sizeof(node)))==NULL){ 　　　　　　　printf("メモリ割り当てエラー\n"); 　　　　　　　exit(-1); 　　　　} q->left=NULL; q->right=NULL; q->data=data; 　　return q; } をつくり、for文でまわしながら、処理を行うプログラムにしたいんですが、まわす回数が４までだときちんと動くのですが５以上にすると エラーになってしまいます。なぜエラーになるか全くわかりません。 わかる方教えてください。お願いします。

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する