• 締切済み

２分探索木の高さを求めるプログラムの質問です。

２分探索木の高さを求めるプログラムを作成しているのですが、 下に書いたプログラムだと上手くいきません・・。 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; } } どこがおかしいのでしょう。教えてください。 よろしくお願いします。

みんなの回答

回答No.2

深さを加算していない。 ノードの終端は必ずNULLなので0が返り、 それをlh、rhに代入してるだけなので いつまでたっても０のまま。 +1すればいけるとおもうよ。 lh=compute_height(p->left)+1; rh=compute_height(p->right)+1;

362696
質問者

お礼

ご回答ありがとうございます！ 考えが足りなかったようです（汗 無事お二人のおかげで上手くいけました。 親切に教えてくださってありがとうございます！！

  • mtaka2
  • ベストアンサー率73% (867/1179)
回答No.1

あるノードの「高さ」を求めるには、「左右の子ノードの高さ(の高い方)」に、自身のノード分の1を足さないといけません。 あとは、変数Maxは使ってないので不要ですので、 --- if(lh > rh){ return Max=lh; } else{ return Max=rh; } --- この部分を --- if(lh > rh){ return lh+1; } else{ return rh+1; } --- でいけるかと思います。

362696
質問者

お礼

ご回答ありがとうございます！ なるほど・・・言われてみれば（汗 Ｃ言語でいつもこういう感じなんです。 分かりやすいご回答ありがとうございました！

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

関連するQ&A

  • 多分探索木の高さを測定する関数について

    今、多分探索木の高さを測定する関数を作成していますが、行き詰ってしまいました。 二分探索木の深さを求める関数を改良すればよろしいと思ったんですが。 どうもうまくいきません。助言お願いします。 以下、二分探索木の高さを求める関数を貼っときます。 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

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

    ２分探索木のプログラムを作っているのですが、実行するとセグメテーション違反がでます。何が間違っているんでしょうか？ #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; }

  • 二分探索木への挿入

    今学校で二分探索木を勉強しています。二分探索木に要素を挿入したいのですが、うまくいかないのでアドバイスをいただけないでしょうか。ファイル中の英文を単語に分けてその出現頻度をカウントするプログラムです。とりあえず二分探索木を作るところまではなんとか完成させたいです。 #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言語で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言語　二分木探索

    今、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); }

  • 二分探索木の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
  • 二分木のなぞり

    ノードにデータが与えられているものとして帰りがけで二分木をなぞり、ノードに立ち寄った順にデータを書き出すときにそのデータが大きい順に並んでいるか判定するプログラムを作りたいです。 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;を入れればよいのか、また根本的に考え方がおかしいなら方針を教えていただきたいです。よろしくお願いします。

  • 二分探索木

    下のプログラムはコンパイルはできたのですが、実行すると「セグメンテーション違反です」とでました。デバッガをしてみたら、 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; }

  • 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言語についての質問です。 キューと再起関数を使って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); }

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

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

質問する