求一个算法，删除掉树状结构的空节点

有如下一张表

id	name	parent_id
1	中国	0
2	广东省	1
3	深圳市	2
4	广州市	2
5	广西省	1

使用java从mysql拉取到整颗树状结构如下

中国

 广东省
        深圳市（1人）
        广州市
 广西省

要求如下（使用java实现，此处不涉及到mysql的增删）
1.如何通过递归删除掉没有挂人的地域
2 如上所示如果子节点挂载了人，那么父节点也需要保留
综上，如何获取到一颗新的树，这棵树是提供给前端渲染的

你这些数据最终要在页面上显示，那就遵循一个原则：想要显示的查询，不显示的不查询。

1.用id做为参数，递归查询所有层级的所有子节点
2.判断：如果其中有一个子节点有人，那么整条线都要展示，记录下该节点id
3.查询：把上面记录下的id所对应的数据查询出来，就是需要展示的，因为没有人的节点根本不会记录

问题不在于删除，在于如何找出需要的数据，本质是一个剔除查询。

用递归遍历删除。跟删除空文件夹一个意思。

Java递归删除空文件夹_二十同学-CSDN博客_java删除空文件夹 import java.io.File;public class ClearFile { static int iFile = 0; public static void main(String[] args) { // TODO Auto-generated method stub// dir_str清理文件夹的路径 String dir_s...

https://blog.csdn.net/qq_18298439/article/details/80914346

1.查询出所有的机构id allCityList
2.机构关联人员表，查询出所有有人员的机构id effectiveList
3.根据effectiveList 向上子级递归，查询出有效的城市Id compareList
4.allCityList remove compareList 得到的就是需要删除的城市id

实现逻辑比较简单，看你数据量大小注意别内存溢出了，有溢出风险，就分批次处理。
然后在是子级向上递归的查询，数据库用的是oracle那实现比较简单，是mysql，也可以实现，就是复杂点

用广度优先算法递归遍历，递归中发现子节点没人当前节点有人则断连接，子节点有人也默认当前节点有人。
以二叉树为例，大致思路如下

boolean filterPeople(Node node) {
    // 当前节点有没有人
    boolean hasPeople = node有人 ? true : false;
    // 叶子节点直接返回
    if(node.left == null && node.right == null ) {
        return hasPeople;
    }
    // 左边有没有人
    boolean leftHasPeople = node.left == null ? false : filterPeople(node.left);
    // 右边有没有人
    boolean rightHasPeople = node.right == null ? false : filterPeople(node.right);

    if (hasPeople) {
        // 当前节点有人，左边没人断左链接
        if (!leftHasPeople) {
            node.left = null;
        }
        // 当前节点有人，右边没人断右链接
        if (!rightHasPeople) {
            node.right = null;
        }
        // 有人返回true
        return true;
    } else {
        // 当前节点没人，但是左右节点任意有人都算有人
        ruturn leftHasPeople || rightHasPeople;
    }
}

要啥有啥，这不香吗

该问题已经解决了，感谢一位小水牛的网友，附上代码

public class RemoveNode {

public static void main(String[] args) {
List<Node> nodes = new ArrayList<>() {
{
add(new Node(0, -1, null));
add(new Node(1, -1, 0));
add(new Node(2, 2, 1));
add(new Node(3, 0, 1));
add(new Node(4, -1, 0));
add(new Node(5, 0, 4));
}
};

List<Node> remove = remove(nodes);
System.out.println(remove);
}

static List<Node> remove(List<Node> nodes) {

Map<Integer, Node> nodeMap = nodes.stream()
.collect(Collectors.toMap(
Node::getId, node -> node
));

List<Node> remainNode = new ArrayList<>();

nodes.stream()
.filter(node -> node.getNum() > 0)
.forEach(
e -> remainNode.addAll(findParents(nodeMap, e))
);

return remainNode.stream().distinct().collect(Collectors.toList());

}

static List<Node> findParents(Map<Integer, Node> nodes, Node node) {
//此处漏了加入自身节点
List<Node> parents = new ArrayList<>();
while (node != null) {
node = findParent(nodes, node);
parents.add(node);
}
return parents;
}

static Node findParent(Map<Integer, Node> nodes, Node node) {

return nodes.get(node.parentId);
}

@Data
@NoArgsConstructor
@AllArgsConstructor
static class Node {

Integer id;
Integer num;
Integer parentId;
}
}

boolean filterPeople(Node node) {
boolean hasPeople = node有人 ? true : false;
if(node.left == null && node.right == null ) {
return hasPeople;
}
boolean leftHasPeople = node.left == null ? false : filterPeople(node.left);
boolean rightHasPeople = node.right == null ? false : filterPeople(node.right);

if (hasPeople) {
    if (!leftHasPeople) {
        node.left = null;
    }
    if (!rightHasPeople) {
        node.right = null;
    }
    return true;
} else {
    ruturn leftHasPeople || rightHasPeople;
}

}