2分木

質問

実行すると
「トップノードの値を入力してください。20
ノード[20:深さ0]の左の子の値を入れてください。15
ノード[20:深さ0]の右の子の値を入れてください。40
ノード[15:深さ1]の左の子の値を入れてください。11
ノード[15:深さ1]の右の子の値を入れてください。18
ノード[11:深さ2]の左の子の値を入れてください。/
ノード[18:深さ2]の左の子の値を入れてください。17
ノード[18:深さ2]の右の子の値を入れてください。/
　　　　　　　　　　・
が表示されて2分木のデータを作成するプログラムを作りたいのです。絵で表すと、
　　　　　 20
／ ＼
　　　　15 40
／ ＼ ／＼
11 18 30 55
／ ／＼ ＼
17 25 33 61
のようになります(なんか絵がずれて表示される）。
一応、自分で考えてみたのですが
#include<stdio.h>
#include<malloc.h>
struct data
{ int kazu;
struct data *left;
struct data *right;
};
main()
{
struct data *root,*p;
root=(struct data *)malloc(sizeof(struct data));
printf("トップノードの値を入れてください:");
scanf("%d",root->kazu);
root->left=root->right=NULL;

while(1){
p=(struct data *)malloc(sizeof(struct data));
printf("ノード%d,深さ%dの左の子の値を入れてください",root->kazu,
scanf("%d", );
printf("ノード%d,深さ%dの右の子の値を入れてください",root->kazu,
scanf("%d", );
if(
break;

なんか全然良くわからないのです。アルゴリズムの本を見て勉強していて、データ構造は理解できたのですが、２分木(グラフ)で詰まってしまいました。
小さい順に数を表示させるとか、そういうのじゃなくて、単にデータを格納するだけです。どうかよろしくお願いします。

回答No.2

yatokesa

数年ぶりにこういうものを作ってみたくなり、作ってみました。参考程度にとどめて置いてください。一応動くとは思いますが、検証してません。入力部分は関数化した方がよいですが、本題と関係ないのでそのままです。

struct data
{
int kazu;
struct data *left;
struct data *right;
};

char buf[32];

main()
{
struct data *root;

root = (struct data*)malloc(sizeof(struct data));

root->left = NULL;
root->right = NULL;

printf ("Input node of top >");
scanf ("%d", &root->kazu);

cur = root;

btree(root, 0);

}

btree (struct data *cur, int depth)
{
printf ("node %d depth %d left >", cur->kazu, depth);
scanf ("%s", buf);
if (buf[0] == '/') {
cur->left = NULL;
} else {
cur->left = (struct data*)malloc(sizeof (struct data));
cur->left->kazu = atoi(buf);
}

printf ("node %d depth %d right >", cur->kazu, depth);
scanf ("%s", buf);
if (buf[0] == '/') {
cur->right = NULL;
} else {
cur->right = (struct data*)malloc(sizeof (struct data));
cur->right->kazu = atoi(buf);
}

if (cur->left) {
btree (cur->left, depth + 1);
}

if (cur->right) {
btree (cur->right, depth + 1);
}
}

回答No.1

ymmasayan

ご質問そのものに答える前に、２分木の作り方について少々考えてみます。
２分木は、データを登録する順序を変えるだけで、全く違った構成になることは明白です。

従って、２分木の登録のやり方自体が、この例では、（他にも色々あるとしても）例えば、２０、１５、１１、１８、１７、４０、３０、２５、３３、５５、６１の順で登録すれば題意の２分木が出来るのです。これが通常の２分木の作成方法です。

ご質問にあるように、何番のノードの右下に何番と言うような作り方は普通しないと思います。

あと、疑問点を少々（補足下さい）
（１）文章とノードの図でノードの数が違う。
（２）「／」の使われているところと使われていないところがある。