C言語関係掲示板

過去ログ

No８５９　二分木の問題について

[戻る]　[ホームページ]
No.11093
二分木の問題について
投稿者---ミユキ(2003/12/11 23:36:42)


学校にて以下の様な問題がでたのですが、

ある単性生殖生物は子供を持たないか， もしくは二匹の子供をもつかのどちらかである． すべての生物は整数値のIDにより識別されている。
番号の重複はない。 子供のIDは親のIDよりも必ず大きくなっている。 また、この生物は増殖はするが死滅はしないものとする。
ある生物のIDを入力すると，その生物から先祖までのIDのリストを 表示するプログラムを作成せよ。
生物の家系(木)はデータの中に複数個(森)存在することもある。
親子関係はCSV形式で一行で以下のようにユーザが与えるものとする
親ID,子ID,子ID
もし，IDに関する条件を破る入力が行われた場合， プログラムは即座に終了するものとする．
検索は，単に
ID
という形式で与えられるものとする． 結果は
検索対象,親、祖父、曾祖父,...,家系の始まり のような形式とり，もし対象が存在しないIDの場合， 空行を返すものとする． 

typedef struct binary{
struct binary *parent;
struct binary *child1;
struct binary *child2;
}BINARY;

みたいな構造体で行おうとしたのですが、入力が３つの時と１つの時があり（木の挿入と検索）
どの様に入力すればよいのでしょうか？また、2分木構造への格納がよくわからないので
ご教授お願いいたします。
No.11094
Re:二分木の問題について
投稿者---RAPT(2003/12/11 23:58:43)


示されたデータ構造 struct binary は、親・子へのポインタはありますが、
肝心な、自分自身の情報を格納する場所がありません。

…要するに「整数値のID」を構造体に含める必要があります。

その上で、何が分からないのでしょう？

まずは、簡単に、この構造体によるリストの作成を行い、
ノードの追加と、検索を行なえるようなコードを書いてみてください。

その上で、提示された条件を追加していくようにする良いでしょう。
No.11095
Re:二分木の問題について
投稿者---RAPT(2003/12/12 00:07:18)


二分木の構造は、絵を書くと分かりやすいでしょうが、

根っこの部分、parent == NULL となり、末端部では、child1, child2 が
NULLかどうかで判断することとなるでしょう。

検索アルゴリズムは、child1 == NULL になるまで、順次探索し、
child1==NULL なら、parent->child2へ探索場所を変える。
parent->child2==NULLであれば、parent->parent->child1 … とし、
parent->parent == NULL のとき、探索終了となる。

といった探索方法でいいかな。
No.11096
Re:二分木の問題について
投稿者---ミユキ(2003/12/12 00:12:05)


即レスありがとうございます。
確かにIDを入れる場所がないですね・・・（汗）
検索方法を参考に頑張ってみます。躓いたらまたお願いいたしますね。
No.11097
Re:二分木の問題について
投稿者---RAPT(2003/12/12 00:17:59)


修正
>child1==NULL なら、parent->child2へ探索場所を変える。
>parent->child2==NULLであれば、parent->parent->child1 … とし、
child1==NULL なら、child2へ探索場所を変える。
child2==NULLであれば、parent->child2 … とし、
です。
No.11098
二分木の問題について（入力について）
投稿者---ミユキ(2003/12/12 02:26:15)


入力についてですが３つの時と１つの時があり（木の挿入と検索）
コレについてどうしても出来ず困ってます・・・（最初の一歩目なのに・・）
scanf("%d,%d,%d",a,b,c);
みたいだと３つ入力しなければ次の命令にいかないですし・・・
getsを使って下記の様に分解を試みたのですがどうも駄目です。
もしgetsで読み込んで分解したとしても入力した文字が３つか１つの判定のしかたが
思いつきません。
どうかお助けください。あぁ締め切りに間に合わない・・・

#include        <stdio.h>
#include        <string.h>

