使用Java无法完全递归树形层次结构

Question

使用Java无法完全递归树形层次结构

javaspring-bootrecursiontreespring-data-jpa

6

我创建了一个Spring Boot微服务，它发出HTTP GET请求从MySQL数据库中提取数据（每个节点），该数据在单个基于邻接列表树的表中设置。

我能够获取特定级别节点的子节点，但还需要能够查看所有子节点（即使这需要不同的REST调用和服务方法）。

我在我的技术栈中使用Java 1.8、Spring Boot 1.5.6.RELEASE、JPA和MySQL 5。

pom.xml:

<parent>
    <groupId>org.springframework.boot</groupId>
    <artifactId>spring-boot-starter-parent</artifactId>
    <version>1.5.6.RELEASE</version>
</parent>

<properties>
    <project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
    <project.reporting.outputEncoding>UTF-8</project.reporting.outputEncoding>
    <java.version>1.8</java.version>
</properties>

<dependencies>
    <dependency>
        <groupId>org.springframework.boot</groupId>
        <artifactId>spring-boot-starter-web</artifactId>
    </dependency>

    <dependency>
        <groupId>org.springframework.boot</groupId>
        <artifactId>spring-boot-starter-test</artifactId>
        <scope>test</scope>
    </dependency>

    <dependency>
        <groupId>org.springframework.boot</groupId>
        <artifactId>spring-boot-starter-data-jpa</artifactId>
    </dependency>

    <dependency>
        <groupId>javax.xml.bind</groupId>
        <artifactId>jaxb-api</artifactId>
        <version>2.3.0</version>
    </dependency>

    <dependency>
        <groupId>mysql</groupId>
        <artifactId>mysql-connector-java</artifactId>
        <scope>runtime</scope>
    </dependency>
</dependencies>

Node.java（POJO）：

@Entity
public class Node {

    @Id
    @GeneratedValue(strategy=GenerationType.IDENTITY)
    private Long id;

    @NotNull
    private String name;

    @Column(name = "parent_id")
    private Long parentId;

    // Getters & Setters Omitted for Brevity 
}

NodeRepository：

@Repository
public interface NodeRepository extends JpaRepository<Node, Long> {

    @Query(value = "SELECT * FROM NODE WHERE parent_id = ?", nativeQuery = true)
    List<Node> findNodesByParentId(Long parentId);

    @Query(value = "SELECT * FROM NODE WHERE name = ?", nativeQuery = true)
    Node findByName(String name);
}

我的服务：

public interface MyService {
    List<Node> getHierarchyPerNode(Node node);
    void removeNode(String node);
}

MyServiceImpl：

@Service
public class MyServiceImpl implements MyService {

   @Autowired
   NodeRepository repository;

   @Override
   public List<Node> getHierarchyPerNode(Node node) {
        List<Node> nodes = new ArrayList<>();
        List<Node> children = new ArrayList<>();
        if (node != null) {
            Node aNode = repository.findByName(node.getName());
            nodes.add(aNode);
            Long parentId = aNode.getId();
            children = repository.findNodesByParentId(parentId);

            // Was trying this as recursion but kept throwing an NullPointerException.
            // for (Node child : children) {
            //      return getHierarchyPerNode(child);
            //  }
        }
        if (!children.isEmpty()) {
            return children;
        } 
        else { 
            return nodes;
        }
    }
}

RestController：

@RestController
public class RestController {

    private HttpHeaders headers = null;

    @Autowired
    MyService myService;

    public RestController() {
        headers = new HttpHeaders();
        headers.add("Content-Type", "application/json");
    }

    @RequestMapping(
        value = {"/api/nodes"}, 
        method = RequestMethod.GET, 
        produces = "APPLICATION/JSON"
    )
    public ResponseEntity<Object> getHierarchyPerNode(Node node) {
        if (null == node) {
            return new ResponseEntity<Object>(HttpStatus.NOT_FOUND);
        }
        List<Node> nodes = myService.getHierarchyPerNode(node);

        if (null == nodes) {
            return new ResponseEntity<Object>(HttpStatus.NOT_FOUND);
        }

        return new ResponseEntity<Object>(nodes, headers, HttpStatus.OK);
    }
}

