再帰処理について

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

No.2 ベストアンサー 回答者： a-kuma 回答日時： 2001/12/08 12:57

「再帰だ」ってるのに、あほうですね、私。

枝の処理を忘れてました。

それを直せたのだから、検索も簡単でしょう。

TraverseTree() が全てのノードを処理しているのに対し、検索はひとつでも
見つかれば、１を返せばよいのですから。

(1) 自分がその値であるか？　そうなら、１を返しておしまい
(2) 無ければ、左にあるか？　あれば、１を返しておしまい
(3) 無ければ、右にあるか？　あれば、１を返しておしまい
(4) どこにもないので、０を返す

蛇足かもしれませんが、

> 　　　　} else if (ExistTest(ptr->left, searchdata)) {

と書いたのは

} else if (ExistTest(ptr->left, searchdata) != 0) {

と全く同じことです。

No.1 回答者： a-kuma 回答日時： 2001/12/07 11:01

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;
　　　　}
　　}
}

＃ コンパイルや動作確認をしたわけではないので、自信無しです

この回答への補足

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

入れ替えとトラバーサルを行えばできました。
ありがとうございます。
検索は、奮闘中です.

補足日時：2001/12/08 01:22

この回答へのお礼

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

お礼日時：2001/12/08 01:13