C++で二分木における最長の葉から葉へのパスを出力するプログラム

このチュートリアルでは、与えられた二分木(binary tree)において、ある葉ノードから別の葉ノードまでの最長パスを出力するプログラムについて解説します。

言い換えると、二分木の直径(diameter)に含まれるすべてのノードを出力することが目的です。ここでいう直径(または幅)とは、ある端のノードからもう一方の端のノードまでの最長パス上に存在するノードの数として定義されます。

解決のアプローチ

この問題は、以下の手順で解くことができます。

1. 高さ関数による直径の計算: 各ノードに対して「左部分木の高さ + 右部分木の高さ + 1」を評価し、これが現在の最大値より大きければ、そのノードを直径の中間ノードとして記録します。
2. 左側の最長パスを探索: 記録した中間ノードの左部分木内で、指定された長さに一致する葉までのパスを見つけます。
3. 右側の最長パスを探索: 同様に右部分木内でも最長パスを見つけます。
4. 結果の出力: 左部分木のノード → 根ノード → 右部分木のノード の順に出力することで、直径上のすべてのノードが表示されます。

プログラム例

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    Node *left, *right;
};
struct Node* create_node(int data){
    struct Node* node = new Node;
    node->data = data;
    node->left = node->right = NULL;
    return (node);
}
int tree_height(Node* root, int& ans, Node*(&k), int& lh, int& rh, int& f){
    if (root == NULL)
        return 0;
    int left_tree_height = tree_height(root->left, ans, k, lh, rh, f);
    int right_tree_height = tree_height(root->right, ans, k, lh, rh, f);
    if (ans < 1 + left_tree_height + right_tree_height){
        ans = 1 + left_tree_height + right_tree_height;
        k = root;
        lh = left_tree_height;
        rh = right_tree_height;
    }
    return 1 + max(left_tree_height, right_tree_height);
}
void print_roottonode(int ints[], int len, int f){
    int i;
    if (f == 0){
        for (i = len - 1; i >= 0; i--) {
            printf("%d ", ints[i]);
        }
    }
    else if (f == 1) {
        for (i = 0; i < len; i++) {
            printf("%d ", ints[i]);
        }
    }
}
void print_pathr(Node* node, int path[], int pathLen, int max, int& f){
    if (node == NULL)
    return;
    path[pathLen] = node->data;
    pathLen++;
    if (node->left == NULL && node->right == NULL) {
        if (pathLen == max && (f == 0 || f == 1)) {
            print_roottonode(path, pathLen, f);
            f = 2;
        }
    }
    else {
        print_pathr(node->left, path, pathLen, max, f);
        print_pathr(node->right, path, pathLen, max, f);
    }
}
void calc_diameter(Node* root){
    if (root == NULL)
        return;
    int ans = INT_MIN, lh = 0, rh = 0;
    int f = 0;
    Node* k;
    int tree_height_of_tree = tree_height(root, ans, k, lh, rh, f);
    int lPath[100], pathlen = 0;
    print_pathr(k->left, lPath, pathlen, lh, f);
    printf("%d ", k->data);
    int rPath[100];
    f = 1;
    print_pathr(k->right, rPath, pathlen, rh, f);
}
int main(){
    struct Node* root = create_node(12);
    root->left = create_node(22);
    root->right = create_node(33);
    root->left->left = create_node(45);
    root->left->right = create_node(57);
    root->left->right->left = create_node(26);
    root->left->right->right = create_node(76);
    root->left->left->right = create_node(84);
    root->left->left->right->left = create_node(97);
    calc_diameter(root);
    return 0;
}

コードのポイント

• tree_height() 関数は再帰的に各ノードの左右の高さを求めながら、同時に最大の直径とその中間ノード k を更新します。
• print_pathr() 関数は、中間ノードから葉までのパスを配列に記録し、長さが一致した時点で出力を行います。
• フラグ変数 f を使うことで、左側のパスは逆順(葉→根方向)、右側のパスは正順(根→葉方向)に出力され、全体として一本の連続した経路になります。

出力

97 84 45 22 57 26

このように、直径に相当する「97 → 84 → 45 → 22 → 57 → 26」という最長の葉から葉へのパスが出力されます。