小さい順に出力したい

[jacks_pow]

はじめまして。
以下のプログラムはツリーを考えるものです。

コード:

#include<stdio.h>
#include<stdlib.h>

/*構造体を宣言する*/
struct node
{
	int data;
	struct node *left;
	struct node *right;
};

void print_tree(struct node *p);

int main(void)
{
	/*変数宣言*/
	struct node *root,*tmp,*p;
	int d,flg;
	
	/*ツリーを初期化する*/
	root = NULL;
	
	/*最初のデータを入力する*/
	printf("Input Number : ");
	scanf("%d",&d);
	
	while(d > 0)
	{
		/*要素を作成する*/
		tmp = malloc(sizeof(struct node));
		tmp->data = d;
		tmp->left = NULL;
		tmp->right = NULL;
		
		if(root == NULL)
		{
			/*ルートにくっつける*/
			root = tmp;
		}
		else
		{
			p=root;
			flg = 0;
			
			while(flg == 0)
			{
				if(tmp->data < p->data)
				{
					if(p->left == NULL)
					{
						/*	左にくっつける*/
						printf("%dの左につけた\n",p->data);
						p->left = tmp;
						flg = 1;
					}
					else
					{
						p = p->left;
					}	
				}
					else
					{
						if(p->right == NULL)
						{
							printf("%dの右につけた\n",p->data);
							p->right = tmp;
							flg =1;
						}
						else
						{
							p = p->right;
						}
					}
				}
			}
	
	/*次のデータを入力する*/
	printf("Input Number : ");
	scanf("%d", &d);
	
	}
	
	/*画面に出力する*/
	printf("Result : ");
	print_tree(root);
	printf("\n");
	
	return 0;
}
		

/*ツリーを出力する関数*/
void print_tree(struct node *p)
{
	if(p != NULL)
	{
		/*自分自身を出力する*/
		printf("%d",p->data);
	
		/*左側を出力する*/
		print_tree(p->left);
		
		/*右側を出力する*/
		print_tree(p->right);
	}
}

これでは、通りかけ順になってしまいます。
これを行きがけ順にしたいです。よろしくお願いします。

[hoge]

エラーでます。関数化のendoさんと同一人物ですよね？

[超初級者]

疑問点が２つ。

１）提示のコードは、行きがけであるように見えます。

２）小さい順に出力したい、と、行きがけにしたい、とは矛盾しているように思います。
小さい順に出力したいならば、通りがけではないでしょうか。

[maxweber]

コンパイル通りますでしょうか。
VC 2013 Communityではコンパイルエラーとなります。

[jacks_pow]

すみません。小さい順でなく左から出力される行きがけ順にしたいです。
あと、コンパイルは通ります。

[jacks_pow]

取り敢えず、行きがけ順を通りがけ順にしたいです。

[box]

これでは、通りかけ順になってしまいます。
これを行きがけ順にしたいです。よろしくお願いします。

と言ってみたり

取り敢えず、行きがけ順を通りがけ順にしたいです。

と言ってみたりで、本当にしたいことは何なのかよくわかりませんが、
通りがけ順に出力したい、というのが本当なら、

左部分木を出力
自分を出力
右部分木を出力

という順にするだけでいいような気がします。

[jacks_pow]

説明が上手くできず申し訳ございません。
前順でプログラムを書きたいです。

[みけCAT]

jacks_powさんが考える、ここでの

• 通りかけ順
• 行きがけ順
• 左から出力される行きがけ順
• 通りがけ順
• 前順

の定義を説明してください。

なお、GCCの場合C言語だとコンパイルが通りましたが、C++だと

コード:

prog.cc: In function 'int main()':
prog.cc:30:41: error: invalid conversion from 'void*' to 'node*' [-fpermissive]
         tmp = malloc(sizeof(struct node));
                                         ^

というエラーになりました。

[jacks_pow]

最初に入力された値が1で
2.3.5で入力したら、
2は1の右、3は2の右、5は3の右になります。

出力は昇順でなくてよい。
やり方だけ、前順にしたいです。

[box]

1, 2, 3, 5の順に入力したものをそのまま
1 2 3 5
と出力するのはあまりおもしろくないし、質問の例としてはあまりよくないと思います。

例えば、
5, 3, 2, 7, 4, 1, 6
と入力した順にツリーを作ったとき、前順（私は聞いたことがない）というのは
どんな順番に出力することを指しますか？

