C++で葉ノードが循環双方向連結リストとして接続された特別な二分木の高さを求める方法

特別な二分木とは

本記事で扱うのは、葉ノード（リーフノード）が循環双方向連結リストとして接続された特別な二分木です。この構造では、最も左側にある葉ノードの左ポインタが連結リストの「前（previous）」ポインタとして機能し、右ポインタが「次（next）」ポインタとして機能します。このような木の高さを求める方法を解説します。

高さを求めるアルゴリズムの考え方

高さを求める基本的な戦略は、通常の二分木の場合と同様です。各ノードについて左部分木と右部分木の高さを再帰的に計算し、そのノードの高さを「2つの子ノードの高さの最大値 + 1」として決定します。

ただし、この問題では葉ノードが循環双方向連結リストの要素となっている点がポイントです。そのため、あるノードが葉ノードかどうかを判定する際には、以下の2つの条件をチェックします。

• そのノードの左の子の右ポインタが、そのノード自身を指していること
• そのノードの右の子の左ポインタが、そのノード自身を指していること

この2つの条件が両方とも成立していれば、そのノードは二分木の葉であると同時に、循環双方向連結リストの一部であると判断できます。

C++による実装例

#include<iostream>
using namespace std;
class Node {
    public:
        int data;
        Node *left, *right;
};
bool isLeafNode(Node* node) {
    return node->left && node->left->right == node && node->right && node->right->left == node;
}
int findHeight(Node* node) {
    if (node == NULL)
        return 0;
    if (isLeafNode(node))
        return 1;
    return 1 + max(findHeight(node->left), findHeight(node->right));
}
Node* getNode(int data) {
    Node* node = new Node;
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}
int main() {
    Node* root = getNode(1);
    root->left = getNode(2);
    root->right = getNode(3);
    root->left->left = getNode(4);
    root->left->right = getNode(5);
    root->left->left->left = getNode(6);
    Node *L1 = root->left->left->left;
    Node *L2 = root->left->right;
    Node *L3 = root->right;
    L1->right = L2, L2->right = L3, L3->right = L1;
    L3->left = L2, L2->left = L1, L1->left = L3;
    cout << "Height of tree is: " << findHeight(root);
}

コードの解説

isLeafNode() 関数は、前述の条件を使ってノードが葉かどうかを判定します。findHeight() 関数は再帰的に木をたどり、NULLノードの高さを0、葉ノードの高さを1として返し、それ以外のノードについては左右の部分木の高さの最大値に1を加えた値を返します。

main() 関数では、まず通常の二分木を構築した後、3つの葉ノード（L1、L2、L3）の左右ポインタを書き換えることで、循環双方向連結リストを形成しています。

出力結果

Height of tree is: 4

この例では、根ノードから最も深い葉ノードまでの経路が「1 → 2 → 4 → 6」となり、木の高さは4と計算されます。葉ノードが連結リストとして接続されていても、適切に葉の判定を行うことで、通常の二分木と同じ要領で高さを求められることがわかります。