int main(void)
{
  char line[20];
  char *tp;
  char a[20];
  char b[20];
  char c[20];
  const char *seps = "," ;
  const char *token = NULL;
  /* スペース.を区切りに文字列を抽出 */
  gets(line);   
  token = strtok(line, seps);
  strncpy(a, token, 200);
  
  token = strtok(NULL, seps);
  strncpy(b, token, 200);
  
  token = strtok(NULL, seps);
  strncpy(c, token, 200);
  printf("%s,%s,%s",a,b,c);
}


No.11100
Re:二分木の問題について（入力について）
投稿者---NykR(2003/12/12 08:42:39)


a,b,cをintで宣言して、

sscanf(line, "%d,%d,%d", &a, &b, &c)

scanf関係の関数は、代入に成功した数を返します
だから、この式の値が3なら入力が３つ、1なら１つ、で判定できます。
scanfに似てますが、この式を評価する前に、(getsのところで)入力は終わってるので、
>３つ入力しなければ次の命令にいかないですし・・・

ということもありません。

＃a,b,cはnode_id, child1, child2とかの方がいいような気がしますが。
＃あとgetsもfgetsの方がいいです。getsでは配列のサイズを超えた入力に対応するのは不可能ですから。
No.11141
二分木の問題について（ノードの追加について）
投稿者---ミユキ(2003/12/13 03:11:04)


>scanf関係の関数は、代入に成功した数を返します
>だから、この式の値が3なら入力が３つ、1なら１つ、で判定できます。
この様な事が出来たとは知りませんでした！！ありがとうございます。
で、一応作ってみたのですが、ノードの追加のしかたがうまく出来ません・・・
親の番地をつなげて森（木の構造体をつなげる）をつくりたいのですが
どうすればよいのでしょうか？と言うか私のプログラムだと
どうも木すらままならないです・・・（汗）どうかご教授くださいませ。

#include <stdio.h>
#include <stdlib.h> /* malloc */

typedef struct binary {         /* 2分木のデータ構造 */
  int id;   /*データ*/
  struct binary   *parent;           /* 親の番地 */
  struct binary   *child1;      /* 子の節の番地 */
  struct binary   *child2;     /* 子の節の番地 */
}binary_t;

typedef struct mori {         /*親をくっ付ける 森のデータ構造 */
  binary   *root;          
  struct mori *next;     /* 森の番地 */
}mori_t;

binary_t  root = {NULL, &root, &root}; /* 最初の節の番地 */

int serch();/*検索関数*/
void print();/*出力関数*/
int add_node(int oya,int ko1,int ko2); /* ノードの追加 */;

void main(void)
{
  int i; /*入力個数*/
  int oya; /*親のID*/
  int ko1; /*子のID*/
  int ko2; /*子のID*/
  while(1){
    sscanf("%d,%d,%d",&oya,&ko1,&ko2); /*ユーザからの入力*/
    i = scanf("%d,%d,%d",&oya,&ko1,&ko2); /*入力個数をiに代入*/
    if(i == 1){
      serch(); /*検索関数*/
      print(); /*表示関数*/
      b == NULL;
      c == NULL;
    }
    if((i != 1 && a >= b) || (i != 1 && a >= c)){ /*普遍命題を破る入力がされたら終了 親が子より大きな数字*/
      break;
    }
    add_node(oya,ko1,ko2);/*挿入関数*/
  }
}

