递归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()); 
    } 

}