ツリー構造について
Posted: 2011年12月14日(水) 21:25
ツリー構造の問題なのですが、最後の問題が解けなくて困ってます。
ここまではできたのですが、どのように組めばよいのかわかりません。
解答よろしくお願いします。
構造体メンバの dup は重複度を表す数字である。
２分木は data=3 となるデータが存在したときに「３」が追加された場合、そのデータの右下に新たな「３」が追加されていた。
これを改良し、同じ値のデータが入力された場合には、dup = dup+1 となるようにせよ。
つまり、data=3 となるデータが存在したときに「３」が追加された場合、新たにデータを追加して木を大きくするのではなく、データ「３」の dup を dup=dup+1 とせよ。
さらに、木を表示する関数 disp_tree を改良し、重複度を表示するようにせよ。
例えば、data=3 となるデータの重複度 dup=2 のときは
3[2]
と表示するようにせよ。
つまり、木が
-------------------
90[1]
50[1]<
10[3]
3[2]<
2[1]
-------------------
となるようにせよ。
ここまではできたのですが、どのように組めばよいのかわかりません。
解答よろしくお願いします。
構造体メンバの dup は重複度を表す数字である。
２分木は data=3 となるデータが存在したときに「３」が追加された場合、そのデータの右下に新たな「３」が追加されていた。
これを改良し、同じ値のデータが入力された場合には、dup = dup+1 となるようにせよ。
つまり、data=3 となるデータが存在したときに「３」が追加された場合、新たにデータを追加して木を大きくするのではなく、データ「３」の dup を dup=dup+1 とせよ。
さらに、木を表示する関数 disp_tree を改良し、重複度を表示するようにせよ。
例えば、data=3 となるデータの重複度 dup=2 のときは
3[2]
と表示するようにせよ。
つまり、木が
-------------------
90[1]
50[1]<
10[3]
3[2]<
2[1]
-------------------
となるようにせよ。
#include < stdio.h >
#include < stdlib.h >
struct tree
{
int data;
struct tree *left;
struct tree *right;
int dup;//ここを追加
};
void add_tree( struct tree *parent, int x )
{
struct tree *child;
child = (struct tree *)malloc( sizeof(struct tree) );
child->data = x;
child->left = NULL;
child->right = NULL;
if( x < parent->data )
{
if( parent->left == NULL )
{
parent->left = child;
}
else
{
free( child );
add_tree( parent->left, x );
}
}
else
{
if( parent->right == NULL )
{
parent->right = child;
}
else
{
free( child );
add_tree( parent->right, x );
}
}
}
void disp_tree( struct tree *head, int depth )
{
int i;
if( head->right != NULL )
disp_tree( head->right, depth+1 );
for( i=0 ; i < depth ; i++ ) // まずは depth の分だけ空白を表示しておく
printf(" ");
if( head->data <10 )// 桁数によって表示がズレないように空白と記号表示
printf(" ");
printf("%d<\n",head->data); // データ表示
if( head->left != NULL )
disp_tree( head->left, depth+1 ); // 再帰呼び出しで表示
}
void disp_sort( struct tree *head)
{
if(head->left !=NULL)
disp_sort(head->left);
printf("%d ",head->data);//データ表示
if(head->right!=NULL)
disp_sort(head->right);//再帰呼び出しで表示
}
void main()
{
int a;
struct tree *head; // 木の頂上になるデータ
head = (struct tree *)malloc( sizeof(struct tree) );
head->data = 50; // 木の頂上の値は50としておく
head->left = NULL;
head->right = NULL;
do
{
disp_tree( head, 1 ); // 木の表示
printf("\n\n\n");
printf("1-99の整数を入力して下さい（０で終了／１００でソート結果表示）：");
scanf("%d",&a);
if( a == 100 )
{
disp_sort(head);
printf("\n\n");
}
else
add_tree( head, a ); // データの追加
}
while( a != 0 );
}