二分木　解答ページ | Programming Place Plus　アルゴリズムとデータ構造編【データ構造】　第７章

トップページ – アルゴリズムとデータ構造編 – 【データ構造】第７章

問題① 🔗

問題①　二分木の高さを返す関数を作成してください。


高さを調べる際にも、やはり再帰処理が利用できます。

int get_height(BinaryTree tree, int height)
{
    if( tree == NULL ){
        return height;
    }

    int l = get_height( tree->left, height );
    int r = get_height( tree->right, height );
    return (l >= r) ? (l + 1) : (r + 1);
}

引数は、現在注目している節と、現時点での高さです。初回の呼び出し時には、根と 0 を渡すということになります。

関数内でしていることは、左の子と、右の子を新たな注目節として再帰呼び出しを行い、返ってきた値が大きい方を採用して、自分の高さを加算して返すというものです。

問題② 🔗

問題②　幅優先探索による走査を行う関数を実装してください。


少し難しかったでしょうか。二分木の幅優先探索は、キュー（第６章）を利用すると奇麗に実装できます。

ということで、まずキューを用意します。コードライブラリに int型のキューがあるので、これを持ってきて、int型の部分を二分木の節のポインタ型 (struct Node_tag*型) に置き換えます。

// ppps_node_queue.h

#ifndef PPPS_NODE_QUEUE_H_INCLUDED
#define PPPS_NODE_QUEUE_H_INCLUDED

#include <stdbool.h>

/*
    キュー型
*/
typedef struct PPPSNodeQueue_tag* PPPSNodeQueue;


/*
    キューを作る

    引数：
        size:   格納できる要素数
    戻り値：
        作成されたキュー。
        使い終わったら、ppps_node_queue_delete関数に渡して削除する。
*/
PPPSNodeQueue ppps_node_queue_create(size_t size);

/*
    キューを削除する

    引数：
        queue:  キュー
*/
void ppps_node_queue_delete(PPPSNodeQueue queue);

/*
    キューに要素を入れる

    引数：
        queue:  キュー
        value:  入れる要素
*/
void ppps_node_queue_enqueue(PPPSNodeQueue queue, struct Node_tag* value);

/*
    キューから要素を取り出す

    引数：
        queue:  キュー
    戻り値：
        取り出された要素
*/
struct Node_tag* ppps_node_queue_dequeue(PPPSNodeQueue queue);

/*
    キューが空かどうか調べる

    引数：
        queue:  キュー
    戻り値：
        キューが空であれば true を返し、空でなければ false を返す。
*/
bool ppps_node_queue_is_empty(PPPSNodeQueue queue);


#endif
// ppps_node_queue.c

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "ppps_node_queue.h"

static size_t get_next_index(PPPSNodeQueue queue, size_t index);
static void* xmalloc(size_t size);


struct PPPSNodeQueue_tag {
    struct Node_tag** data;    // 要素を格納する動的配列
    size_t            size;    // data の要素数
    size_t            front;   // 先頭の要素の位置
    size_t            tail;    // 末尾の要素の位置
};


/*
    キューを作る
*/
PPPSNodeQueue ppps_node_queue_create(size_t size)
{
    // front == tail を空の状態にしようとすると、配列全体を使い切った状態を作れない。
    // そこで、指定された size を +1 して、１つ余分に領域を確保しておく。
    size += 1;

    struct PPPSNodeQueue_tag* queue = xmalloc( sizeof(struct PPPSNodeQueue_tag) );
    queue->data  = xmalloc( sizeof(struct Node_tag*) * size );
    queue->size  = size;
    queue->front = 0;
    queue->tail  = 0;

    return queue;
}

/*
    キューを削除する
*/
void ppps_node_queue_delete(PPPSNodeQueue queue)
{
    free( queue->data );
    free( queue );
}

/*
    キューに要素を入れる
*/
void ppps_node_queue_enqueue(PPPSNodeQueue queue, struct Node_tag* value)
{
    assert( get_next_index(queue, queue->tail) != queue->front );

    queue->data[queue->tail] = value;

    // 次に要素を入れるときに使う位置を求める
    // リングバッファ構造なので、単純に +1 するだけではダメ
    queue->tail = get_next_index( queue, queue->tail );
}

/*
    キューから要素を取り出す
*/
struct Node_tag* ppps_node_queue_dequeue(PPPSNodeQueue queue)
{
    assert( !ppps_node_queue_is_empty(queue) );

    struct Node_tag* pop_value = queue->data[queue->front];