int add_node(int oya,int ko1,int ko2) /* ノードの追加 */;
{
  binary_t *pp;
  binary_t *new;
  
  pp = &root;         /* ルートの番地を格納 */
  if(pp->child1 == &root || pp->child2 == &root){    /* 最初のデータ格納 */
    pp->key = oya;
    pp->child1 = NULL;
    pp->child2 = NULL;
    return(1);
  }
  
  /* 領域確保（新しい節を作成） */
  if((new = (binary_t *)malloc(sizeof(binary_t))) == NULL){
    printf("領域を確保できません\n");
    exit(1);
  }
  while(pp->parent != id){        /* 枝をたどって節を探す */
    if(id < pp->parent){
      if(pp->child1 == NULL){
    pp->child1 = new;
    break;
      }
      pp = pp->child1;              /* 次の節を探す */
    }else{
      if(pp->child2 == NULL){
    pp->child2 = new;
    break;
      }
      pp = pp->child2;             /* 次の節を探す */
    }
  }
  if(pp->parent == id){           /* 登録済み */
    free(new);                      /* 領域開放 */
    return(0);
  }
  new->parent = id;               /* 新しい節にデータを登録 */
  new->child1 = NULL;
  new->child2 = NULL;
  return(1);
}

No.11155
Re:もう一杯一杯です（泣）どなたか教えてください・・・（ノードの追加について）
投稿者---NykR(2003/12/13 16:28:04)		 


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

typedef struct unity_t {
    int id;
    struct unity_t *parent;
    struct unity_t *l_child;
    struct unity_t *r_child;
} Unity;

typedef struct rhizome_t {
    Unity       *root;
    struct rhizome_t *next;
} Rhizome;

Rhizome *gb_head = NULL;

void printAll_sub(Unity *root)
{
    if (root->l_child == NULL || root->r_child == NULL)
        return;

    fprintf(stderr, "%d,%d,%d\n", root->id, root->l_child->id, root->r_child->id);
    printAll_sub(root->l_child);
    printAll_sub(root->r_child);
}

void printAll(void)
{
    Rhizome *idx;

    fprintf(stderr, "###########################################\n");
    for (idx = gb_head; idx->next != NULL; idx = idx->next) {
        printAll_sub(idx->next->root);
    }
    fprintf(stderr, "###########################################\n");
}

Unity *searchUnit_sub(Unity *root, int id)
{
    Unity *temp;

    if (root == NULL || root->id == id)
        return root;

    if ((temp = searchUnit_sub(root->l_child, id)) != NULL)
        return temp;

    return searchUnit_sub(root->r_child, id);
}

Unity *searchUnit(int id)
{
    Rhizome *tree;
    Unity *temp;

    for (tree = gb_head; tree != NULL; tree = tree->next) {
        if ((temp = searchUnit_sub(tree->root, id)) != NULL)
            return temp;
    }

    return NULL;
}

int addNode(Unity *node, int l_child_id, int r_child_id)
{
    if ((node->l_child = malloc(sizeof(Unity))) == NULL)
        return 0;

    if ((node->r_child = malloc(sizeof(Unity))) == NULL)
        return 0;

    node->l_child->id = l_child_id;
    node->l_child->parent = node;
    node->l_child->l_child = NULL;
    node->l_child->r_child = NULL;

    node->r_child->id = r_child_id;
    node->r_child->parent = node;
    node->r_child->l_child = NULL;
    node->r_child->r_child = NULL;

    return 1;
}

int addTree(int parent_id, int l_child_id, int r_child_id)
{
    Rhizome *tail;

    for (tail = gb_head; tail->next != NULL; tail = tail->next)
        ;

    if ((tail->next = malloc(sizeof(Rhizome))) == NULL)
        return 0;

    tail = tail->next;

    if ((tail->root = malloc(sizeof(Unity))) == NULL)
        return 0;

    tail->root->id = parent_id;
    tail->root->parent = NULL;
    tail->next = NULL;

    addNode(tail->root, l_child_id, r_child_id);

    return 1;
}

