二分木構造

http://www.geocities.jp/ky_webid/algorithm/016.html

いわゆるツリー構造と呼ばれる物です。

概念としては良く分かりました。が、実際にどう実装するかのイメージがつきません。

ということで今回は先に解答例をじっくり読んでどういったものかを理解した上で、自分なりに実装したいと思います。

読み解いていくと、いくつか気になる点が。

値の探索はいいんですが、初期値の設定に難がありそうですね。先に一次元配列でデータの定義を行っています。

これを元に初期値の設定をする流れですね。

とりあえずマネしながら実装してみます。

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

#define MAX 15

struct NODE {
    int data;
    struct NODE *left;
    struct NODE *right;
};
typedef struct NODE NODE;

int init_data[MAX+1] = {0,4,7,9,13,8,10,22,6,0,0,15,2,29,0,0};

NODE *create_node(int data);
void create_tree(NODE **root);
void preorder(NODE *n);
void inorder(NODE *n);
void postorder(NODE *n);

NODE *create_node(int data) {
    NODE *p;
    p = (NODE *)malloc(sizeof(NODE));
    if ( p == NULL ) {
        return NULL;
    }
    p->left  = NULL;
    p->right = NULL;
    p->data  = data;
    return p;
}

void create_tree(NODE **root){
    int i;
    int left,right;
    NODE *tmp[MAX+1];
    
    *root = tmp[1] = create_node(init_data[1]);
    for(i=1;i<MAX/2;i++){
        left  = i * 2;
        right = left + 1;
        if ( init_data[left] ) {
            tmp[i]->left = tmp[left] = create_node(init_data[left]);
        }
        if ( init_data[right] ) {
            tmp[i]->right = tmp[right] = create_node(init_data[right]);
        }
    }
}

void preorder(NODE *n){
    if( n == NULL ){ return; }
    printf( "%2d ", n->data );
    preorder( n->left );
    preorder( n->right );
}

void inorder(NODE *n){
    if( n == NULL ){ return; }
    inorder( n->left );
    printf( "%2d ", n->data );
    inorder( n->right );
}

void postorder(NODE *n){
    if( n == NULL ){ return; }
    postorder( n->left );
    postorder( n->right );
    printf( "%2d ", n->data );
}

int main (void) {
    NODE *root;
    
    create_tree(&root);
    
    printf("preorder  : ");
    preorder(root);
    
    printf("\ninorder   : ");
    inorder(root);
    
    printf("\npostorder : ");
    postorder(root);
    
    return 0;
}

$ main
preorder  :  4  7 13  6  8 15  9 10  2 29 22
inorder   :  6 13  7  8 15  4  2 10 29  9 22
postorder :  6 13 15  8  7  2 29 10 22  9  4

とりあえずできました。

探索の仕方に三パターンあるわけですが、これらの違いが何かの役に立つのでしょうか。

いまいちどういうものにこれを使うのかが分からないですね。

実例とかあるとわかりやすいのですが・・・。