DatabasePopulator（在Spring Boot启动期间使用此选项来填充数据库）：

@Component
public class DatabasePopulator implements ApplicationListener<ContextRefreshedEvent> {

    private final NodeRepository repository;

    public DatabasePopulator(NodeRepository repository) {
        this.repository = repository;
    }

    @Override
    public void onApplicationEvent(ContextRefreshedEvent event) {
        Node root = new Node();
        root.setName("Store");
        root.setParentId(null);
        repository.save(root);

        // Populate Books Node (along with children)
        Node books = new Node();
        books.setName("Books");
        books.setParentId(root.getId());
        repository.save(books);

        Node horror = new Node();
        horror.setName("Horror");
        horror.setParentId(books.getId());
        repository.save(horror);

        Node romance = new Node();
        romance.setName("Romance");
        romance.setParentId(books.getId());
        repository.save(romance);

        Node fantasy = new Node();
        fantasy.setName("Fantasy");
        fantasy.setParentId(books.getId());
        repository.save(fantasy);

        // Populate Coffee Node (along with children)
        Node coffee = new Node();
        coffee.setName("Coffee");
        coffee.setParentId(root.getId());
        repository.save(coffee);

        Node mocha = new Node();
        mocha.setName("Mocha");
        mocha.setParentId(coffee.getId());
        repository.save(mocha);

        Node latte = new Node();
        latte.setName("Latte");
        latte.setParentId(coffee.getId());
        repository.save(latte);

        // Populate show espresso as a child underneath the Latte node.
        Node espresso = new Node();
        espresso.setName("Espresso");
        espresso.setParentId(latte.getId());
        repository.save(espresso);
    }
}

显然，所填充的数据代表了数据库中的这棵树：

Store
|______ Books
        |
        |______Horror
        |
        |______Romance
        |
        |______Fantasy

 |______Coffee
        |
        |______Mocha
        |
        |______Latte
               |
               |_____Espresso

观察 / 问题：

通过我的RestController，调用这个REST端点，我可以获取第一级记录：

http://localhost:8080/myapp/api/nodes?name=Products

然而，它仅提供了第一级（而非 Books & Coffee 和 Latte 下面的子节点）：

[
  {
    "id": 2,
    "name": "Books",
    "parentId": 1
  },
  {
    "id": 6,
    "name": "Coffee",
    "parentId": 1
  }
]

在书籍分类下，不再列出恐怖、浪漫和幻想等子类别，在咖啡分类下，不再将摩卡、拿铁（以及拿铁下的浓缩咖啡）作为子类别。

现在，如果使用parentNode（例如Books），它会显示子级（但仅限第一级）：

http://localhost:8080/myapp/api/nodes?name=Books

JSON响应有效载荷：

[
  {
    "id": 3,
    "name": "Horror",
    "parentId": 2
  },
  {
    "id": 4,
    "name": "Romance",
    "parentId": 2
  },
  {
    "id": 5,
    "name": "Fantasy",
    "parentId": 2
  }
]

尝试列出 Coffee 的所有子元素时：

http://localhost:8080/myapp/api/nodes?name=Coffee

JSON响应有效负载：

[
  {
    "id": 7,
    "name": "Mocha",
    "parentId": 6
  },
  {
    "id": 8,
    "name": "Latte",
    "parentId": 6
  }
]

看，这个没有显示Espresso，必须调用Latte作为父级来显示：

http://localhost:8080/myapp/api/nodes?name=Latte

JSON响应有效载荷：

{
    "id": 9,
    "name": "Espresso",
    "parentId": 8
}

我可以翻译中文。

能否获取特定子级别的节点？

如何使用递归获取所有层级上的节点（我知道这将涉及不同的REST GET调用/ REST终端点）？

