二分探索木のheightを見つけるアルゴリズムについて
- 前回の質問で頂いた回答を元に、私が作成したアルゴリズムでは正しく動作していないようです。
- アルゴリズムの問題点は、左と右の値を比較しているため、入力値によって偶然に正しく動作してしまっていたということです。
- 正しいアルゴリズムでは、左と右の高さを比較する必要があります。しかし、どうしても行き詰まってしまいました。ヒントをお願いします。
- ベストアンサー
二分探索木のheightを見つけるアルゴリズム2
誠に申し訳ありません。 前回下記のとおり質問して、 二分探索木のheight(高さ?)を見つけるアルゴリズム http://www.okweb.ne.jp/kotaeru.php3?q=710354 丁寧な回答を頂き、自分では解決したと思い、 お礼も差し上げたのですが 私のメソッドは正しく動いていないようです。 どうやら私が間違って解釈してしまったようです。 public int height() { return height(root, 0); } public int height(IntBSTNode p, int h) { if (p != null && p.right != null && p.left != null) { if (p.left.key < p.right.key) return height(p.right, h+1); else return height(p.left, h+1); } return h; } 何を思ったのか、 if (p.left.key < p.right.key)では 左と右の「値」を比較しています。 なので入力した値によって「たまたま」動いてました。 本当は左と右の「height」を比較しなければならなかったのに…。 if (p != null && p.right != null && p.left != null)の条件もこれでいいのか…。 いろいろやってみたのですが行き詰まりました。 どうか、更にヒントを下さい。お願いします。
- ginkgo
- お礼率94% (132/139)
- Java
- 回答数1
- ありがとう数2
- みんなの回答 （1）
- 専門家の回答
質問者が選んだベストアンサー
再帰処理ですね。最近やってないからなあ・・・ public int height(IntBSTNode p, int h) { int hl, hr; if(p = NULL) { return(h); } hl = height(p.left, h); hr = height(p.right, h); if (hl > hr) { return(hl+1); } else { return(hr+1); } } ・自分自身がNULLだったら、カウントアップせずそのまま返る。 ・左右それぞれにたどっていき、大きい（深い）ほうを採用し、+1して返る 呼ぶときに+1するのではなく、返るときに+1するようにしています（NULLにあたったら+1しないため）
関連するQ&A
- ２分探索木の高さを求めるプログラムの質問です。
２分探索木の高さを求めるプログラムを作成しているのですが、 下に書いたプログラムだと上手くいきません・・。 int compute_height(struct BST_Node *p){ int lh=0, rh=0, Max; if(p==NULL){ return 0; } lh=compute_height(p->left); rh=compute_height(p->right); if(lh > rh){ return Max=lh; } else{ return Max=rh; } } どこがおかしいのでしょう。教えてください。 よろしくお願いします。
- 締切済み
- C・C++・C#
- 多分探索木の高さを測定する関数について
今、多分探索木の高さを測定する関数を作成していますが、行き詰ってしまいました。 二分探索木の深さを求める関数を改良すればよろしいと思ったんですが。 どうもうまくいきません。助言お願いします。 以下、二分探索木の高さを求める関数を貼っときます。 int compute_height(NODE *root){ int lh=0, rh=0, Max; if(root==NULL){ return 0; } lh=compute_height(root->left)+1; rh=compute_height(root->right)+1; if(lh > rh){ return Max=lh; }else{ return Max=rh; } } 多分木探索の構造体定義は以下のようです typedef struct node{ int key[16]; //キー配列 int nkeys ; // キーの個数(実際の) struct node *refs[17] ; // 子への参照欄 } NODE
- 締切済み
- C・C++・C#
- 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の条件を変えればいいのかと思い、いろいろ試してみたのですが、 左部分木には左側にしか葉がなく、右部分木には右にしか葉がないようなものしかできませんでした もう何時間も悩んだのですが自分の知識では手づまりです どうかよろしくお願いします。
- ベストアンサー
- C・C++・C#
- 二分探索木のプログラム
２分探索木のプログラムを作っているのですが、実行するとセグメテーション違反がでます。何が間違っているんでしょうか？ #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・C++・C#
- 二分探索木への挿入
今学校で二分探索木を勉強しています。二分探索木に要素を挿入したいのですが、うまくいかないのでアドバイスをいただけないでしょうか。ファイル中の英文を単語に分けてその出現頻度をカウントするプログラムです。とりあえず二分探索木を作るところまではなんとか完成させたいです。 #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); }
- ベストアンサー
- C・C++・C#
- ２分探索木、挿入
行き詰まりました。 ２分探索木の要素挿入です。 何がいけないのでしょうか？？ 思うように動作しません。 ルートはどうやら設定されるようですが、 その他のデータがうまく挿入されません。 たぶんポインタの使い方がなってないようなのですが、 どこをどうしていいか分からないのでどなたか教えてください。 (インデントくずれました・・・見にくくてすみません) データ構造は以下の通りです。 node{ key //item template ですがint とみなしてください。 node *left //左の子へのポインタ node *right //右の子へのポインタ } root{ node *root //ルートへのポインタ } //ここからソース（多少省略してます。） insert(const K & newKey) { node<K> *temp; if(empty()){//ルートの設定。 temp = new node<K>(newKey, NULL,NULL); root = temp; }else{//木が既存する場合 insertItem(root, newKey); } } insertItem(node<K> *fact, const K & newKey) { node<K> *temp,test; if(fact == NULL){//要素挿入 temp = new node<K>(newKey,NULL,NULL); fact = temp; test = *fact; }else{//挿入場所探索 test=*fact; if(test.key == newKey){ cout<<"same key"; }else if(test.key > newKey){ insertItem(test.left, newKey); }else{ insertItem(test.right, newKey); } } }
- ベストアンサー
- C・C++・C#
- C言語 2分木探索について質問です
Ｃ言語初心者です。 2分木構造体 struct node{ int data; Tree left_subtree; Tree right_subtree; } を上記のように定義した場合、 2分木の根節点のポインタ struct node *Tree を引数として与えられたとき、 2分木内の節点に保持された整数データの総和を戻り値として返す関数 int sum_data(Tree t);を再帰呼び出しで作成してみたのですが、正しいでしょうか？ ■2分木内の節点に保持された整数データの総和を戻り値として返す関数 int sum_data(Tree t) { // 左分木、右分木のどちらも存在しなければ根節点の値を返す if ((t->left_subtree == NULL) && (t->right_subtree == NULL)) { return t->data; } else// どちらか存在していれば再帰呼び出しする { return (t->data + sum_data(t->left_subtree) + sum_data(t->right_subtree)) } } ご指摘ありましたら、お願いしますm(_ _)m
- ベストアンサー
- C・C++・C#
- 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; }
- ベストアンサー
- C・C++・C#
- 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・C++・C#
- 二分木のなぞり
ノードにデータが与えられているものとして帰りがけで二分木をなぞり、ノードに立ち寄った順にデータを書き出すときにそのデータが大きい順に並んでいるか判定するプログラムを作りたいです。 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;を入れればよいのか、また根本的に考え方がおかしいなら方針を教えていただきたいです。よろしくお願いします。
- ベストアンサー
- C・C++・C#
お礼
はい、ちゃんと動作していてます! 呼ぶときではなく、返るときに+1するのですね。 それとよくよく考えると、呼び出されたときにnullならそのまま返ってくるので p.leftとp.rightがnullかどうかなんて判断しなくてもよかったんですね。 とても勉強になりました。 本当に、本当に助かりました。 ありがとうございました!