[C言語]二分探索木の走査(行きがけ・通りがけ・帰りがけ)の実装[コード付]

どうもー
今回は前回の続きで二分探索木について扱います！
前回は二分探索木に要素を追加する関数と、要素を探索する関数をメインで扱いました。

今回は二分探索木の要素を走査（全探索）する関数を実装していきます！

二分探索木の走査とは
それぞれの走査の解説
コードの実装
使ってみた
全体のコード

二分探索木の走査とは

走査というのは二分探索木の構造に含まれる全ての要素を辿ることです。
まあ画像処理における、画像の左上から右下まで順に画素を全て辿るラスタ走査などは有名ですね。

しかし二分探索木は全ての要素が一筆書きできるわけではないんですよね。
構造上どこかで走査をジャンプする必要があります。

そのため走査を行う際に一定のルールを決めようってことです。
それが今回実装する

行きがけ順
通りがけ順
帰りがけ順

です！

それぞれの走査の解説

ここからは上の3つの走査がどのようなアルゴリズムであるかを解説していきます。

行きがけ順

行きがけ順では根要素から要素を辿っていき、

現在注目している要素の値を出力
左側の子要素に移動
右側の子要素に移動

していきます。
名前の通りまず要素の値を出力します。
その後左側の子要素に移動して、また1から処理を行います。つまり要素を出力して、左側の子要素に移動するってわけですね。

あれ、そうすると３の右側の子要素に移動の処理っていつ行われるの？

どんどん左側の要素を辿っていくといつか左側に子要素が存在しなくなります。そのタイミングが２の処理が完了したという事です。
そうすると処理が３に移る、つまり右側の要素に移動します。

移った先でまた１から処理を行なって、、、というふうにやっていき全ての要素を訪問したら終了です。ざっくりいうと左に行けるだけ行ったら次は右に、、という風に要素を移動していき、要素に訪問する度に値を出力する感じですね。
その時の出力された値の順番が行きがけ順です！

こちらがイメージです！

通りがけ順

通りがけ順も根要素から要素を辿っていき、

左側の子要素に移動
現在注目している要素の値を出力
右側の子要素に移動

という処理で全ての要素を訪問します。
先ほどの行きがけ順と違い、値の出力処理が真ん中に来ています。
イメージとしては行ける限り左にいく。左の要素に行けなくなったら値を出力して右の要素に移動。そこからまた行けるかぎり左にいき、、って感じですかね。

帰りがけ順

帰りがけ順も根要素から要素を辿っていき、

左側の子要素に移動
右側の子要素に移動
現在注目している要素の値を出力

という処理で全ての要素を訪問します。
こちらは行きがけ順と逆で左に行けるだけ行ったら次は右に、、という風に要素を移動していき、どこにも行けなくなったら要素を出力する感じですね。

コードの実装

まず今回の記事では前回までに作成した二分探索木のコードを用います。
この記事内では特に詳しく解説しないので、もしそこが気になる方がいれば以下の記事を参考にしてください↓

また再帰的な処理を用いますのでもしよかったら以下の記事も参考にしてください！

二分探索木の構造体

typedef struct node {
    int data;
    struct node* left;//親より小さい要素を指す
    struct node* right;//親より大きい要素を指す
} Node;

ざっくり説明すると構造体で二分探索木の各要素を表しています。
その要素より小さい値を持つ要素を指すleftと大きい値を持つrightをポインタ型で持っています。

二分探索木に要素を追加する関数

Node* insert(Node* pNode, int insert_data) {
    if (pNode == NULL) {
        Node* new_node = (Node*)malloc(sizeof(Node));
        new_node->data = insert_data;
        new_node->left = NULL;
        new_node->right = NULL;
        return new_node;
    }
    if (insert_data < pNode->data) {
        pNode->left = insert(pNode->left, insert_data);
    } else if (insert_data > pNode->data) {
        pNode->right = insert(pNode->right, insert_data);
    }
    return pNode;
}

こちらは要素を追加する関数です。
引数のpNodeに追加する二分探索木の根要素へのポインタを、insert_dataに追加したい要素の値を入れることでその要素があるべき位置に挿入されます。

行きがけ順で二分探索木の要素の値を出力する関数

ここからが今回の主題ですね。
といってもコードは簡単です。

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

引数には二分探索木の要素を指すポインタを渡します。
最初にそのポインタがNULLを指していないかを判定します。
指している場合はその要素が存在しないのでreturnで関数の処理を終了させます。

その判定が終われば現在指している要素の値を出力します。

そしてここからが再帰的な処理に入ります。

    preorder(root->left);
    preorder(root->right);

最初にpreoder(root->left)とする事で二分探索木の要素の左側を優先的に進めて行ってます。

preoderが呼び出されるたびにその要素を出力して左側の要素に関数が移動していきます。もし要素が存在しなければ最初のif文に引っかかりその関数の処理が終わります。そうなると一つ前の関数の処理に戻り、今度はpreoder(root->right)の処理が行われる、つまり右側の要素の関数が移動するわけですね。

すべての要素に訪問すると最初に呼び出したpreoderのreturnに辿り着くので全体の処理が終了します。この時に出力されている値の順番が行きがけ順というわけです。

通りがけ順で二分探索木の要素の値を出力する関数

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

見てもらってわかる通り、ほとんど行きがけ順の関数と同じですね。
値を出力するタイミングがinorder(root->left)とinorder(root->right)の間に入る事で、左側の要素を辿れなくなったら値が出力されます。

帰りがけ順で二分探索木の要素の値を出力する関数

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

こちらも同様です。出力のタイミングを最後にする事で帰りがけ順に値が出力されていきます。

使ってみた

実行した結果がこちら

全体のコード

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

typedef struct node {
    int data;
    struct node* left;
    struct node* right;
} Node;

Node* insert(Node* pNode, int insert_data) {
    if (pNode == NULL) {
        Node* new_node = (Node*)malloc(sizeof(Node));
        new_node->data = insert_data;
        new_node->left = NULL;
        new_node->right = NULL;
        return new_node;
    }
    if (insert_data < pNode->data) {
        pNode->left = insert(pNode->left, insert_data);
    } else if (insert_data > pNode->data) {
        pNode->right = insert(pNode->right, insert_data);
    }
    return pNode;
}

void post_order(Node* root) {
    if (root == NULL) {
        return;
    }
    post_order(root->left);
    post_order(root->right);
    printf("%d", root->data);
}

void in_order(Node* root) {
    if (root == NULL) {
        return;
    }
    in_order(root->left);
    printf("%d", root->data);
    in_order(root->right);
}

void pre_order(Node* root) {
    if (root == NULL) {
        return;
    }
    printf("%d", root->data);
    pre_order(root->left);
    pre_order(root->right);
}

int main(void){
    Node* root = NULL;
    root = insert(root, 6);
    root = insert(root, 8);
    root = insert(root, 9);
    root = insert(root, 3);
    root = insert(root, 7);
    root = insert(root, 4);
    root = insert(root, 1);
    root = insert(root, 0);
    root = insert(root, 2);
    root = insert(root, 5);

    printf("\npre＿order: ");
    pre_order(root);
    printf("\nin＿order: ");
    in_order(root);
    printf("\npost＿order: ");
    post_order(root);
    printf("\n");

    return 0;
}