再帰処理について

前へ 次へ
このQ&Aのポイント
  • 再帰処理を用いた二分木の生成とトラバーサル
  • 全ての節の子を交換する再帰的な処理方法
  • 指定した整数値の存在判定を行う関数の作成
回答を見る
  • ベストアンサー

再帰処理について

以下のソースコードを用いて二分木を生成して、それをトラバーサルすると 昇順に表示されますが！ これを、用いて全ての節の子を（左の子と右の子）を交換する。 関数定義 void ReverseTree( struct BTREE *ptr); を再帰的呼び出しによって実現してのですが！ どう考えればよいのでしょうか？ さらに、２分木の生成後に入力した整数値がリスト中にあるかどうかを 判定し、（存在すれば１、存在しなければ、0を関数値とする） 関数定義　int　ExistTest(struct BTREE *ptr, searchdata); を作成し動作を確認したいのですが！ ご教授して下さい。お願いします.

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

  • ベストアンサー
  • a-kuma
  • ベストアンサー率50% (1122/2211)
回答No.2

「再帰だ」ってるのに、あほうですね、私。枝の処理を忘れてました。 それを直せたのだから、検索も簡単でしょう。 TraverseTree() が全てのノードを処理しているのに対し、検索はひとつでも 見つかれば、１を返せばよいのですから。 (1) 自分がその値であるか？　そうなら、１を返しておしまい (2) 無ければ、左にあるか？　あれば、１を返しておしまい (3) 無ければ、右にあるか？　あれば、１を返しておしまい (4) どこにもないので、０を返す 蛇足かもしれませんが、 > 　　　　} else if (ExistTest(ptr->left, searchdata)) { と書いたのは } else if (ExistTest(ptr->left, searchdata) != 0) { と全く同じことです。

その他の回答 (1)

  • a-kuma
  • ベストアンサー率50% (1122/2211)
回答No.1

TraverseTree() をじっと見れば、さほど難しくないと思うのだけどなあ。 > 全ての節の子を（左の子と右の子）を交換する。 void ReverseTree(struct BTREE *ptr) { 　　if (ptr == NULL) { 　　　　return; 　　} else { 　　　　struct BTREE* tmp; 　　　　tmp = ptr->left; 　　　　ptr->left = ptr->right; 　　　　ptr->right = tmp; 　　} } > ２分木の生成後に入力した整数値がリスト中にあるかどうかを int ExistTest(struct BTREE *ptr, int searchdata) { 　　if (ptr == NULL) { 　　　　return 0; 　　} else { 　　　　if (ptr->data == searchdata) { 　　　　　　return 1; 　　　　} else if (ExistTest(ptr->left, searchdata)) { 　　　　　　return 1; 　　　　} else if (ExistTest(ptr->right, searchdata)) { 　　　　　　return 1; 　　　　} else { 　　　　　　return 0; 　　　　} 　　} } ＃ コンパイルや動作確認をしたわけではないので、自信無しです

naguma
質問者

お礼

入れ替えはワークを使用して入れ替えるのですが、 全ての節を行うには、という点がわかりません。

naguma
質問者

補足

void ReverseTree (struct BTREE *ptr) { struct BTREE *workp; if(ptr == NULL){ return; }else{ workp = ptr->left; ptr->left = ptr->right; ptr->right = workp; ReverseTree (ptr->left); ReverseTree (ptr->right); } } 入れ替えとトラバーサルを行えばできました。 ありがとうございます。 検索は、奮闘中です.

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

関連するQ&A

  • リストに整数値があるか判定するプログラム

    ↓のプログラムのint ExistTest(struct BTREE *ptr, int searchdata)を、2分木の生成後に入力した整数値がリストの中にあるかどうかを判定するプログラムにしたいのですが、うまくいきません(>_<) 入力された整数値があれば1、なければ0を返したいのですが。。 どなたかお願いしますm(__)m #include <stdio.h> #include <stdlib.h> struct BTREE {int data; struct BTREE *left; struct BTREE *right;}; void AddLeaf(struct BTREE **ptr, int newdata); void TraverseTree (struct BTREE *ptr); int ExistTest(struct BTREE *ptr, int searchdata); int ExistTest(struct BTREE *ptr, int searchdata){ if (ptr->data == searchdata){ return 1; } else{ ExistTest(ptr->right, searchdata); } } void AddLeaf(struct BTREE **ptr, int newdata){ if (*ptr == NULL){ *ptr = (struct BTREE *)malloc(sizeof(struct BTREE)); (*ptr)->data = newdata; (*ptr)->left = NULL; (*ptr)->right = NULL; } else if (newdata < (*ptr)->data){ AddLeaf(&(*ptr)->left, newdata); } else{ AddLeaf(&(*ptr)->right, newdata); } } void TraverseTree(struct BTREE *ptr){ if (ptr == NULL){ return; } else{ TraverseTree(ptr->left); printf("%3d", ptr->data); TraverseTree(ptr->right); } } int main(void){ struct BTREE *root = NULL; int newdata; int searchdata; while(1){ printf("data > "); scanf("%d", &newdata); if (newdata < 0)break; AddLeaf(&root, newdata); TraverseTree(root); putchar('\n'); } /*ExistTest*/ /* printf("num? : "); scanf("%d", &searchdata); ExistTest(root ,searchdata); */ return 0; }

  • 今、構造体の勉強をしているのですが…

    初心者です。 今、木構造を生成するプログラムを勉強しております。 参考書のプログラムの中に 新たなノードを生成する関数。 void AddLeaf(struct BTREE **ptr,int newdata) とあるのですが、 struct BTREE **ptr って何ですか？？ 特に*が二つあるところがわからないです。 *(*ptr)となっているから ptrのアドレスの指す実体？？ って事なのでしょうか？？ 少々混乱気味です(^^;) どなたか助言お願いします

  • 再帰呼び出しについて

    C言語のプログラムについてです。 テキストからランダムに並べられたアルファベットを順番にひっぱってきて、 二分木の構造にアルファベットをアルファベット順に格納していき、その順番で表示するプログラムなのですが、 typedef struct rec{ char word[1]; struct rec *left; struct rec *right; }rec; という構造体が定義されており、 二分木構造に（なるように）アルファベットを順番に格納していったあと、 それをアルファベット順に表示していく関数が以下の関数hyoujiなのですが、 （二分木を生成する際にmallocを使用しているので、freeがありますが今回は無視してください。） void hyouji(rec *top){ if(top!= NULL){ hyouji(top->left); printf("%s\n",top->word); hyouji(top->right); free(top); } } この再帰呼び出しの動きがよくわかりません。（つまりはhyoujiの関数の動きがわかりません。） *topは二分探索木の一番上のアドレスを示しています。 wordにアルファベットが格納されています。 たとえば、下のように格納されていたらどのようにhyouji関数は動くのでしょうか。 順番に説明していっていただけたらありがたいです。 （ちなみにプログラム的に下の例のように格納されていきます。 まずtopを生成して、テキストファイルの先頭のアルファベットを入れて、そこから順に 格納していくので、topがaとは限りません。） ........................[b] ....................／...＼ .................[a]........[e] ...........................／...＼ .......................[c].........[g]

  • 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

  • 関数の再帰処理

    1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657... という数列（フィボナ数列）を再帰処理でだしたいのですが・・・・・ include <stdio.h> int function( int ); int main( void ){ int n; do { printf( "0 以上の整数値を入力して下さい→ " ); scanf( "%d", &n ); }while ( n < 0 ); printf( "計算結果： %d\n", function( n ) ); getchar(); getchar(); return 0; } int function( int n ){ //フィボナの処理（function）の再帰呼び出しによる } function内に再帰処理を用いてprintf( "計算結果： %d\n", function( n ) );で画面出力したいのですが・・・・・・。

  • 再帰処理　変換

    初歩的で申し訳ないのですが、10進数を2進数に変換して表示する関数dt(n)を再帰的に定義するプログラムを作ってみたのですがつまってしまいました。以下、考えたコード文です。 #include <stdio.h> /*****dt*******/ long dt(int n) { 　　　　 if(n == 1) 　　　　　　　　　printf("1"); 　　　　 else 　　　　　　　　　dt(n % 2); 　　　　　　　　　printf("%d" , n); } /****** Main ******/ void main(void) { 　　　　 dt(10); } どこが間違えているかご指摘頂けたら有難いです。

  • プログラムについて

    ２分木のプログラムなのですが、関数部分を作るという学校の問題なのですが、習いはじめで構造体など殆ど分かりません。ヒントでも良いので教えてください。合っていないとは思いますが、一応初期化の部分と、終了の部分、ノードの追加部分は考えました。 typedef struct t_Btree { struct t_Btree *left; struct t_Btree *right; int data; } Btree; // Btreeの初期化 void Btree_ini(Btree *a, int b) { a->left=NULL; a->right=NULL; a->data=b; a = (Btree *)malloc(sizeof(Btree)); } // 領域の開放 void Btree_end(Btree *a, int b) { free(a); } // 新しいノードを追加 void Btree_ad(Btree *a, int b) { Btree_tansaku(a, b); a = (Btree *)malloc(sizeof(Btree)); self->left_ = NULL; self->right_ = NULL; self->data_ = b; } // 探索し、bに一致するデータのポインタを返す void *Btree_tansaku(const Btree *a, int b) { } // aのデータのみを出力 void Btree_pri(const Btree *a) { } // 全体を出力 void Btree_tpri(const Btree *a) { } int main(void) { int i; int d[] = {7,3,6,4,1,9,2,0,10,8}; Btree bt; Btree_ini(&bt,5); for(i=0;i<10;i++) Btree_ad(&bt,x[i]); Btree_tpri(&bt); Btree_end(&b); return 0; } おねがいします。

  • 再帰呼び出しについて（基本）

    #include <stdio.h> void dan(int i); void kuku(void); void dan(int i) { int j; for (j = 1; j <= 9; j++) printf("%3d", i*j); putchar('\n'); } void kuku(void) { int i; for (i = 1; i <= 9; i++) dan(i); } int main(void) { kuku( ); return(0); } というプログラムがあるのですが、danとkukuを再帰呼び出しにしたいのですが、再帰の仕方がまったく分かりません。 知り合いに聞くと、両関数の引数を１つずつ増やすとよいと言われたのですが、手をつけられない状態です。 よろしくご教授お願いします。

  • Ｃ言語 再帰呼びだし

    Ｃ言語 再帰呼びだし 問題が解けません。もしよろしければご指導お願いします。 フィボナッチ数を求めるプログラミングを作成せよ。 非負の整数ｎに対するフィボナッチ数Ｆｎは以下のように再帰的に定義される。 Ｆｎ＝０ （ｎ＝０の時） Ｆｎ＝１ （ｎ＝１の時） Ｆｎ＝Ｆ(ｎ-1)+F(n-2) (n>1の時) ・関数int fibo(int n)を作成し、関数mainで、複数のnに対して関数fiboを呼びだし、その結果を表示せよ。 ・関数fiboは、再帰的にfiboを呼びだすようにせよ。 よろしくお願いします。

  • Ｃ言語で、再帰呼び出しを使用せずに、文字列"(12 + 3) * (

    Ｃ言語で、再帰呼び出しを使用せずに、文字列"(12 + 3) * ( 3 * (4 + 5 ))"を、優先順位が低い順に二分木に入れる関数を作成したいのですが・・・。 char str[15] = ""(12 + 3) * ( 3 * (4 + 5 ))";なら char n[100];に n[0] = '*' n[1] = '+' n[2] = '*' n[3] = 12 n[4] = 3 n[5] = 3 n[6] = '+' n[7] = \0 n[8] = \0 n[9] = \0 n[10] = \0 n[11] = \0 n[12] = \0 n[13] = 4 n[14] = 5 （n[15] 以降は\0が格納されています。） というように入れたいのですが関数からその関数を呼び出す再帰を使わずに作成する方法がわかりません。 再帰を使用しなければかなり処理が複雑になるような気がしますがどなたか詳しい方よろしくお願いします。 言語はＣ言語です。

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

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

質問する