C言語アルゴリズム-2分木
前へ 目次へ 次へ 

5 2分木(Binary Tree) (3)

変数名(文字列)とそのデータ(整数)を入力し、2分木に格納する。変数名にendを入力すると終了する。 (pro5-5.c)

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct binary {         /* 2分木のデータ構造 */
    char        *key;           /* 節(データ) */
    int         data;
    struct binary   *left;      /* 左の枝の節の番地 */
    struct binary   *right;     /* 右の枝の節の番地 */
}BINARY;
BINARY  root = {NULL, 0, &root, &root};     /* 最初の節の番地 */
typedef struct hensuu{
    char    name[256];
    int     data;
}HENSUU;

void tree_print(BINARY *);
int tree_insert(HENSUU);

void main(void)
{
    char        buff[256];
    HENSUU      val;

    while(1){
        printf("変数名 : ");
        gets(val.name);
        if(!strcmp(val.name, "end"))
            break;
        printf("整数データ : ");
        gets(buff);
        val.data = atoi(buff);
        tree_insert(val);
        tree_print(&root);
    }
}
void tree_print(BINARY *p)
{
    static int  depth = 0;

    if(p->right != NULL){
        ++depth;
        tree_print(p->right);
        --depth;
    }
    printf("%*c%s(%d)\n", 5 * depth, ' ', p->key, p->data);
    if(p->left != NULL){
        ++depth;
        tree_print(p->left);
        --depth;
    }
}
int tree_insert(HENSUU vv)          /* 2分木構造に格納する */
{
    BINARY  *pp, *new;
    int     cmp;
    char    *s;

    pp = &root;         /* ルートの番地を格納 */
    /* 文字列データを格納する領域を確保 */
    if((s = (char *)malloc(sizeof(vv.name))) == NULL){
        printf("領域を確保できません\n");
        exit(1);
    }
    strcpy(s, vv.name);     /* 確保した領域に文字列データを格納 */

    if(pp->left == &root || pp->right == &root){    /* 最初のデータ格納 */
        pp->key = s;
        pp->data = vv.data;
        pp->left = NULL;
        pp->right = NULL;
        return(1);
    }

    /* 領域確保(新しい節を作成) */
    if((new = (BINARY *)malloc(sizeof(BINARY))) == NULL){
        printf("領域を確保できません\n");
        exit(1);
    }
    while(1){               /* 枝をたどって節を探す */
        cmp = strcmp(pp->key, s);
        if(cmp == 0){           /* 登録済み */
            free(s);            /* 領域開放 */
            free(new);          /* 領域開放 */
            return(0);
        }else if(cmp > 0){
            if(pp->left == NULL){
                pp->left = new;
                break;
            }
            pp = pp->left;  /* 次の節を探す */
        }else{
            if(pp->right == NULL){
                pp->right = new;
                break;
            }
            pp = pp->right;     /* 次の節を探す */
        }
    }
    new->key = s;       /* 新しい節にデータを登録 */
    new->data = vv.data;
    new->left = NULL;
    new->right = NULL;
    return(1);
}
実行結果
変数名 : mnd
整数データ : 11
 mnb(11)
変数名 : asd
整数データ : 22
 mnb(11)
     asd(22)
変数名 : sdf
整数データ : 33
     sdf(33)
 mnb(11)
     asd(22)
変数名 : ghj
整数データ : 44
     sdf(33)
 mnb(11)
          ghj(44)
     asd(22)
変数名 : qwe
整数データ : 55
     sdf(33)
          qwe(55)
 mnb(11)
          ghj(44)
     asd(22)
変数名 : end

 2分木に格納するデータが2つになったので、構造体binaryのデータが増えたのと、変数名とそのデータを格納する構造体を新たに宣言しているだけで、ほぼpro11-4.c(pro5-4.c)のプログラムと同じである。
 実行例の最後には、2分木は次のようになる。
btree

 

変数名とそのデータをあらかじめ2分木に格納し、入力した変数名を検索し、そのデータを表示する。endを入力すると終了する。 (pro5-6.c)

 1:
 2:
 3:
 4:
 5:
 6:
 7:
 8:
 9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct binary {         /* 2分木のデータ構造 */
    char        *key;           /* 節(データ) */
    int         data;
    struct binary   *left;      /* 左の枝の節の番地 */
    struct binary   *right;     /* 右の枝の節の番地 */
}BINARY;
BINARY  root = {NULL, 0, &root, &root};     /* 最初の節の番地 */
typedef struct hensuu{
    char    name[256];
    int     data;
}HENSUU;

HENSUU tree_search(char *);
void tree_print(BINARY *);
int tree_insert(HENSUU);

void main(void)
{
    char        buff[256];
    int         i = 0;
    static HENSUU   vv, val[] = {
            "hensuu", 12, "joho", 38,
            "tree", 123, "start", 33,
            "first", 1, "abcd", 111,
            "goal", 99, "masuda", 121,
            "*", 0
                };

    while(1){       /* 変数名とデータの格納 */
        if(val[i].name[0] == '*'){
            tree_print(&root);
            break;
        }
        tree_insert(val[i]);
        ++i;
    }
    while(1){
        printf("変数名 : ");
        gets(buff);
        if(!strcmp(buff, "end"))
            break;
        vv = tree_search(buff);
        if(vv.name[0] == '\0')
            printf("見つからない\n");
        else
            printf("データ = %d\n", vv.data);
        tree_print(&root);
    }
}
HENSUU tree_search(char *hensuu)
{
    BINARY  *pp;
    int     cmp;
    HENSUU  vv;

    vv.name[0] = '\0';
    vv.data = 0;
    pp = &root;
    while((cmp = strcmp(hensuu, pp->key)) != 0){
        if(cmp < 0){
            if(pp->left == NULL)    /* データ終了 */
                return(vv);
            pp = pp->left;
        }else{
            if(pp->right == NULL)   /* データ終了 */
                return(vv);
            pp = pp->right;
        }
    }
    strcpy(vv.name, hensuu);
    vv.data = pp->data;
    return(vv);
}
実行結果
          tree(123)
               start(33)
                    masuda(121)
     joho(38)
 hensuu(12)
          goal(99)
     first(1)
          abcd(111)
変数名 : tree
データ = 123
          tree(123)
               start(33)
                    masuda(121)
     joho(38)
 hensuu(12)
          goal(99)
     first(1)
          abcd(111)
変数名 : end

 ユーザ関数tree_insertとtree_printはproc5-5.cと同じであるので省略している。



前へ 目次へ 次へ 
Copyright © 2001 Hiroshi Masuda 

 

 

inserted by FC2 system