- 締切済み
多分探索木の高さを測定する関数について
今、多分探索木の高さを測定する関数を作成していますが、行き詰ってしまいました。 二分探索木の深さを求める関数を改良すればよろしいと思ったんですが。 どうもうまくいきません。助言お願いします。 以下、二分探索木の高さを求める関数を貼っときます。 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#
- 回答数1
- ありがとう数0
- みんなの回答 （1）
- 専門家の回答
みんなの回答
- Tacosan
- ベストアンサー率23% (3656/15482)
そもそも「多分探索木の高さ」はどのように定義されているのですか? そして, どのように考えどのような関数を作ってどう困っているのですか?
関連する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#
- 多分探索木の昇順出力
多分探索木の昇順出力する。関数を作っています。以下の関数が、多分木を出力関数ですが 途中でセグメントエラーが起きてしまいます。 void out_MS(NODE *p){ int i,n=0 ; for(i = 0; i <= p->nkeys; ++i) if (p->refs[i] != NULL) out_MS(p->refs[i]) ; while(p->keys[n+1]!='\0'){ printf("No:%3d \"%s\"\n",count,p->keys[n]) ; count++; n++; } } この、多分木に使われている、構造体は以下のとおりです #define KK 16 typedef struct node{ // 多分探索木、B(B*)木構造体 char *keys[KK] ; // キー配列 int nkeys ; // キーの個数(実際の) struct node *refs[KK + 1] ; // 子への参照欄 } NODE ; この構造体に以下の関数で、10万要素の単語（ランダム）に追加していきます。 int add(NODE *root, char *inv) { NODE *now , // 当該節 *prnt ; // nowの親節 int pos ; // 節内のキーの追加位置 prnt = now = root ; while(now != NULL) { // キーの探索 pos = binsearch(now->keys, now->nkeys, inv) ; // 二分探索 if (pos < now->nkeys && strcmp(inv,now->keys[pos])==0) // 探索値はある return FLS ; // 追加の必要なし if (now->nkeys == KK) { // 当該節に無い、節内に空きが無い prnt = now ; now = now->refs[pos] ; // 子の節へ }else if (pos <= now->nkeys) // 当該節に無い－追加位置が範囲内 break ; } if (now != NULL) // 当該節は在る store_key(now, inv, pos, &(now->nkeys)) ; // 当該節にキーを追加格納 else { // 当該節は無い－新規生成 if (now != root) { // nowは根ではない now = set_key(KK, inv) ; // キーを新節に格納 prnt->refs[pos] = now ; // 親節の参照欄に新節の番地を格納 }else return FLS ; } return 1 ; } 上記の関数で使われている、store_key set_key binserch の関数は以下のとおりです void store_key(NODE *trgt, char *inv, int pos, int *nkeys) { if (trgt->keys[pos] == INTV) // 当該位置は空 trgt->keys[pos] = strdup(inv) ; // 当該位置に格納 else { // 当該位置に入っている shift_element(trgt, 'R', pos, *nkeys) ; // 要素を移動 trgt->keys[pos] = strdup(inv) ; // 当該位置に格納 } ++*nkeys ; return ; } int binsearch(char *array[], int size, char *inv){ // 二分探索 int mid, // 当該位置 low, // 探索範囲の下限 high ; // 探索範囲の下限 if (size == 0) // キーは格納されていない return 0 ; if (strcmp(inv,array[0])<0) // 探索範囲以下 return 0 ; if (0 < strcmp(inv,array[size - 1] )) // 探索範囲以上 return size ; low = 0 ; // 下限設定 high= size - 1 ; // 上限設定 while(0 <= high - low) { // 二分探索本体 mid = (high + low) >> 1 ; // 中間位置を調べる if (strcmp(inv,array[mid])==0) // 入力値が一致したとき return mid ; if (strcmp(inv,array[mid])<0) // 入力値が小さいとき high = mid - 1; else // 入力値が大きいとき low = mid + 1 ; } return low ; } NODE *set_key(int size, char *key) { NODE *new ; new = crt_node(size) ; // 節の生成 new->keys[0] = strdup(key) ; // 配列の先頭に入力値を格納 new->nkeys = 1 ; // 節内の実際の要素数 return new ; } ぜひ、お力をお貸しください。よろしくお願いします。
- 締切済み
- C・C++・C#
- ポインタ型の関数のコンパイル
Cについて勉強中の一回生です 今回初めてポインタ型の関数を作ったのですが コンパイルができません エラー内容は warning: assignment makes pointer from integer without a cast warning: assignment makes pointer from integer without a cast でした。 型があってないっぽいのですがどうしてできないのですか？ struct node { int key; struct node *parent,*left,*right; }; struct node *memvber_recursive(int key,struct node *root){ struct node *x; if(root->key == 0){ printf("ありません\n",root->key); return NULL; } else if(root->key == key) printf("あります\n",root->key); else if(root->key > key) x = member_recursive(key,root->left); else x = member_recursive(key,root->right); return x; } 課題の内容は再帰を使った二分木の探索です 引数は、探索する要素の値（キー）と２分探索木の根のポインタ 戻り値は要素が見つかればその点を示すポインタを、見つからなければNULLを返します あと関数の前にアスタリスクがつく意味がわかりません ポインタを返すと言う意味ですか？ 先生が例文として与えてくれたのですが こんな形は教科書にのっておらず困っています よかったら教えて下さい 宜しくお願いします。
- ベストアンサー
- 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#
- 二分探索木の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)の条件もこれでいいのか…。 いろいろやってみたのですが行き詰まりました。 どうか、更にヒントを下さい。お願いします。
- ベストアンサー
- Java
- C言語 二分木探索
今、int型の二分木にデータを追加する関数(引数は二分木へのポインタと追加する値、追加されたノードへのポインタを返す)をつくろうとしてます。 以前リストにデータを追加する関数をつくったのでそれを変更してつくろうとしているのですが途中までいってつまってしまいました。 つくりかたを教えてください。 よろしくお願いします！ struct BinaryTreeNode{ int data; struct BinaryTreeNode *l_next; struct BinaryTreeNode *r_next; }; struct BinaryTree{ int node_num; struct BinaryTreeNode *root; }; BinaryTreeNode *BinaryTreeNodeAlloc(void) { BinaryTreeNode *node; node = (BinaryTreeNode *)malloc(sizeof(BinaryTreeNode)); if (node == NULL) { return (NULL); } node->l_next = NULL; node->r_next = NULL; return (node); } BinaryTreeNode *BinaryTreeDataAdd(BinaryTree *list, int x) { BinaryTreeNode *ptr; BinaryTreeNode *prev; BinaryTreeNode *new_node; ptr = list->root; prev = NULL; while (ptr) { ←？？ if (ptr->data < x) { prev = ptr; ptr = ptr->next; } else if (ptr->data == x) { return (NULL); } else { new_node = BinaryTreeNodeAlloc(); if (new_node == NULL) { exit (0); ←？？ } new_node->data = x; new_node->next = ptr; if (prev != NULL) { prev->next = new_node; } else { list->head = new_node; } list->node_num++; return (new_node); } } new_node = BinaryTreeNodeAlloc(); if (new_node == NULL) { exit (0); } new_node->data = x; new_node->r_next = NULL; new_node->l_next = NULL; if (prev != NULL) { prev->next = new_node; } else { list->head = new_node; } list->node_num++; return (new_node); }
- 締切済み
- C・C++・C#
- 二分探索木
下のプログラムはコンパイルはできたのですが、実行すると「セグメンテーション違反です」とでました。デバッガをしてみたら、 Program received signal SIGSEGV, Segmentation fault. 0x080483e8 in inorder (root=0x0) at nibun.c:12 12 inorder(root->llink); と表示されましたが解決方法が分かりません。どのように直せば、エラーを出さずに実行できるようになるか教えてください。 #include<stdio.h> #include<stdlib.h> typedef struct node *NodeP; typedef struct node { int data; NodeP llink, rlink; } Node; void inorder(NodeP root) { inorder(root->llink); printf(" %d", root->data); inorder(root->rlink); } NodeP newNode(int val) { NodeP newp = (NodeP) malloc (sizeof(Node)); newp->data = val; newp->llink = NULL; newp->rlink = NULL; return newp; } void insert(NodeP *root, int val){ NodeP curr,prev; if(*root == NULL) *root = newNode(val); else{ curr = *root; do{ prev = curr; if ( val < curr->data) curr = curr->llink; else if ( val > curr->data) curr = curr->rlink; else return; }while(curr!= NULL); if(val > prev->data){ prev->llink = newNode(val); } else{ prev->rlink = newNode(val); } } } NodeP createBSTree(void){ int i,n,val; NodeP root=NULL; printf("Number of Nodes:"); scanf("%d",&n); for (i=1;i<=n;i++){ printf("Node[%d]: ",i); scanf("%d",&val); insert(&root,val); } return root; } int main(){ NodeP root=NULL; root = createBSTree(); inorder(root); printf("\n"); return 0; }
- ベストアンサー
- C・C++・C#
- 二分木のデータ入力について
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); }
- 締切済み
- 情報工学
- 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#
