具有节点过滤的Java通用树遍历

4 回答

• 1

  我建议你尝试以下方法：

  方法 boolean removeRecursively(String id, Set<String> leavesToKeep) 将从具有给定 id 的节点遍历到此分支离开 .

  首先，我们检查一下是不是一个叶子 . 如果叶子不在 leavesToKeep 集合中，我们将其删除并返回 true ，否则返回 false . 这是我们递归的基本情况 .

  如果节点不是叶子，那么我们这样做：

  children.removeIf(n -> removeRecursively(n.id, leavesToKeep));
  

  removeIf是一种方便的Java 8方法，用于删除满足给定谓词的所有元素 . 这意味着只有在删除了所有子项时，才会从列表中删除子项 . 因此，如果 children.removeIf 调用 children 列表为空，我们应该使 removeRecursively 返回true：

  if (children.isEmpty()) {
      tree.remove(id);
      return true;
  } else return false;
  

  完整方法可能如下所示：

  public static boolean removeRecursively(Map<String, List<Node>> tree, String id, Set<String> leavesToKeep) {
      List<Node> children = tree.get(id);
      if (children == null || children.isEmpty()) {
          if (!leavesToKeep.contains(id)) {
              tree.remove(id);
              return true;
          } else return false;
      }
      children.removeIf(n -> removeRecursively(tree, n.id, leavesToKeep));
      if (children.isEmpty()) {
          tree.remove(id);
          return true;
      } else return false;
  }
  

  其中 tree 是您描述的 Map ， id 是起始节点ID， leavesToKeep 是要保留的一组ID .

  回复于 2024-04-26T16:15:54+08:00
• 0

  我想，某种递归DFS遍历算法应该可行

  这是完全正确的 . 以下是构建此算法的方法：

  • 观察任务是否具有递归结构：将其应用于树的任何分支对分支执行与您想要对整个树执行的操作相同的操作

  • 分支可以被修剪，也可以完全删除

  • 您的递归实现将返回一个已修剪的分支;它会通过返回 null 来指示删除分支

  • 递归函数会检查传入 Node

  • 如果节点表示叶子，则将根据我们希望保留的项目列表检查其内容

  • 如果"keep list"上没有叶子，则返回 null ;否则返回叶子

  • 对于非叶子分支，调用递归方法，并检查其结果

  • 如果结果为 null ，则从 Map 中删除相应的分支;否则，用从调用返回的修剪分支替换分支

  • 如果检查所有分支时子节点的映射为空，则返回 null

  请注意，如果没有叶节点与"keep"列表匹配，则算法可以返回 null . 如果这不合适，请在递归实现之上添加额外的级别，并在返回空树的情况下替换顶层的 null 返回 .

  回复于 2024-04-26T16:15:54+08:00
• 1

  使用界面树：

  public static interface Tree<T> {
      public T getValue();
  
      public List<Tree<T>> children();
  
      public default boolean isLeaf() {
          return children().isEmpty();
      }
  
      public default boolean removeDeadBranches(Predicate<T> testLiveLeaf) {
          if (isLeaf()) {
              return testLiveLeaf.test(getValue());
          }
          boolean remainLife = false;
          for (Iterator<Tree<T>> it = children().iterator(); it.hasNext();) {
              if (it.next().removeDeadBranches(testLiveLeaf)) {
                  remainLife = true;
              } else {
                  it.remove();
              }
          }
          return remainLife;
      }
  }
  

  回复于 2024-04-26T16:15:54+08:00
• 0

  import com.google.common.collect.Lists;
  import org.junit.Before;
  import org.junit.Test;
  import org.slf4j.Logger;
  import org.slf4j.LoggerFactory;
  
  import java.util.List;
  
  public class FilterTreeNode {
      private Logger logger = LoggerFactory.getLogger(FilterTreeNode.class);
      private TreeNode node0;
      private List<String> targetNode = Lists.newArrayList("B1","D1");
  
      @Before
      public void init(){
          node0 = TreeNode.builder().nodeCode("0").nodeName("A").build();
          TreeNode node1 = TreeNode.builder().nodeCode("1").nodeName("B").build();
          TreeNode node2 = TreeNode.builder().nodeCode("2").nodeName("C").build();
          TreeNode node3 = TreeNode.builder().nodeCode("3").nodeName("D").build();
  
          TreeNode node4 = TreeNode.builder().nodeCode("4").nodeName("B1").build();
          TreeNode node5 = TreeNode.builder().nodeCode("5").nodeName("B2").build();
          TreeNode node6 = TreeNode.builder().nodeCode("6").nodeName("C1").build();
          TreeNode node7 = TreeNode.builder().nodeCode("7").nodeName("D1").build();
          TreeNode node8 = TreeNode.builder().nodeCode("8").nodeName("D2").build();
  
          node1.setChildren(Lists.newArrayList(node4,node5));
          node2.setChildren(Lists.newArrayList(node6));
          node3.setChildren(Lists.newArrayList(node7,node8));
  
          node0.setChildren(Lists.newArrayList(node1,node2,node3));
      }
  
      @Test
      public void filterTest(){
          logger.info("before filter node0: {}",node0);
          List<TreeNode> retNodes = filterNode(node0);
          if (retNodes.size() >0){
              node0.setChildren(retNodes);
          }
          logger.info("after filter node0: {}",node0);
      }
  
      private List<TreeNode> filterNode(TreeNode treeNode){
  
          List<TreeNode> nodes = treeNode.getChildren();
          List<TreeNode> newNodes = Lists.newArrayList();
          List<TreeNode> tagNodes = Lists.newArrayList();
  
          for(TreeNode node : nodes){
              if (targetNode.contains(node.getNodeName())){
                  newNodes.add(node);
              }
              if (node.getChildren() != null && node.getChildren().size() >0){
                  List<TreeNode> retNodes = filterNode(node);
                  if (retNodes.size()>0){
                      node.setChildren(retNodes);
                  }else {
                      node.setChildren(null);
                      tagNodes.add(node);
                  }
              }
          }
          nodes.removeAll(tagNodes);
          return newNodes;
      }
  }
  

  回复于 2024-04-26T16:15:54+08:00