[jacks_pow]

下の方でお願いします！！

[jacks_pow]

5.3.2.1.4.6.7

先行順って、左から見てくんですよね？

[box]

下の方でお願いします！！

下の方で、というのは
何が上で何が下なんですか？
また、別の投稿で「先行順」という新たな用語が出てきました。これの意味は何ですか？

ちなみに、ツリー構造をトラバースするときに使う一般的な用語は

行きがけ順
通りがけ順
帰りがけ順

の3つだけだと思います。
これら以外の用語を使うのであれば、まずはその定義から教えてください。

[jacks_pow]

行きがけ順で、下はNo.14のコメントです。

[box]

コード:

		/*自分自身を出力する*/
		printf("%d",p->data);
	
		/*左側を出力する*/
		print_tree(p->left);
		
		/*右側を出力する*/
		print_tree(p->right);

少なくともここだけを見る限り、すでに行きがけ順になっています。この部分を

コード:

		/*左側を出力する*/
		print_tree(p->left);
		
		/*自分自身を出力する*/
		printf("%d",p->data);
	
		/*右側を出力する*/
		print_tree(p->right);

↑ こう書けば通りがけ順。

コード:

		/*左側を出力する*/
		print_tree(p->left);
	
		/*右側を出力する*/
		print_tree(p->right);
		
		/*自分自身を出力する*/
		printf("%d",p->data);

↑ こう書けば帰りがけ順。

[jacks_pow]

ありがとうございます。
このプログラムをwhileのところから違うプログラムを変えたいのですが、何かうまくできませんか？

[jacks_pow]

行きがけ順に処理を考えたいです。
また、入れ替えるだけでは、入り方が違うのでは？
出力の部分は変えずに。

[box]

また、入れ替えるだけでは、入り方が違うのでは？
出力の部分は変えずに。

何をおっしゃりたいのか意味不明です。まあそれはさておき、
No.11のコメントで例示した5, 3, 2, 7, 4, 1, 6の順に入力したツリーを図化すると添付のようになり、

行きがけ順にトラバースすると、
5 → 3 → 2 → 1 → 4 → 7 → 6

通りがけ順にトラバースすると
1 → 2 → 3 → 4 → 5 → 6 → 7
（並びが昇順になる）

帰りがけ順にトラバースすると
1 → 2 → 4 → 3 → 6 → 7 → 5

となるのはおわかりでしょうか？

[jacks_pow]

　　　 5
| 　　|
3　　　7
| | | |
2 4 6
|
1

親より小さければ左、違うならば右。
６は５より大きく、かつ３より大きいので、７のほうで小さく見る。
行きがけ順なら左から見て、親　右　中間　左
よって　５．３，２，１，４，６，７

先ほどの質問は、出力は変えずに、処理で行きがけ順をやりたいです。
出力は行きがけ順でなくてよい。

[box]

よって　５．３，２，１，４，６，７

違います。
ツリーの絵柄を見て左からとかいうことではなく、トラバースというのは、
添付の赤い線のとおりにノードをたどることをいいます。
行きがけ順というのは、そのノードを初めて通過するときにカウントするやり方です。

先ほどの質問は、出力は変えずに、処理で行きがけ順をやりたいです。
出力は行きがけ順でなくてよい。

処理で行きがけ順というのは、どういう意味ですか？
ツリーへの放り込み方はおそらく1とおりしかなくて、
　・左部分木は自ノードよりも必ず小さい
　・右部分木は自ノードよりも必ず大きい
というルールに従っていないとマズいはずです。

[jacks_pow]

入力された値が1番小さかったらツリーの上にくっつける

基本的には基準より大きい値をとりあえず左に付けて、
基準と左の要素より大きい場合は右にくっつける。

こんな感じにしたいです。
普通のツリーとは何か違うみたいです。

入れ替えてくってことです。多分。。

あと、データの入れ替えは禁止です。

[みけCAT]

オフトピック

ツリーの出力なのかトラバースなのか更新なのか…
本当に、一体なにがしたいのでしょう…？

[jacks_pow]

説明不足ですみません。

処理はNo.22の通りで、出力は最初に質問したままで大丈夫です。

[みけCAT]

入力された値が1番小さかったらツリーの上にくっつける

