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

5 2分木(Binary Tree) (2)

データ9,24,18,15,12,27,6,21,3を2分木に格納したあと、キーボードから入力したデータも追加格納できるようにする。0を入力すると終了する。 (pro5-3.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:
#include <stdio.h>
#include <stdlib.h>

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

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

void main(void)
{
    int     i, ndata[9] = { 9, 24, 18, 15, 12, 27, 6, 21, 3 };
    int     x, r;

    for(i = 0; i < 9; ++i){
        tree_insert(ndata[i]);
    }
    while(1){
        printf("Data : ");
        scanf("%d", &x);
        if(x == 0)
            break;
        r = tree_insert(x);
        if(r == 0)
            printf("登録済みです\n");
        else
            tree_print(&root);
    }
}

ユーザ関数tree_insertとtree_printはpro11-2.c(pro5-2.c)はと同じであるので省略してある。

 

入力した文字列を2分木に格納する。endを入力すると終了する。 (pro5-4.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:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

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

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

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

    while(1){
        printf("文字列データ : ");
        gets(buff);
        if(!strcmp(buff, "end"))
            break;
        tree_insert(buff);
        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\n", 5 * depth, ' ', p->key);
    if(p->left != NULL){
        ++depth;
        tree_print(p->left);
        --depth;
    }
}
int tree_insert(char *str)      /* 2分木構造に格納する */
{
    BINARY  *pp, *new;
    int     cmp;
    char    *s;

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

    if(pp->left == &root || pp->right == &root){    /* 最初のデータ格納 */
        pp->key = s;
        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, str);
        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->left = NULL;
    new->right = NULL;
    return(1);
}


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

 

 

inserted by FC2 system