Java Tree Search

Question

我尝试解决树遍历的问题。我觉得我快要解决这个问题了，但是我还需要更多的线索。

我有两个接口:

public interface Department {
String getName();
String getType();
}

public interface Company extends Department {
List<Department> getDepartments();
}

这就创建了树形结构

我要按类型查找部门列表。

我已经实现了查找单个元素。

public class Concern {
private List<Department> getDepartments;

public Optional<Department> findDepartmentByName(String name) {
return findDepartmentByPredicate(department -> department.getName().equals(name)).findFirst();
}
public List<Department> findDeparmentByType(String type) {
return findDepartmentByPredicate(department -> deparment.getType().equals(type))
.toList();
}
private Stream<Department> findDepartmentByPredicate(Predicate<Department> predicate) {
return department.stream()
.map(department -> department.getMatchingDepartment(predicate))
.filter(Optional::isPresent)
.map(Optional::get);
}
}

我试着用这个函数。

public interface Department {
....
default Optional<Department> getMatchingDepartment(Predicate<Department> predicate) {
if (predicate.test(this)) {
return Optional.of(this);
}
return Optional.empty();
}
}

这是我不知道怎么做的部分。

我尝试在每个列表元素上调用getMatchingDepartment，但它不会遍历所有子元素。

public interface Comapny extends Deparment {
default Optional<Department> getMatchingDepartment(Predicate<Department> predicate) {
return getDepartments().stream()
.map(department -> department.getMatchingDepartment(predicate))
.filter(Optional::isPresent)
.map(Optional::get)
.findFirst();
}

}

可以这样做吗?我需要使用递归吗?

Answer 1

可以使用递归

public List<Department> findDepartmentByType( String type ) {
ArrayList<Department> result = new ArrayList<>();
findDepartmentByTypeImpl(type, getDepartments(), result);
return result;
}
private void findDepartmentByTypeImpl( String type, List<Department> departments, List<Department> result ) {
for (Department current : departments) {
if (type.equals(current.getType())) {
result.add(current);
}
if (current instanceof Company) {
findDepartmentByTypeImpl(type, ((Company) current).getDepartments(), result);
}
}
}

但是也可以使用迭代方法

public List<Department> findDepartmentByType( String type ) {
ArrayList<Department> result = new ArrayList<>();
ArrayList<Department> stack = new ArrayList<>();
stack.addAll(getDepartments());
while (!stack.isEmpty()) {
Department current = stack.remove(stack.size() - 1);
if (type.equals(current.getType())) {
result.add(current);
}
if (current instanceof Company) {
stack.addAll(((Company) current).getDepartments());
}
}
return result;
}

(未经测试，使用风险自负)