void unitAddition(int parent_id, int l_child_id, int r_child_id)
{
    Unity *parent_node;

    if (searchUnit(l_child_id) != NULL || searchUnit(r_child_id) != NULL) {
        printAll();
        exit(1);
    }

    if ((parent_node = searchUnit(parent_id)) != NULL) {
        if (parent_node->l_child != NULL || parent_node->r_child != NULL) {
            printAll();
            return;
        }
        if (!addNode(parent_node, l_child_id, r_child_id))
            goto error;
    } else {
        if (!addTree(parent_id, l_child_id, r_child_id))
            goto error;
    }
    return;

  error:
    fprintf(stderr, "メモリ不足\n");
    printAll();
    exit(1);
}

int main(void)
{
    int node_id, l_child_id, r_child_id;
    int status;

    gb_head = malloc(sizeof(Rhizome));

    for (;;) {
        for (;;) {
            char buf[1024];

            fgets(buf, sizeof(buf), stdin);
            status = sscanf(buf, "%d,%d,%d", &node_id, &l_child_id, &r_child_id);

            if (status == 1 || status == 3)
                break;
        }

        if (status == 3) {
            if (node_id >= l_child_id || node_id >= r_child_id) {
                printAll();
                return 1;
            }

            unitAddition(node_id, l_child_id, r_child_id);
        } else if (status == 1) {
            Unity *node;

            for (node = searchUnit(node_id); node != NULL; node = node->parent) {
                printf("%d,", node->id);
            }
            printf("\n");
        }
    }

    return 0;
}

freeしてませんけど。

あと、テストもあまりやってません。
No.11164
Re:もう一杯一杯です（泣）どなたか教えてください・・・（ノードの追加について）
投稿者---NykR(2003/12/13 17:34:15)		 


void printAll(void)
{
    Rhizome *idx;

    fprintf(stderr, "###########################################\n");
    for (idx = gb_head->next; idx != NULL; idx = idx->next) {
        printAll_sub(idx->root);
    }
    fprintf(stderr, "###########################################\n");
}

こっちの方がいいかな。って要求仕様にない部分ですけど。
No.11165
Re:もう一杯一杯です（泣）どなたか教えてください・・・（ノードの追加について）
投稿者---NykR(2003/12/13 18:25:23)


親へのポインタを消しました。あった方が楽ですけど。

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

typedef struct unity_t {
    int id;
    struct unity_t *l_child;
    struct unity_t *r_child;
} Unity;

typedef struct rhizome_t {
    Unity       *root;
    struct rhizome_t *next;
} Rhizome;

Rhizome *gb_head = NULL;

void printAll_sub(Unity *root)
{
    if (root->l_child == NULL || root->r_child == NULL)
        return;

    fprintf(stderr, "%d,%d,%d\n", root->id, root->l_child->id, root->r_child->id);
    printAll_sub(root->l_child);
    printAll_sub(root->r_child);
}

void printAll(void)
{
    Rhizome *idx;

    fprintf(stderr, "###########################################\n");
    for (idx = gb_head->next; idx != NULL; idx = idx->next) {
        printAll_sub(idx->root);
    }
    fprintf(stderr, "###########################################\n");
}

Unity *searchUnit_sub(Unity *root, int id)
{
    Unity *temp;

    if (root == NULL || root->id == id)
        return root;

    if ((temp = searchUnit_sub(root->l_child, id)) != NULL)
        return temp;

    return searchUnit_sub(root->r_child, id);
}

Unity *searchUnit(int id)
{
    Rhizome *tree;
    Unity *temp;

    for (tree = gb_head; tree != NULL; tree = tree->next) {
        if ((temp = searchUnit_sub(tree->root, id)) != NULL)
            return temp;
    }

    return NULL;
}

Unity *creatNode(int id)
{
    Unity *temp;

    if ((temp = malloc(sizeof(Unity))) == NULL)
        return NULL;

    temp->id = id;
    temp->l_child = NULL;
    temp->r_child = NULL;

    return temp;
}

int addNode(Unity *node, int l_child_id, int r_child_id)
{
    if ((node->l_child = creatNode(l_child_id)) == NULL)
        return 0;

    if ((node->r_child = creatNode(r_child_id)) == NULL)
        return 0;

    return 1;
}

