Java 再帰処理を使い階層構造を階層順にソートする方法

Javaで再帰処理を使用して、階層構造があるデータを階層の順番にソートする方法をご紹介します。

とあるプロジェクトでMySQLを使用しているのですが、バージョン8では階層をいい感じに扱うことができるのですが、バージョンが5なので階層をSQLで扱うことが困難だったので、データ取得後のJavaで階層構造をいい感じに処理することにしようと思ったのがきっかけです。

階層構造があるデータ

今回は以下のような階層があるデータを使用します。

class Department {

    Department(String dc, int dl, String hd, String dn) {
        this.departmentCd = dc;
        this.departmentLevel = dl;
        this.higherHierarchyDepartmentCd = hd;
        this.departmentName = dn;
    };

    private String departmentCd;    
    private int departmentLevel;
    private String higherHierarchyDepartmentCd;
    private String departmentName;

    public String getDepartmentCd() {
        return departmentCd;
    }

    public int getDepartmentLevel() {
        return departmentLevel;
    }

    public String getHigherHierarchyDepartmentCd() {
        return higherHierarchyDepartmentCd;
    }

    public String getDepartmentName() {
        return departmentName;
    }

    @Override
    public String toString() {
        return String.format("組織コード:%s 組織階層:%d 上位組織コード:%s 組織名:%s", this.departmentCd, this.departmentLevel, this.higherHierarchyDepartmentCd, this.departmentName);
    }

}

各組織データには自分の階層と、上位階層が存在する場合の上位組織の組織コードを保持しています。

この組織データを適当に生成して、リストに追加したものが以下です。

import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;


public class Saiki {

    public static void main(String[] args) {
        List<Department> departmentList = new LinkedList<>();
        departmentList.add(new Department("001", 1, "", "会社"));
        departmentList.add(new Department("003", 2, "001", "部1"));
        departmentList.add(new Department("002", 2, "001", "部2"));
        departmentList.add(new Department("004", 2, "001", "部3"));
        departmentList.add(new Department("006", 3, "003", "課1"));
        departmentList.add(new Department("005", 3, "003", "課2"));

        departmentList.forEach(System.out::println);
    }
}

以下の結果になります。

組織コード:001 組織階層:1 上位組織コード: 組織名:会社
組織コード:003 組織階層:2 上位組織コード:001 組織名:部1
組織コード:002 組織階層:2 上位組織コード:001 組織名:部2
組織コード:004 組織階層:2 上位組織コード:001 組織名:部3
組織コード:006 組織階層:3 上位組織コード:003 組織名:課1
組織コード:005 組織階層:3 上位組織コード:003 組織名:課2

今回の目標は組織階層、組織コードの順でソートをしたいですが、自分に紐づく下位の組織がある場合は、その下位の組織が次に来るようにします。

つまり、以下のような結果になることを目指します。

組織コード:001 組織階層:1 上位組織コード: 組織名:会社
組織コード:002 組織階層:2 上位組織コード:001 組織名:部2
組織コード:003 組織階層:2 上位組織コード:001 組織名:部1
組織コード:005 組織階層:3 上位組織コード:003 組織名:課2
組織コード:006 組織階層:3 上位組織コード:003 組織名:課1
組織コード:004 組織階層:2 上位組織コード:001 組織名:部3

組織階層、組織コードの順でソートをすると、組織コード003の次は組織コード004になりますが、下位の組織が存在する場合に次に来るようにするという条件を守ると、

組織コード003の次に、上司組織コードが003である、組織コード005,006のデータが先にくるようになります。

この様なケースでは、階層の数がどこまであるか分からないので、何回ループすればいいかが分かりません。こんなときは再帰処理を使用するといい感じに書くことができます。

再帰処理で階層順にデータをソートする

以下のコードでは再帰処理を使用して、階層順にデータをソートしています。

import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;


public class Saiki {

    public static void main(String[] args) {
        List<Department> departmentList = new LinkedList<>();
        departmentList.add(new Department("001", 1, "", "会社"));
        departmentList.add(new Department("003", 2, "001", "部1"));
        departmentList.add(new Department("002", 2, "001", "部2"));
        departmentList.add(new Department("004", 2, "001", "部3"));
        departmentList.add(new Department("006", 3, "003", "課1"));
        departmentList.add(new Department("005", 3, "003", "課2"));

        List<Department> firstHierarchyList = departmentList.stream()
            .filter(d -> d.getDepartmentLevel() == 1)
            .collect(Collectors.toCollection(LinkedList::new));

        List<Department> hierarchySortedList = new LinkedList<>();

        for (Department department : firstHierarchyList){
            sortHierarchy(hierarchySortedList, departmentList, department, 1);      
        }
         
        hierarchySortedList.forEach(System.out::println);
    }

    public static void sortHierarchy(
        List<Department> hierarchySortedList, List<Department> sortedList,
            Department department, int departmentLevel){
        hierarchySortedList.add(department);
        int nextDepartmentLevel = departmentLevel + 1;
        List<Department> nextHierarchyList = sortedList.stream()
            .filter(d -> d.getDepartmentLevel() == nextDepartmentLevel)
            .filter(d -> d.getHigherHierarchyDepartmentCd().equals(department.getDepartmentCd()))
            .sorted(Comparator.comparing(Department::getDepartmentCd))
            .collect(Collectors.toCollection(LinkedList::new));
        if (nextHierarchyList.size() != 0) {
            for (Department nextDepartment : nextHierarchyList){
                sortHierarchy(hierarchySortedList, sortedList, nextDepartment, nextDepartmentLevel);      
            }
        }
    }
}

結果は以下の通り、期待した結果を取得することができました。

組織コード:001 組織階層:1 上位組織コード: 組織名:会社
組織コード:002 組織階層:2 上位組織コード:001 組織名:部2
組織コード:003 組織階層:2 上位組織コード:001 組織名:部1
組織コード:005 組織階層:3 上位組織コード:003 組織名:課2
組織コード:006 組織階層:3 上位組織コード:003 組織名:課1
組織コード:004 組織階層:2 上位組織コード:001 組織名:部3

再帰処理を書いたメソッドであるsortHierarchyで、まずは自分をソート済みリストに追加したうえで、自分の組織を上位組織とする次の階層の組織一覧を取得します。

その組織一覧を再び、sortHierarchyに放り込むことで、下の階層を1つずつ見ていきます。

次の階層の組織一覧が取得できなくなったら、処理は終了します。

このように再帰処理を書くことで、階層を持つデータをキレイに処理することができます。

階層は3階層までのようなルールが存在しない限り、階層がある限り走査する必要が出てきます。その様な場合は再帰処理がおすすめです。