木構造①

備忘録

木構造とは，階層的なデータを表現するための非線形データ構造．
例）二分木，二分探索木，ヒープなど．．．

プログラミングで木構造を表現する場合は，基本的にはノード（木構造内のデータ）を表現する構造体（クラス）と木構造を扱うクラスを作成する．

C++での二分木の実装例は以下のようになる

struct Node
{
    int data;//データそのもの
    Node* left;//左の子ノードへのポインタ
    Node* right;//右の子ノードへのポインタ
};

木構造の操作としては大きく４つある．
１．探索
２．挿入
３．削除
４．走査

木構造はその構造上，操作が再起的になるので．，ヘルパー関数を用いて実装する．

class BinarySearchTree
{
    private:
        Node* root;//根ノードへのポインタ
       
        // ヘルパー関数（再帰的な処理のために内部的に使用）

        // ノードを挿入するヘルパー関数
        Node* insertNode(Node* current, int val) {
            if (current == nullptr) {
                return new Node(val); // 新しいノードを作成して返す
            }
            if (val < current->data) {
                current->left = insertNode(current->left, val); 
                // 左のサブツリーに挿入
            } 
            else if (val > current->data) {
                current->right = insertNode(current->right, val); 
                // 右のサブツリーに挿入
            }
            // val == current->data の場合（重複を許可しない場合）は何もしない
            return current; // 更新された現在のノードを返す
        }

        // ノードを探索するヘルパー関数
        Node* searchNode(Node* current, int val) const {
            if (current == nullptr || current->data == val) {
                return current; // 見つかったか、または木がない（見つからなかった）
            }
            if (val < current->data) {
                 // 左のサブツリーを探索
                return searchNode(current->left, val); 
               
            } 
            else {
            // 右のサブツリーを探索
            return searchNode(current->right, val); 
            
            }
        }

        // 通りがけ順走査（昇順表示）のヘルパー関数
        void inorderTraversal(Node* current) const {
            if (current != nullptr) {
                inorderTraversal(current->left);  // 左の子ツリー
                std::cout << current->data << " "; // 現在のノード
                inorderTraversal(current->right); // 右の子ツリー
            }
        }

        // 帰りがけ順走査（メモリ解放のため）のヘルパー関数
        void postorderDelete(Node* current) {
            if (current != nullptr) {
                postorderDelete(current->left);
                postorderDelete(current->right);
                delete current; // 子を削除してから自身を削除
            }
        }

public:
    // コンストラクタ
    BinarySearchTree() : root(nullptr) {}

    // デストラクタ（メモリリーク防止のために全てのノードを解放）
    ~BinarySearchTree() {
        postorderDelete(root);
    }

    // 公開メソッド（ユーザーが呼び出す）

    // 挿入
    void insert(int val) {
        root = insertNode(root, val);
    }

    // 探索
    bool search(int val) const {
        return searchNode(root, val) != nullptr;
    }

    // 通りがけ順走査の開始
    void printInorder() const {
        inorderTraversal(root);
        std::cout << std::endl;
    }
   
};

本来はまだ削除が必要だが，勉強できていないのでまた次に載せます．