int addTree(int parent_id, int l_child_id, int r_child_id)
{
    Rhizome *tail;

    for (tail = gb_head; tail->next != NULL; tail = tail->next)
        ;

    if ((tail->next = malloc(sizeof(Rhizome))) == NULL)
        return 0;

    tail = tail->next;

    if ((tail->root = malloc(sizeof(Unity))) == NULL)
        return 0;

    tail->root->id = parent_id;
    tail->next = NULL;

    addNode(tail->root, l_child_id, r_child_id);

    return 1;
}

void unitAddition(int parent_id, int l_child_id, int r_child_id)
{
    Unity *parent_node;

    if (searchUnit(l_child_id) != NULL || searchUnit(r_child_id) != NULL) {
        printAll();
        exit(1);
    }

    if ((parent_node = searchUnit(parent_id)) != NULL) {
        if (parent_node->l_child != NULL || parent_node->r_child != NULL) {
            printAll();
            return;
        }
        if (!addNode(parent_node, l_child_id, r_child_id))
            goto error;
    } else {
        if (!addTree(parent_id, l_child_id, r_child_id))
            goto error;
    }
    return;

  error:
    fprintf(stderr, "メモリ不足\n");
    printAll();
    exit(1);
}

int printFamilyTree_sub(Unity *root, int id)
{
    if (root == NULL) return 0;
    if (root->id == id) goto print;

    if (printFamilyTree_sub(root->l_child, id))
        goto print;

    if (printFamilyTree_sub(root->r_child, id))
        goto print;

    return 0;

  print:
    printf("%d,", root->id);
    return 1;
}

void printFamilyTree(int id)
{
    Rhizome *tree;

    for (tree = gb_head; tree != NULL; tree = tree->next) {
        printFamilyTree_sub(tree->root, id);
    }
    printf("\b\n");
}

int main(void)
{
    int node_id, l_child_id, r_child_id;
    int status;

    gb_head = malloc(sizeof(Rhizome));

    for (;;) {
        for (;;) {
            char buf[1024];

            fgets(buf, sizeof(buf), stdin);
            status = sscanf(buf, "%d,%d,%d", &node_id, &l_child_id, &r_child_id);

            if (status == 1 || status == 3)
                break;
        }

        if (status == 3) {
            if (node_id >= l_child_id || node_id >= r_child_id) {
                printAll();
                return 1;
            }
            unitAddition(node_id, l_child_id, r_child_id);
        } else if (status == 1) {
            printFamilyTree(node_id);
        }
    }

    return 0;
}

No.11168
Re:もう一杯一杯です（泣）どなたか教えてください・・・（ノードの追加について）
投稿者---NykR(2003/12/13 20:28:01)


配列を使うという手もあります。（メモリが勿体ないけど）

#include <stdio.h>
#define TREE_SIZE (0x100000)
#define TREE_NUM (0x10)

int vec[TREE_NUM][TREE_SIZE];

int search_node(int id, int *tree, int *node)
{
    for (*tree = 0; *tree < TREE_NUM; ++*tree) {
        if (vec[*tree][0] == 0) break;
        for (*node = 0; *node < TREE_SIZE; ++*node)
            if (vec[*tree][*node] == id) return 1;
    }
    return 0;
}

void add_node(int p_id, int l_id, int r_id)
{
    int i, j;

    if (search_node(l_id, &i, &j) || search_node(r_id, &i, &j)) {
        printf("duplicate\n"); return;
    }
    if (!search_node(p_id, &i, &j))
        if (i >= TREE_NUM) printf("not vacant\n");
        else vec[i][0] = p_id, add_node(p_id, l_id, r_id);
    else
        if (j*2+1 >= TREE_SIZE || vec[i][j*2+1] != 0) printf("not vacant\n");
        else vec[i][j*2+1] = l_id, vec[i][j*2+2] = r_id;
}

