ARTS打卡计划第5周-SHARE-java构建树形结构

骑猪看日落 2021-12-19 17:21 322阅读 0赞

在项目开发过程中，我们经常会遇到树形数据结构的设计，例如菜单树，地区树和类别树等等。一般而言，我们需要把数据库中记录全取出来，然后构建树（注意的是，最好是一次性取出来，如果是ajax按需拉数据则不需要）。下面分享了递归和非递归两种方式：

package test.tree;
    
    import java.util.ArrayList;
    import java.util.List;
    
    public class Node {
    
    	private String id;
    	private String parentId;
    
    	private String value;
    	private Node parent;
    
    	private List<Node> children;
    
    	public Node() {
    		super();
    		this.children = new ArrayList<>();
    	}
    
    	public Node(String value, String id, String parentId) {
    		this.value = value;
    		this.id = id;
    		this.parentId = parentId;
    		this.children = new ArrayList<>();
    	}
    
    	public String getValue() {
    		return value;
    	}
    
    	public void setValue(String value) {
    		this.value = value;
    	}
    
    	public String getId() {
    		return id;
    	}
    
    	public void setId(String id) {
    		this.id = id;
    	}
    
    	public String getParentId() {
    		return parentId;
    	}
    
    	public void setParentId(String parentId) {
    		this.parentId = parentId;
    	}
    
    	public Node getParent() {
    		return parent;
    	}
    
    	public void setParent(Node parent) {
    		this.parent = parent;
    	}
    
    	public List<Node> getChildren() {
    		return children;
    	}
    
    	public void setChildren(List<Node> children) {
    		this.children = children;
    	}
    
    	public void addChild(Node child) {
    		if (!this.children.contains(child) && child != null)
    			this.children.add(child);
    	}
    
    	@Override
    	public boolean equals(Object obj) {
    		// TODO Auto-generated method stub
    		if(obj instanceof Node) {
    			if(this.id.equals(((Node) obj).getId())) {
    				return true;
    			}
    		}
    		return false;
    	}
    	@Override
    	public String toString() {
    		return "Node [id=" + id + ", parentId=" + parentId + ", value=" + value + ", children=" + children + "]";
    	}
    }

非递归的方式

package test.tree;
    
    import java.io.IOException;
    import java.nio.file.Files;
    import java.nio.file.Paths;
    import java.util.ArrayList;
    import java.util.HashMap;
    import java.util.List;
    import java.util.Map;
    
    public class ListToTreeNoRecurse {
    
    	public static void main(String[] args) throws IOException {
    		List<Node> nodes = new ArrayList<>();
    		List<String> lines = Files
    				.readAllLines(Paths.get("C:\\Users\\95\\Desktop\\leetCode\\src\\test\\tree\\jsontest.txt"));
    		nodes.add(new Node("all", "0", null));
    		for (String line : lines) {
    			String[] values = line.split(",");
    			Node node = new Node(values[1].trim(), values[0].trim(), values[3].trim());
    			nodes.add(node);
    		}
    
    		long start = System.currentTimeMillis();
    		createTree(nodes);
    		long end = System.currentTimeMillis();
    		System.err.println((end - start));
    
    	}
    
    	private static void createTree(List<Node> nodes) {
    
    		Map<String, Node> mapTmp = new HashMap<>();
    		// Save all nodes to a map
    		for (Node current : nodes) {	
    			mapTmp.put(current.getId(), current);
    		
    		}
    		// loop and assign parent/child relationships
    		for (Node current : nodes) {
    			String parentId = current.getParentId();
    			if (parentId != null) {
    				Node parent = mapTmp.get(parentId);
    				if (parent != null) {
    					current.setParent(parent);
    					parent.addChild(current);
    					mapTmp.put(parentId, parent);
    					mapTmp.put(current.getId(), current);
    				}
    			}
    
    		}
    
    		System.out.println(mapTmp.get("0"));
    		
    	}
    }

递归的方法来

package test.tree;
     
    import java.io.IOException;
    import java.nio.file.Files;
    import java.nio.file.Paths;
    import java.util.ArrayList;
    import java.util.List;
    
    import test.tree.Node;
     
    
    public class TreeBuilder {
     
     
        /**
         * 使用递归方法建树
         * @param Nodes
         * @return
         */
        public static List<Node> buildByRecursive(List<Node> Nodes) {
            List<Node> trees = new ArrayList<Node>();
            for (Node Node : Nodes) {
                if ("0".equals(Node.getParentId())) {
                    trees.add(findChildren(Node,Nodes));
                }
            }
            return trees;
        }
     
        /**
         * 递归查找子节点
         * @param Nodes
         * @return
         */
        public static Node findChildren(Node Node,List<Node> Nodes) {
            for (Node it : Nodes) {
                if(Node.getId().equals(it.getParentId())) {
                    if (Node.getChildren() == null) {
                        Node.setChildren(new ArrayList<Node>());
                    }
                    Node.getChildren().add(findChildren(it,Nodes));
                }
            }
            return Node;
        }
     
     
     
        public static void main(String[] args) throws IOException {
        	 List<Node> list = new ArrayList<Node>();
        	 List<String> lines =  Files.readAllLines(Paths.get("C:\\Users\\95\\Desktop\\leetCode\\src\\test\\tree\\jsontest.txt"));
        	for(String line:lines) {
        		String[] values = line.split(",");
        		Node node = new Node(values[1], values[0], values[3]);		
        		list.add(node);
        	}
        	
        	long beforeUsedMem=Runtime.getRuntime().totalMemory()-Runtime.getRuntime().freeMemory();
            long start = System.currentTimeMillis();
            List<Node> trees_ = TreeBuilder.buildByRecursive(list);
            long afterUsedMem=Runtime.getRuntime().totalMemory()-Runtime.getRuntime().freeMemory();
            
            long actualMemUsed=afterUsedMem-beforeUsedMem;
    
            long end = System.currentTimeMillis();
            System.out.println(trees_);
            System.err.println((end - start));
            System.err.println(actualMemUsed);
        }
     
    }

上述方法的测试数据是世界地区数据，下载地址是：[https://epubi.oss-cn-shanghai.aliyuncs.com/jsontest.txt][https_epubi.oss-cn-shanghai.aliyuncs.com_jsontest.txt]

经过测试，如果不打印树的话，非递归方法构建树是非常快的，远少于递归方法。打印树的话，非递归的方法的性能是略微优于递归的。

因为非递归方法构建的时候，只是构建child，parent之间的引用，在真正打印的时候，会调用toString方法对child进行打印，这个时候也是一个遍历的过程。在项目中还是推荐使用非递归方法，非递归方法比较可控。

该方法继承至AbstractCollection中的toString方法。

public String toString() {
            Iterator<E> it = iterator();
            if (! it.hasNext())
                return "[]";
    
            StringBuilder sb = new StringBuilder();
            sb.append('[');
            for (;;) {
                E e = it.next();
                sb.append(e == this ? "(this Collection)" : e);
                if (! it.hasNext())
                    return sb.append(']').toString();
                sb.append(',').append(' ');
            }
        }

转载于:https://www.cnblogs.com/dongqiSilent/p/10897573.html

[https_epubi.oss-cn-shanghai.aliyuncs.com_jsontest.txt]: https://epubi.oss-cn-shanghai.aliyuncs.com/jsontest.txt