「ツリーの上」って何ですか？

基本的には基準より大きい値をとりあえず左に付けて、
基準と左の要素より大きい場合は右にくっつける。

「基準」って何ですか？
「基準より大きい値」はどうやって得るのですか？
「左の要素」って何のですか？
右にくっつける処理をした場合、およびしなかった場合、とりあえず左に付けた(?)値はどうするのですか？
「基本的には」ということは、例外もあるのですか？ある場合、具体的にどのようなケースですか？

普通のツリーとは何か違うみたいです。

入れ替えてくってことです。多分。。

あと、データの入れ替えは禁止です。

ごめんなさい。全然想像もつきません。

処理はNo.22の通りで、出力は最初に質問したままで大丈夫です。

「最初に質問したまま」って何ですか？No: 1のコードの出力という意味ですか？

[hoge]

完全にスルーされているんですが、受け答え的に「エラーでます。関数化」のendoさんと同一人物ですよね?

[みけCAT]

説明不足ですみません。

意識しているのでしたら、改善する努力をしていただけますか？

[jacks_pow]

分かりました。
今後は質問内容を明確にした上で質問します。

[jacks_pow]

処理は先行順にして、結果を昇順にしたいです。
出力の所は自分、右、左です。

[みけCAT]

処理は先行順にして、

何をどうする処理のことですか？
ここでの「先行順」の定義は何ですか？

結果を昇順にしたいです。

何の結果ですか？
昇順にするための順序はどのようなものを使いますか？

オフトピック

そうか…これは質問ではなく独り言だから「今後は質問内容を明確にした上で質問します。」が適用されないのか…

[かずま]

分かりました。
今後は質問内容を明確にした上で質問します。

見ていると、明確にしようとすればするほど矛盾した説明になって、
回答者を混乱させているようです。
これは、何かの課題なんでしょう？
それなら、まずその課題の文章を一字一句変更せずにそのまま全部
コピペしてください。
その上で、分からないところがどこなのかを示してください。
普通の課題なら、それを解くための条件はすべて含まれているはず
ですが、そうでないと思ったら、あなたの考えを追加するのは
かまいませんが、課題の全文とあなたの考えがはっきり区別できる
ように書いてください。

[jacks_pow]

先生は、行きがけ順で昇順としか言われてないです。

恐らくですが、数値を処理で入れ替えをし、小さいならばルートに入れて、結果を昇順にするのだと思います。

私はその処理がわからないでいます。結果は自分、左、右は絶対らしいです。

[よもやま]

先生は、行きがけ順で昇順としか言われてないです。

恐らくですが、数値を処理で入れ替えをし、小さいならばルートに入れて、結果を昇順にするのだと思います。

私はその処理がわからないでいます。結果は自分、左、右は絶対らしいです。

マルチポスト相互リンク
http://bbs.wankuma.com/index.cgi?mode=al2&namber=77797
わんくま同盟　C# と VB.NET の質問掲示板　利用方法／規約： http://bbs.wankuma.com/index.cgi?mode=man

掲示板（フォーラム）ルール
http://dixq.net/board/board.html

似た内容が異なる掲示板サイトに投稿されております。
広く多くの人から意見など募集したいのであれば、本掲示板を利用していることも記載お願いします。

ネットエチケット／ネットマナーに関するサイト：　http://netiquette.fureai.or.jp/guideline.html

[usao]

オフトピック

No1の時点のコードは，
(1)二分探索木を作る部分
(2)ノードのデータ値をを行きがけ順で表示する部分
で構成されている．
このコードの表示結果は昇順ではない．
　↓
目的は，表示結果が昇順になるようにコードを変更することである
　↓
(2)の表示順を通りがけ順に変更すれば表示結果はさくっと昇順になるのだが，その方法はダメよという話になっていて，
(1)の側を（二分探索木ではない，別の二分木を作る処理に）変更することが求められている

……という話……だろうか…？

[jacks_pow]

大体はusaoさんがおっしゃる通りです。
私もこれは二分探索とは言えない気がします。

取り敢えず、処理の指定はありません。
ただ、出力が行きがけ順になります。

[jacks_pow]

入力された値が小さい数値をツリーの上にする処理は何となくできました。
後の処理が不明です。

コード:

#include<stdio.h>
#include<stdlib.h>