void print(int id)
{
    int i, j;

    if (!search_node(id, &i, &j)) return;
    for (;;) {
        printf("%d", vec[i][j]);
        if (j <= 0) { putchar('\n'); return; }
        j = (j - 1) / 2;
        putchar(',');
    }
}

int main(void)
{
    int node_id, l_id, r_id, status;

    for (;;) {
        for (;;) {
            char buf[1024];

            fgets(buf, sizeof(buf), stdin);
            status = sscanf(buf, "%d,%d,%d", &node_id, &l_id, &r_id);
            if (status == 1 || status == 3) break;
        }
        if (status == 3) {
            if (node_id >= l_id || node_id >= r_id) return 1;
            add_node(node_id, l_id, r_id);
        } else if (status == 1) print(node_id);
    }
    return 0;
}

No.11170
Re:ノードの追加について
投稿者---ミユキ(2003/12/13 21:35:22)


返信ありがとうございます！！ソースを拝見しましたが美しいですね〜
結構感激です。
配列を使うのは考えましたが私は無理だとは思い諦めたのですが、可能だとは！！（驚）構造体とポインタを使う問題はどうも苦手なので復習しなくては・・・では、参考にして頑張ってみます。本当にありがとうございます。
No.11205
Re:ノードの追加について
投稿者---NykR(2003/12/15 15:13:45)


今更ですが、森の中のすべてのノードを一つの配列に入れると
メモリも有効利用できますし、ノードの探索が簡単になります。

また、この場合、根本からノードをたどる必要がないので、子へのポインタはいりません。
＃別に有ってもいいですが

子そのものを参照する代わりに、数を覚えておくようにすれば、本質的には二分木の問題ではなくなります。
＃子の数を変更しても対応できる

                :
                :
                :
                :
       +----------------+
       | parnt_ptr>>>>--------------->NULL (rootには親がいない)
       | id             |<-----+
       | n_of_chldrn==2 |<-+   |
       +----------------+  |   |
       | parnt_ptr>>>>-----+   |
       | id             |      |
       | n_of_chldrn    |      |
       +----------------+      |
       | parnt_ptr>>>>---------+
       | id             |<---+
       | n_of_chldrn==2 |<-+ |
       +----------------+  | |
       | parnt_ptr      |  | |
       | id             |  | |
       | n_of_chldrn    |  | |
       +----------------+  | |
       | parnt_ptr      |  | |
       | id             |  | |
       | n_of_chldrn    |  | |
       +----------------+  | |
       | parnt_ptr>>>>-----+ |
       | id             |    |
       | n_of_chldrn==0 |    |
       +----------------+    |
       | parnt_ptr>>>>-------+
       | id             |
       | n_of_chldrn==0 |
       +----------------+
                :
                :
                :
                :
                :

この場合ノードの型は、こんな感じの構造体になりますね。

typedef struct {
    int id;           /* ｉｄ　　　　　 */
    int parnt_ptr;    /* 親へのポインタ */
    int n_of_chldrn;  /* 子供の数　　　 */
} Unity;


この場合、親へのポインタはポインタ型である必要はありません。
添字で参照すればいいのでint型で十分です。
＃どっちが楽かはわかりませんが

家系の始まりの親には負の数など、添字としてあり得ない値を入れればいい。

データを追加するときは、配列の使用済み部分の末尾に代入するだけでよく、
毎回mallocする必要もありません。
配列のサイズと入力済みのデータ数をグローバル変数で保持しておいて、
typedef struct {
    Unity       *unity;     /* 配列　　　　　　 */
    int         data_count; /* 入力済みデータ数 */
    int         size;       /* 配列のサイズ　　 */
} Woods;

Woods   woods = {NULL, 0, 0};


狭くなったら（追加されるデータは、最大三つなので、
それが可能かどうかで判定すればいい）reallocで拡張するようにするといいでしょう。