使用递归方式过滤树结构

使用递归方式过滤树结构

本文介绍使用递归方法过滤树数据结构。

需求

给定叶子节点，过滤树。下面通过示例说明。

示例数据结构：

         0
       / |  \
      1  2   3
    /  \ |  / \
   4   5 6  7  8

给定条件为：4 和 6，如果所有子节点都不符合条件，对应父节点也不显示。

过滤后的树为：

         0
       / | 
      1  2 
    /    | 
   4     6  

定义数据结构

定义TreeNode 类，其包括子节点集合：

import ;
import ;
import ;
import ;

import ;

@Getter
@Setter
@Builder
@ToString
public class TreeNode {
    private String nodeName;
    private String nodeCode;

    private List<TreeNode> children;
}

实现过滤算法

在TreeNode 类中定义静态方法实现过滤算法：

    public static List<TreeNode> filterNode(TreeNode treeNode, List<String> targetNode) {

        List<TreeNode> nodes = ();
        List<TreeNode> newNodes = ();
        List<TreeNode> tagNodes = ();

        for (TreeNode node : nodes) {
            if ((())) {
                (node);
            }
            if (() != null && ().size() > 0) {
                List<TreeNode> retNodes = filterNode(node, targetNode);
                if (() > 0) {
                    (retNodes);
                } else {
                    // 没有子节点情况
                    (null);
                    // 标记,循环结束后删除
                    (node);
                }
            }
        }
        (tagNodes);
        return newNodes;
    }

循环当前节点下所有子节点，如何该子节点符合条件加入newNodes；如果该子节点还有子节点集合，则递归调用自身；所有子节点循环结束后，判断其返回的newNodes集合，如何不空，替换其子节点集合，否则，删除子节点集合，并标记当前节点。当前循环结束后，删除标记的节点，返回当前节点的子节点newNodes集合。

测试

import ;
import ;
import ;
import org.;
import org.;

import ;

public class FilterTreeNode {
    private Logger logger = ();
    private TreeNode node0;
    private List<String> targetNode = ("B1","C1");

    @Before
    public void init(){
        node0 = ().nodeCode("0").nodeName("A").build();
        TreeNode node1 = ().nodeCode("1").nodeName("B").build();
        TreeNode node2 = ().nodeCode("2").nodeName("C").build();
        TreeNode node3 = ().nodeCode("3").nodeName("D").build();

        TreeNode node4 = ().nodeCode("4").nodeName("B1").build();
        TreeNode node5 = ().nodeCode("5").nodeName("B2").build();
        TreeNode node6 = ().nodeCode("6").nodeName("C1").build();
        TreeNode node7 = ().nodeCode("7").nodeName("D1").build();
        TreeNode node8 = ().nodeCode("8").nodeName("D2").build();

        ((node4,node5));
        ((node6));
        ((node7,node8));

        ((node1,node2,node3));
    }

    @Test
    public void filterTest(){
        ("before filter node0: {}",node0);
        (node0, targetNode);
        if (().size() == 0){
            node0 = null;
        }
        ("after filter node0: {}",node0);
    }

首先定义测试数据结构，然后调用()方法，最后判断其返回值，并决定是否修改node0子节点或自身。
测试结果如下：

INFO FilterTreeNode - before filter node0: TreeNode(nodeName=A, nodeCode=0, children=[TreeNode(nodeName=B, nodeCode=1, children=[TreeNode(nodeName=B1, nodeCode=4, children=null), TreeNode(nodeName=B2, nodeCode=5, children=null)]), TreeNode(nodeName=C, nodeCode=2, children=[TreeNode(nodeName=C1, nodeCode=6, children=null)]), TreeNode(nodeName=D, nodeCode=3, children=[TreeNode(nodeName=D1, nodeCode=7, children=null), TreeNode(nodeName=D2, nodeCode=8, children=null)])])

INFO FilterTreeNode - after filter node0: TreeNode(nodeName=A, nodeCode=0, children=[TreeNode(nodeName=B, nodeCode=1, children=[TreeNode(nodeName=B1, nodeCode=4, children=null)]), TreeNode(nodeName=C, nodeCode=2, children=[TreeNode(nodeName=C1, nodeCode=6, children=null)])])

总结

本文介绍java 树形结构数据过滤，使用递归方法并通过实际示例进行说明。