/*構造体を宣言する*/
struct node
{
	int data;
	struct node *left;
	struct node *right;
};

void print_tree(struct node *p);

int main(void)
{
	/*変数宣言*/
	struct node *root,*tmp,*p;
	int d,flg;
	
	/*ツリーを初期化する*/
	root = NULL;
	
	/*最初のデータを入力する*/
	printf("Input Number : ");
	scanf("%d",&d);
	
	while(d > 0)
	{
		/*要素を作成する*/
		tmp = malloc(sizeof(struct node));
		tmp->data = d;
		tmp->left = NULL;
		tmp->right = NULL;
		
		if(root == NULL)
		{
			/*ルートにくっつける*/
			root = tmp;
		}
		else
		{
			p=root;
			flg = 0;
			
			while(flg == 0)
			{
				if(tmp->data < p->data)
				{
					if(p->left == NULL )
					{
						printf("%dのうえに付けた\n",p->data);
						tmp->left=root;
						root=tmp;
						if(root->left->right!=NULL)
						{
							root->right=root->left->right;
						}
						flg=1;
					}
					/*else
					{
						if(p->data>tmp->data)
						{
							if(p->right==NULL)
						{
							printf("%dの右につけた\n",p->data);
							p->right = tmp;
							flg =1;
						}
						}
						else
						{
							p = p->right;
						}
					
					}*/
						
				}
			}
		}
	
	/*次のデータを入力する*/
	printf("Input Number : ");
	scanf("%d", &d);
	
	}
	
	/*画面に出力する*/
	printf("Result : ");
	print_tree(root);
	printf("\n");
	
	return 0;
}
		

/*ツリーを出力する関数*/
void print_tree(struct node *p)
{
	if(p != NULL)
	{
		/*自分自身を出力する*/
		printf("%d",p->data);
	
		/*左側を出力する*/
		print_tree(p->left);
		
		/*右側を出力する*/
		print_tree(p->right);
	}
}

[かずま]

多分、バグがあると思います。

コード:

#include <stdio.h>
#include <stdlib.h>

struct node { int data; struct node *left, *right; };

void print_tree(struct node *p)
{
    if (p != NULL) {
        printf("%d ", p->data); /* 行きがけ順 */
        print_tree(p->left);
        print_tree(p->right);
    }
}

void print(struct node *p, int depth)
{
    if (p) {   /* 左がルート(根)、右がリーフ(葉) */
        print(p->right, depth + 4);
        printf("%*s%d\n", depth, "", p->data);
        print(p->left, depth + 4);
    }
}

int main(void)
{
    struct node *root = NULL;
    int data;

    printf(">> ");
    while (scanf("%d", &data) == 1 && data != 0) {
        struct node **p, *tmp = (struct node *)malloc(sizeof(struct node));
        tmp->data = data;
        tmp->left = tmp->right = NULL;
        p = &root;
        while (1) {
            if (*p == NULL) {
                tmp->left = *p; *p = tmp; break;
            }
            if (data < (*p)->data) {
                tmp->left = *p;
                if ((*p)->right)
                    tmp->right = (*p)->right, (*p)->right = NULL;
                else if ((*p)->left)
                    tmp->right = (*p)->left, (*p)->left = NULL;
                *p = tmp;
                break;
            }
            if ((*p)->left == NULL) {
                (*p)->left = tmp; break;
            }
            if ((*p)->right == NULL) {
                if (data < (*p)->left->data) {
                    (*p)->right = (*p)->left;
                    (*p)->left = tmp;
                    break;
                }
                (*p)->right = tmp; break;
            }
            if (data > (*p)->right->data)
                p = &(*p)->right;
            else
                p = &(*p)->left;
        }
    }

    print(root, 0);
    printf("\nResult: ");
    print_tree(root);
    printf("\n");
    return 0;
}

実行結果その 1

コード:

>> 1 2 3 4 5 0
        5
    3
        4
1
    2

Result: 1 2 3 4 5

1 がルートで、その左の子が 2、右の子が 3。
3 の子が 4 と 5。

実行結果その 2

コード:

C:\Users\sakamoto\tmp>a
>> 3 1 4 2 5 0
    4
        5
1
    2
        3

Result: 1 2 3 4 5

これをあなたの書き方に変えて、提示してください。
そして、もっとたくさんのデータで検証して正しいと思ったら、
解決にしてください。