バイナリツリーの基本概念

バイナリツリーは計算機科学における重要なデータ構造であり、多くのアルゴリズムでスタックを用いて実装されます。

バイナリツリーの分類

完全二分木 (Full Binary Tree)

すべてのノードが0個または2個の子ノードを持ち、すべての葉ノードが同じ深さにある二分木を完全二分木と呼びます。深さkの完全二分木は2^k-1個のノードを持ちます。

完全二分木 (Complete Binary Tree)

最下層を除くすべての層が完全に埋まっており、最下層のノードが左詰めで配置されている二分木です。ヒープデータ構造の基礎となります。

二分探索木 (Binary Search Tree)

各ノードが以下の性質を持つ順序付きツリーです：

• 左部分木のすべてのノードの値は親ノードの値より小さい
• 右部分木のすべてのノードの値は親ノードの値より大きい
• 左右の部分木もそれぞれ二分探索木である

平衡二分探索木 (AVL Tree)

左右の部分木の高さの差が最大1である平衡二分探索木です。C++のmapやsetなどのコンテナはこのデータ構造を基盤としています。

バイナリツリーの表現方法

バイナリツリーは以下の2つの方法で表現できます：

リンク表現

ポインタを使用してノード間の関係を表現する方法で、一般的に広く使用されています。

配列表現

配列を使用してツリーを表現する方法で、親ノードのインデックスがiの場合：

• 左の子ノード：2*i + 1
• 右の子ノード：2*i + 2

バイナリツリーの走査方法

深さ優先探索 (Depth-First Search)

• 先行順走査 (Pre-order): 根 → 左 → 右
• 中間順走査 (In-order): 左 → 根 → 右
• 後行順走査 (Post-order): 左 → 右 → 根

幅優先探索 (Breadth-First Search)

• レベル順走査: 階層ごとに左から右へ

バイナリツリーのデータ構造定義

struct BinaryNode {
    int value;
    BinaryNode* leftChild;
    BinaryNode* rightChild;
    BinaryNode(int x) : value(x), leftChild(nullptr), rightChild(nullptr) {}
};

再帰的走査アルゴリズム

再帰実装の三要素

1. 関数パラメータと戻り値の定義: 再帰処理で必要なパラメータと戻り値の型を明確にします
2. 終了条件の設定: 再帰が終了する条件を設定し、スタックオーバーフローを防止します
3. 単層再帰ロジックの確立: 各再帰層で実行する処理を定義します

先行順走査の実装

class PreorderSolution {
public:
    void traversePreorder(BinaryNode* currentNode, vector<int>& output) {
        if (currentNode == nullptr) return;
        output.push_back(currentNode->value);     // 根
        traversePreorder(currentNode->leftChild, output);  // 左
        traversePreorder(currentNode->rightChild, output); // 右
    }
    
    vector<int> preorderTraversal(BinaryNode* root) {
        vector<int> traversalResult;
        traversePreorder(root, traversalResult);
        return traversalResult;
    }
};

中間順走査の実装

void traverseInorder(BinaryNode* currentNode, vector<int>& output) {
    if (currentNode == nullptr) return;
    traverseInorder(currentNode->leftChild, output);  // 左
    output.push_back(currentNode->value);            // 根
    traverseInorder(currentNode->rightChild, output); // 右
}

後行順走査の実装

void traversePostorder(BinaryNode* currentNode, vector<int>& output) {
    if (currentNode == nullptr) return;
    traversePostorder(currentNode->leftChild, output);   // 左
    traversePostorder(currentNode->rightChild, output);  // 右
    output.push_back(currentNode->value);               // 根
}

反復的走査アルゴリズム

先行順走査（反復法）

class IterativePreorder {
public:
    vector<int> preorderTraversal(BinaryNode* root) {
        stack nodeStack;
        vector<int> result;
        if (root == nullptr) return result;
        
        nodeStack.push(root);
        while (!nodeStack.empty()) {
            BinaryNode* current = nodeStack.top();
            nodeStack.pop();
            result.push_back(current->value);
            if (current->rightChild) nodeStack.push(current->rightChild);
            if (current->leftChild) nodeStack.push(current->leftChild);
        }
        return result;
    }
};

中間順走査（反復法）

class IterativeInorder {
public:
    vector<int> inorderTraversal(BinaryNode* root) {
        vector<int> result;
        stack nodeStack;
        BinaryNode* current = root;
        
        while (current != nullptr || !nodeStack.empty()) {
            if (current != nullptr) {
                nodeStack.push(current);
                current = current->leftChild;
            } else {
                current = nodeStack.top();
                nodeStack.pop();
                result.push_back(current->value);
                current = current->rightChild;
            }
        }
        return result;
    }
};

後行順走査（反復法）

class IterativePostorder {
public:
    vector<int> postorderTraversal(BinaryNode* root) {
        stack nodeStack;
        vector<int> result;
        if (root == nullptr) return result;
        
        nodeStack.push(root);
        while (!nodeStack.empty()) {
            BinaryNode* current = nodeStack.top();
            nodeStack.pop();
            result.push_back(current->value);
            if (current->leftChild) nodeStack.push(current->leftChild);
            if (current->rightChild) nodeStack.push(current->rightChild);
        }
        reverse(result.begin(), result.end());
        return result;
    }
};