工作中有关于菜单的处理,菜单即为多叉树的结构。该样例支持如下功能:
1.获取所有节点;
2.获取当前节点的所有子节点;
3. 获取当前节点的所有父节点 ;
4.获取同级字段;
package express.tree;
import com.alibaba.fastjson.JSONObject;
import java.io.Serializable;
import java.util.*;
import java.util.stream.Collectors;
public class NodeTreeTraversalDemo {
public static void main(String[] args) {
List<Node> allList=new ArrayList<>();
Node node1=new Node();
node1.setId(1);
node1.setLevel(1);
node1.setParentId(0);
Node node2=new Node();
node2.setId(2);
node2.setLevel(2);
node2.setParentId(1);
Node node3=new Node();
node3.setId(3);
node3.setLevel(3);
node3.setParentId(2);
Node node4=new Node();
node4.setId(4);
node4.setLevel(2);
node4.setParentId(1);
Node node5=new Node();
node5.setId(5);
node5.setLevel(4);
node5.setParentId(3);
Node node6=new Node();
node6.setId(6);
node6.setLevel(4);
node6.setParentId(3);
allList.add(node1);
allList.add(node2);
allList.add(node3);
allList.add(node4);
allList.add(node5);
allList.add(node6);
System.out.println("--------------所有节点的节点树--------------");
List<Node> treeList=getTree(allList);
String jsonStr = JSONObject.toJSONString(treeList);
System.out.println(jsonStr);
System.out.println("--------------获取id为2的所有子节点--------------");
List<Node> childNodeList=getChildrenNode(2,allList);
String childJsonStr = JSONObject.toJSONString(childNodeList);
System.out.println(childJsonStr);
System.out.println("--------------向上追溯获取id为3的所有父节点--------------");
Map<Integer, Node> maps = allList.stream().collect(Collectors.toMap(Node::getId, Node->Node));
List<Node> parentNodeList=findAllParent(node3,maps);
String parentJsonStr = JSONObject.toJSONString(parentNodeList);
System.out.println(parentJsonStr);
System.out.println("---------------获取第2层的同级节点--------------");
List<Node> sameLevelTreesList=findSameLevelNode(2,allList);
String sameLevelTreesJsonStr = JSONObject.toJSONString(sameLevelTreesList);
System.out.println(sameLevelTreesJsonStr);
}
/**
* 获取所有节点
* @param allList
* @return
*/
public static List<Node> getTree(List<Node> allList) {
List<Node> treeList=new ArrayList<>();
for (Node vo :allList){
if (vo.getParentId()==0){
vo.setChildren(getChildrenNode(vo.getId(), allList));
treeList.add(vo);
}
}
return treeList;
}
/**
* 递归获取子节点下的子节点
* @param id 父节点的ID
* @param treesList 所有菜单树集合
* @return
*/
private static List<Node> getChildrenNode(Integer id, List<Node> treesList) {
List<Node> newTrees = new ArrayList<Node>();
for (Node tmpNode : treesList) {
if ("0".equals(tmpNode.getParentId())) {
continue;
}
if (id.equals(tmpNode.getParentId())) {
// 递归获取子节点下的子节点,即设置树控件中的children
tmpNode.setChildren(getChildrenNode(tmpNode.getId(), treesList));
newTrees.add(tmpNode);
}
}
return newTrees;
}
/**
* 给定节点查找该节点的所有父节点
* @param node
* @param data 存储的是所有的节点数据,key为该节点的Id,value为该node
* @return
*/
public static List<Node> findAllParent(Node node, Map<Integer,Node> data) {
List<Node> res = new ArrayList<>();
Stack<Node> stack = new Stack<>();
stack.push(node);
while(!stack.isEmpty()){
//弹出栈顶节点
Node n = stack.pop();
if(n.getId().equals(n.getParentId())) {
res.add(n);
break;
}
if(data.containsKey(n.getParentId())){
Node parent = data.get(n.getParentId());
res.add(n);
stack.push(parent);
}else{
res.add(n);
}
}
return res;
}
public static List<Node> findSameLevelNode(Integer level,List<Node> treesList){
List<Node> sameLevelTreesList=new ArrayList<>();
for (Node node: treesList){
if(level.equals(node.getLevel())){
sameLevelTreesList.add(node);
}
}
return sameLevelTreesList;
}
}
/**
* 节点实体类
*/
class Node implements Serializable {
/**
* 主键
*/
private Integer id;
/**
* 节点名称
*/
private String name;
/**
* 节点编码
*/
private String code;
/**
* 父id[根节点为0]
*/
private Integer parentId;
/**
* 等级 [递增 根节点为0]
*/
private Integer level;
/**
* 子树列表 -- 原本没有值
*/
private List<Node> children ;
public Integer getId() {
return id;
}
public void setId(Integer id) {
this.id = id;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public String getCode() {
return code;
}
public void setCode(String code) {
this.code = code;
}
public Integer getParentId() {
return parentId;
}
public void setParentId(Integer parentId) {
this.parentId = parentId;
}
public Integer getLevel() {
return level;
}
public void setLevel(Integer level) {
this.level = level;
}
public List<Node> getChildren() {
return children;
}
public void setChildren(List<Node> children) {
this.children = children;
}
@Override
public boolean equals(Object obj) {
if(this==obj)return true;
if(obj==null) return false;
if(getClass()!=obj.getClass()) return false;
Node node0bj=(Node) obj;
if(id!=null)
{
if(id.equals(node0bj.getId())
){
return true;
}else{
return false;
}
}else {
return false;
}
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((id == null) ? 0 : id.hashCode());
return result;
}
@Override
public String toString(){
return "id "+id+",name "+ name +",level " +level+",children "+children;
}
}
--------------所有节点的节点树--------------
[{"children":[{"children":[{"children":[{"children":[],"id":5,"level":4,"parentId":3},{"children":[],"id":6,"level":4,"parentId":3}],"id":3,"level":3,"parentId":2}],"id":2,"level":2,"parentId":1},{"children":[],"id":4,"level":2,"parentId":1}],"id":1,"level":1,"parentId":0}]
--------------获取id为2的所有子节点--------------
[{"children":[{"children":[],"id":5,"level":4,"parentId":3},{"children":[],"id":6,"level":4,"parentId":3}],"id":3,"level":3,"parentId":2}]
--------------向上追溯获取id为3的所有父节点--------------
[{"children":[{"children":[],"id":5,"level":4,"parentId":3},{"children":[],"id":6,"level":4,"parentId":3}],"id":3,"level":3,"parentId":2},{"children":[{"$ref":"$[0]"}],"id":2,"level":2,"parentId":1},{"children":[{"$ref":"$[1]"},{"children":[],"id":4,"level":2,"parentId":1}],"id":1,"level":1,"parentId":0}]
---------------获取第2层的所有节点--------------
[{"children":[{"children":[{"children":[],"id":5,"level":4,"parentId":3},{"children":[],"id":6,"level":4,"parentId":3}],"id":3,"level":3,"parentId":2}],"id":2,"level":2,"parentId":1},{"children":[],"id":4,"level":2,"parentId":1}]