需要使用递归来获取所有子级/子层级，但是不知道如何在获取子节点和删除节点时实现。

- PacificNW_Lover

你应该尝试使用“Materialised Path Model”，如Recursive JPA query?中所述。 - Ortomala Lokni

2个回答

2

我建议您像maciej建议的那样实施。

这里有一个逻辑问题。而不是return getHierarchyPerNode(child);，您需要添加节点。

public List<Node> getHierarchyPerNode(Node node) {
        List<Node> nodes = new ArrayList<>();
        List<Node> children = new ArrayList<>();
        if (node != null) {
            Node aNode = repository.findByName(node.getName());
            nodes.add(aNode);
            Long parentId = aNode.getId();
            children = repository.findNodesByParentId(parentId);

            // Was trying this as recursion but kept throwing an NullPointerException.
            if (children != null) {
                for (Node child : children) {
                    List<Node> childList = getHierarchyPerNode(child);
                    if (childList != null && !childList.isEmpty()) {
                        nodes.addAll(childList);
                    }
                }
            }
        }
        return nodes;
    }

- Akash Shah

您不需要手动添加任何子项，因为这些都在同一持久化上下文中运行。node.getChildren() 实际上返回一个代理。在 JPA / Hibernate 中，当您调用懒加载集合的任何方法（例如 size()）时，持久性提供程序会自动加载集合。我已经在 getNodeHierarchy 服务方法上添加了 @Transactional，因为错过了这一点。 - Maciej Kowalski

@Akash Shah，对于这个问题有什么想法吗？https://stackoverflow.com/questions/56549158/how-to-count-the-number-of-intersections/56549430#56549430 - sdrtg ghytui

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Maciej Kowalski · Accepted Answer

不确定为什么您在这里没有充分利用JPA，首先在实体级别上，然后在查询期间使用本地SQL而不是JPQL。

1）如果您按以下方式更改实体：

@Entity
public class Node {

    @Id
    @GeneratedValue(strategy=GenerationType.IDENTITY)
    private Long id;

    @NotNull
    private String name;

    @ManyToOne
    @JoinColumn(name = "parent_id")
    private Node parentNode;

    @OneToMany(mappedBy = "parentNode", 
               cascade = { CascadeType.DELETE, CascadeType.PERSIST} )
    private List<Node> children;
}

2) 然后稍微修改一下你的查询，以使其兼容JPQL：

@Query(value = "select n from Node n inner join n.parentNode p where p.id = ?")
List<Node> findNodesByParentId(Long parentId);

现在，默认情况下，仅会获取顶层节点，因为默认情况下 @OneToMany 关系是懒加载的。

3) 在这一点上，你只需要稍微修改递归方法以遵守更改并获得所需内容：

控制器

@RequestMapping(
    value = {"/api/nodes"}, 
    method = RequestMethod.GET, 
    produces = "APPLICATION/JSON"
)
public ResponseEntity<Object> getNodeHierarchy(Node node) {
    if (null == node) {
        return new ResponseEntity<Object>(HttpStatus.NOT_FOUND);
    }
    List<Node> nodes = myService.getNodeHierarchy(node);

    if (null == nodes) {
        return new ResponseEntity<Object>(HttpStatus.NOT_FOUND);
    }

    return new ResponseEntity<Object>(nodes, headers, HttpStatus.OK);
}

顶层节点检索

 @Override
 @Transactional(readOnly = true)
 public List<Node> getNodeHierarchy(Node inNode){
    Node node = repository.findByName(inNode.getName());

    traverseNodeAndFetchChildren(node);

    return node.getChildren();
 }

递归遍历和提取

public void traverseNodeAndFetchChildren(Node node) {
   int size = node.getChildren().size();

   if(size > 0){
      for(Node childNode: node.getChildren()){
         traverseNodeAndFetchChildren(childNode);
      }
   }       
}

node.getChildren().size() - 这会使持久化上下文懒加载@OneToMany依赖项。

4) 同时，将您的服务方法标记为@Transactional(readOnly = true)也是一个好主意。