    // 先頭から要素が１つ取り出されるので、先頭位置を更新する
    // リングバッファ構造なので、単純に +1 するだけではダメ
    queue->front = get_next_index( queue, queue->front );

    return pop_value;
}

/*
    キューが空かどうか調べる
*/
bool ppps_node_queue_is_empty(PPPSNodeQueue queue)
{
    return queue->front == queue->tail;
}


/*
    １つ後ろの添字を取得する
*/
size_t get_next_index(PPPSNodeQueue queue, size_t index)
{
    return (index + 1) % queue->size;
}

/*
    エラーチェック付きの malloc関数
*/
void* xmalloc(size_t size)
{
    void* p = malloc( size );
    if( p == NULL ){
        fputs( "メモリ割り当てに失敗しました。", stderr );
        exit( EXIT_FAILURE );
    }
    return p;
}

ほとんど機械的に、int → struct Node_tag* に置き換えただけです。これを使えば、二分木の幅優先探索は次のように実装できます。

//main.c

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

#define SIZE_OF_ARRAY(array)    (sizeof(array)/sizeof(array[0]))


// 二分木
struct Node_tag {
    int                   value;
    struct Node_tag*      left;
    struct Node_tag*      right;
};
typedef struct Node_tag* BinaryTree;


static BinaryTree create_binary_tree(void);
static void delete_binary_tree(BinaryTree tree);
static void breadth_first(BinaryTree tree);



int main(void)
{
    BinaryTree tree = create_binary_tree();

    breadth_first( tree );

    delete_binary_tree( tree );

    return 0;
}

/*
    二分木を作成

    ここでは、
             0
            / \
           1   6
          / \
         2   3
            / \
           4   5

    という形の二分木を作っている。
*/
BinaryTree create_binary_tree(void)
{
    BinaryTree node[7];

    for( size_t i = 0; i < SIZE_OF_ARRAY(node); ++i ){
        node[i] = malloc( sizeof(struct Node_tag) );
        node[i]->value = i;
    }

    node[0]->left = node[1];
    node[0]->right = node[6];

    node[1]->left = node[2];
    node[1]->right = node[3];

    node[2]->left = NULL;
    node[2]->right = NULL;

    node[3]->left = node[4];
    node[3]->right = node[5];

    node[4]->left = NULL;
    node[4]->right = NULL;

    node[5]->left = NULL;
    node[5]->right = NULL;

    node[6]->left = NULL;
    node[6]->right = NULL;

    return node[0];
}

/*
    二分木を削除
*/
void delete_binary_tree(BinaryTree tree)
{
    if( tree == NULL ){
        return;
    }

    delete_binary_tree( tree->left );
    delete_binary_tree( tree->right );
    free( tree );
}

/*
    幅優先探索でトラバース
*/
void breadth_first(BinaryTree tree)
{
    if( tree == NULL ){
        return;
    }

    PPPSNodeQueue queue = ppps_node_queue_create( 8 );

    // 根をキューへ登録
    ppps_node_queue_enqueue( queue, &tree[0] );

    // キューに何か入っている間は繰り返す
    while( !ppps_node_queue_is_empty(queue) ){

        // キューから取り出して、その値を出力
        struct Node_tag* node = ppps_node_queue_dequeue( queue );
        printf( "%d\n", node->value );

        // 左の子があれば、キューへ追加
        if( node->left != NULL ){
            ppps_node_queue_enqueue( queue, node->left );
        }

        // 右の子があれば、キューへ追加
        if( node->right != NULL ){
            ppps_node_queue_enqueue( queue, node->right );
        }
    }

    ppps_node_queue_delete( queue );
}

実行結果：

0
1
6
2
3
4
5

手順としては、まず根をキューへ追加します。その後は、キューから１つ取り出し、その値を書き出します。また、その取り出された要素が子を持っていたら、左の子、右の子の順番でキューへ追加します。

もし、子があればキューは空にはならないので、キューから取り出す手順まで戻って、同じことを繰り返します。


参考リンク 🔗


更新履歴 🔗

　SIZE_OF_ARRAYマクロの定義を修正。

≪さらに古い更新履歴≫

　サンプルプログラムで、ファイルスコープでよい関数に static を付加。

　問題②のプログラムがコンパイルできない状態になっていたのを修正。

　新規作成。


第７章のメインページへ

アルゴリズムとデータ構造編のトップページへ

Programming Place Plus のトップページへ

はてなブックマーク に保存 Pocket に保存 Facebook でシェア
X で ポスト／フォロー LINE で送る noteで書く
rss1.0 取得ボタン RSS 管理者情報 プライバシーポリシー
先頭へ戻る