欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

栏目树遍历记

程序员文章站 2022-05-19 21:05:52
...

场景:
基于实际项目,系统中有一个栏目树形结构,需要用jquery动态展开树,因此需要后台查询数据,并拼装成jquery可以访问的json格式。

思路:
一开始前端需要分层数据,JSONArray中装载了一个数组,每个元素为该层所有节点,数据格式如下(只举个例子):
[{1:[{id:1,name:“name1”},{id:2,name:“name2”}]},{2:[{id:2_1,name:“name2_1”}]}]
所以找到了一个树的层序遍历的实现,但是后来前端要的数据格式又改了,需要嵌套的数据,所以考虑使用递归遍历。

层序遍历实现:
这个实现后来没有用,所以也就没有再进行优化,总体的思路是维护两个指针,分别指向当前层cur和下一层next,遍历cur层时把该层所有的子节点都放到next层,当cur层都遍历完之后再将cur指针下移,同时重新初始化next层,开始下一波遍历。

public String getTree(Channel topChn){//根节点,即*栏目
        JSONArray array = new JSONArray();//返回的数据
        Queue<Channel> cur = new LinkedList<Channel>();//指向当前层的指针队列
        Queue<Channel> next = new LinkedList<Channel>();//指向下一层的指针队列
        cur.offer(topChn);//根节点入队
        List<Node> list = new ArrayList<Node>();//装载本层节点
        Map<Integer,List<Node>> map = new HashMap<Integer,List<Node>>();//维护一个Map存放类似的键值对[1:[{...},{...}]]
        int i=0;//层标
        while (!cur.isEmpty()){//若当前层还有节点,则遍历
            Channel c = cur.poll();//队头取出第一个节点
            list.add(new Node(c.getId(),c.getName(),c.getParentId));//创建一个Node对象装入List
            if(!c.getChild().isEmpty()){//若当前节点有子节点,则将所有子节点入队
                next.addAll(c.getChild());
            }
            if(cur.isEmpty()){//当当前层节点遍历完之后,指针下移
                cur=next;//当前指针指向next层
                next=new LinkedList<Channel>();//初始化next层
                map.put(++i,list);//将本层数据入map
                array.add(map);//并将map放入结果队列
                list = new ArrayList<Node>();//初始化本层数据
            }
        }
        return array.toJSONString();
    }

递归遍历实现:
改了数据格式之后,考虑递归遍历,我觉得递归遍历的精髓就是只考虑本层节点,下一层节点就交给递归,也就是方法自己来做。这里还有一个特殊的需求就是只展开当前访问的节点的子栏目,其他节点如果有子栏目也不展开。
所以我就需要获取从根节点到当前节点的路径,用来判断遍历的节点需不需要展开。

/*
	 * 获取路径
	 */
	public List<Integer> getInher(Channel channel){//访问的节点
		List<Integer> inher = new ArrayList<Integer>();
		Channel current = channel;//当前栏目
		Channel parent = channel.getParent();//父栏目
		inher.add(current.getId());
		while(parent!=null){//从当前栏目出发,一路向上直到根节点
			inher.add(parent.getId());
			current = parent;
			parent = parent.getParent();
		}
		return inher;
	}

这个方法可以获取到当前节点到根节点的路径。
所以迭代的思路如下:传入根节点,提取所需信息,然后遍历其子节点,并递归获取其子节点Node,此时判断子节点是否在路径中,如果在则向下递归获取,并将返回的节点装入列表,如果不在,则不向下递归,直接new一个nodes成员为空的Node对象,并放入列表,最后将子节点集合装入根节点nodes成员即可。但是看着简单,因为很久没有写这种算法所以还是废了脑筋想了好久的,改了至少3次才得到了现在看起来比较简洁的版本,看来算法还得刷,说不定什么时候就用上了。

/*
	 * 迭代获取栏目树
	 */
	public Node getChildren(Channel root,Channel curChn,List<Integer> inher){
		Node c_node = new Node();
		c_node.setId(root.getId());
		c_node.setText(root.getName());//拼写节点基本信息
		List<Node> children = new ArrayList<Node>();
		//获取节点所有子节点,只装入在栏目路径中的显示节点
		for(Channel child : root.getChild()){
			if(inher.contains(child.getId())){//若该栏目在栏目路径中,则展开
				Node child_node=getChildren(child,curChn,inher);
				children.add(child_node);
			}else {//否则不展开
				children.add(new Node(child.getId(),child.getName(),new ArrayList<Node>()));
			}
		}
		c_node.setNodes(children);
		return c_node;
	}

Node节点是内部类。

class Node implements Serializable{
		private int id;
		private String text;
		private List<Node> nodes;
		
		public Node(){}
		public Node(int id,String text,List<Node> nodes){
			this.id=id;
			this.text = text;
			this.nodes=nodes;
		}
		public int getId() {
			return id;
		}
		public void setId(int id) {
			this.id = id;
		}
		public String getText() {
			return text;
		}
		public void setText(String text) {
			this.text = text;
		}
		public List<Node> getNodes() {
			return nodes;
		}
		public void setNodes(List<Node> nodes) {
			this.nodes = nodes;
		}
	}