递归Java数据结构-创建一个家谱数组

Question

如何创建一个高效的递归函数——它将接受一个输入提要——它可能有1000行长。压缩成一个阵列。递归函数可能需要某种查找，以确定是否有高于当前员工id的经理。

我正在尝试构建一个应用程序，该应用程序可能需要阵列中的整个关系管理树。

我需要找到一个方法，在输入数据提要上创建一个递归函数，将其映射到整理后的输出数组。

//the input data may look something like this
[{
    "employeeId": "A1",
    "managerId": "B1",
    "employeeRole": "Sales0",
    "managerRole": "Sales1"
}, {
    "employeeId": "B1",
    "managerId": "C1",
    "employeeRole": "Sales1",
    "managerRole": "Sales2"
}, {
    "employeeId": "C1",
    "managerId": "D1",
    "employeeRole": "Sales2",
    "managerRole": "Sales3"
}, {
    "employeeId": "D1",
    "managerId": "",
    "employeeRole": "Sales3",
    "managerRole": "Sales4"
}]

//create a final output array like this
[
    "level1id": "A1",
    "level2id": "B1",
    "level3id": "C1",
    "level4id": "D1",
]

我在这个阶段拥有的最基本的pseduo代码类似于这个

void myMethod(String employeeId, String[] rawData, Map < String, String > dataMap) {
    //employeeId -- child id
    //rawData - from feed 
    //dataMap - the array being built to contain ALL relationships from grand child, parent, grandparent.

    getManager(employeeId, rawData) {
        //find the manager of the current employeeid
        //managerData[0] - manager id
        //managerData[1] - manager role
        return managerData;
    }

    managerData = getManager(employeeId, rawData);
    managerId = managerData[0];
    managerRole = managerData[1];
    dataMap.put(managerData[1], managerData[0]);
    // like [{"customerLevel1" : "SKDOL2"}]

    //if there is no manager id - the grandparent manager has been found
    if (managerId !== null)
        return;
    else {
        //this employeeid has a manager above them - loop through again until the grandparent is found (employee id with no manager) 
        myMethod(managerId, rawData, dataMap);
        return;
    }
}

Answer 1

您需要做一些工作来读取数据、解析数据并构建数据结构，但类关系的类似内容看起来接近您应该需要的。

class Person {
    private final String id;
    public Person(String id) {
        this.id = id;
    }
    public String getId() {
        return id;
    }
}
class Employee extends Person {
    private final String managerId;
    public String getManagerId() {
        return managerId;
    }
    public Employee(String id, String managerId ) {
        super(id);
        this.managerId = managerId;
    }
}
class Manager extends Employee {
    private final String role;
    public String getRole() {
        return role;
    }
    public Manager(String id, String managerId, String role ) {
        super(id, managerId);
        this.role = role;
    }
}
/**
 * Use this to look up any person. 
 * 
 * Put ALL employees an managers in here as you read them.
 */
Map<String, Employee> personLookup = new HashMap<>();

Answer 2

我假设您的输入数据格式是json，所以您需要json.jar。

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import org.json.JSONArray;
import org.json.JSONObject;
public class OrgnizationTree {
    HashMap<String, ArrayList<Employee>> jsonDataMap = new HashMap<String, ArrayList<Employee>>();
    HashMap<String, Employee> employeeMap = new HashMap<String, Employee>();
    Employee root;
    public void buildTree(String jsonData) throws Exception {
        JSONArray array = new JSONArray(jsonData);
        for (int i = 0; i < array.length(); i++) {
            JSONObject object = (JSONObject) array.get(i);
            String employeeId = object.get("employeeId").toString();
            String managerId = object.get("managerId").toString();
            if (managerId == null || managerId.isEmpty()) {
                root = new Employee(employeeId, null);
            } else {
                Employee subordinate = new Employee(employeeId);
                if (jsonDataMap.containsKey(managerId)) {
                    jsonDataMap.get(managerId).add(subordinate);
                } else {
                    ArrayList<Employee> subordinates = new ArrayList<Employee>();
                    subordinates.add(subordinate);
                    jsonDataMap.put(managerId, subordinates);
                }
            }
        }
        for (Employee subordinate : jsonDataMap.get(root.getId())) {
            root.addSubordinate(subordinate);
            subordinate.setManager(root);
            employeeMap.put(root.getId(), root);
            buildSubTree(subordinate);
        }
    }
    public void buildSubTree(Employee manager) {
        List<Employee> subordinates = jsonDataMap.get(manager.getId());
        if (subordinates != null) {
            for (Employee subordinate : subordinates) {
                subordinate.setManager(manager);
                manager.addSubordinate(subordinate);
                buildSubTree(subordinate);
            }
        }
        employeeMap.put(manager.getId(), manager);
    }
    public Employee getManager(String employeeId) {
        Employee employee = employeeMap.get(employeeId);
        Employee manager = employee.getManager();
        return manager;
    }
    public Employee getEmployee(String employeeId) {
        return employeeMap.get(employeeId);
    }
    public Employee getRoot() {
        return root;
    }
    public class Employee {
        String id;
        Employee manager;
        List<Employee> subordinates;
        Integer level;
        Employee(String id, Employee manager) {
            this.id = id;
            this.manager = manager;
            if (manager == null) {
                level = 0;
            } else {
                level = manager.level + 1;
            }
        }
        Employee(String id) {
            this.id = id;
        }
        public void addSubordinate(Employee subordinate) {
            if (subordinates == null) {
                subordinates = new ArrayList<Employee>();
            }
            subordinates.add(subordinate);
        }
        public String getId() {
            return this.id;
        }
        public Employee getManager() {
            return manager;
        }
        public void setManager(Employee manager) {
            this.manager = manager;
            this.level = manager.level + 1;
        }
    }
    public static void main(String[] args) throws Exception {
        String jsonData = "[{'employeeId': 'A1', 'managerId': 'B1'}, {'employeeId': 'B1', 'managerId': 'C1'}, "
                + "{'employeeId': 'C1', 'managerId': 'D1'}, {'employeeId': 'D1', 'managerId': ''}]";
        OrgnizationTree t = new OrgnizationTree();
        t.buildTree(jsonData);
        System.out.println(t.getManager("A1").getId());
        System.out.println(t.getEmployee("A1").getManager().getId());
        System.out.println(t.getRoot().getId());
    }
}