二分木の基本的な操作

二分木は、各ノードが最大2つの子ノードを持つ木構造です。この記事では、C言語を用いて二分木の作成、走査、特性の計算、および部分木の交換といった基本的な操作を実装する方法を学びます。

ノードの定義

二分木の各ノードは、データと左右の子ノードへのポインタを持ちます。以下にその構造体を示します。

struct Node {
    char data;
    struct Node* left;
    struct Node* right;
};

木の作成と走査

二分木は、特定の走査順序（例：先行順）に基づいて文字列から再帰的に作成できます。'#'は空のノードを表します。

先行順走査による木の作成

先行順走査（ルート、左部分木、右部分木の順）を使用して木を構築します。入力文字列が空または'#'の場合、NULLポインタを返します。それ以外の場合、新しいノードを作成し、その左と右の子を再帰的に構築します。

Node* createTree(char* s, int* i, int len) {
    if (*i >= len || s[*i] == '#') {
        (*i)++;
        return NULL;
    }
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = s[(*i)++];
    newNode->left = createTree(s, i, len);
    newNode->right = createTree(s, i, len);
    return newNode;
}

中間順走査

中間順走査（左部分木、ルート、右部分木の順）は、ノードを昇順に訪問するのに役立ちます。再帰的なアプローチを使用して実装できます。

void inOrderTraversal(Node* node) {
    if (node != NULL) {
        inOrderTraversal(node->left);
        printf("%c", node->data);
        inOrderTraversal(node->right);
    }
}

木の特性の計算

二分木の深さ、ノードの総数、および葉ノードの数を計算する関数を実装します。

木の深さの計算

木の深さは、ルートから最も遠い葉ノードまでのエッジの数です。再帰的に左右の部分木の深さを計算し、その最大値に1を加えます。

int calculateDepth(Node* node) {
    if (node == NULL) {
        return 0;
    }
    int leftDepth = calculateDepth(node->left);
    int rightDepth = calculateDepth(node->right);
    return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1;
}

ノードの総数の計算

木内のノードの総数は、左右の部分木のノード数にルートノードを加えたものです。

int countNodes(Node* node) {
    if (node == NULL) {
        return 0;
    }
    return 1 + countNodes(node->left) + countNodes(node->right);
}

葉ノードの数の計算

葉ノードは子を持たないノードです。再帰的に左右の部分木を探索し、子を持たないノードをカウントします。

int countLeaves(Node* node) {
    if (node == NULL) {
        return 0;
    }
    if (node->left == NULL && node->right == NULL) {
        return 1;
    }
    return countLeaves(node->left) + countLeaves(node->right);
}

部分木の交換

二分木の左右の部分木を交換する操作は、再帰的および非再帰的な（スタックを使用した）方法で実装できます。

再帰による部分木の交換

各ノードについて、その左右の子ポインタを交換し、その後、左右の部分木に対して同じ操作を再帰的に適用します。

Node* swapSubtreesRecursive(Node* node) {
    if (node == NULL) {
        return NULL;
    }
    // 左右の子を交換
    Node* temp = node->left;
    node->left = node->right;
    node->right = temp;
    // 再帰的に部分木を交換
    swapSubtreesRecursive(node->left);
    swapSubtreesRecursive(node->right);
    return node;
}

スタックによる非再帰的な部分木の交換

スタックを使用して、ノードを反復的に処理し、左右の子を交換します。これは、再帰の深さ制限を回避するのに役立ちます。

Node* swapSubtreesIterative(Node* root) {
    if (root == NULL) {
        return NULL;
    }
    std::stack nodeStack;
    nodeStack.push(root);
    
    while (!nodeStack.empty()) {
        Node* currentNode = nodeStack.top();
        nodeStack.pop();
        
        // 左右の子を交換
        Node* temp = currentNode->left;
        currentNode->left = currentNode->right;
        currentNode->right = temp;
        
        // 子ノードをスタックにプッシュ
        if (currentNode->left != NULL) {
            nodeStack.push(currentNode->left);
        }
        if (currentNode->right != NULL) {
            nodeStack.push(currentNode->right);
        }
    }
    return root;
}

レベル順走査

レベル順走査（BFS）は、ルートレベルから始まり、各レベルのノードを左から右に訪問します。キューを使用して実装します。

void levelOrderTraversal(Node* root) {
    if (root == NULL) {
        return;
    }
    std::queue nodeQueue;
    nodeQueue.push(root);
    
    while (!nodeQueue.empty()) {
        Node* currentNode = nodeQueue.front();
        nodeQueue.pop();
        printf("%c", currentNode->data);
        
        if (currentNode->left != NULL) {
            nodeQueue.push(currentNode->left);
        }
        if (currentNode->right != NULL) {
            nodeQueue.push(currentNode->right);
        }
    }
}