首页 > 代码库 > java 遍历树结点 同时保留所有从根到叶子结点的路径
java 遍历树结点 同时保留所有从根到叶子结点的路径
直接上代码,以后再细说
数据结构定义:
/** * */ package Servlet; import java.util.ArrayList; import java.util.List; /** * @author lei * */ public class node { private String text; private List<node>childList; public String getText() { return text; } public void setText(String text) { this.text = text; } public List<node> getChildList() { return childList; } public void setChildList(List<node> childList) { this.childList = childList; } public static node getInitNode() { node nodeA=new node(); nodeA.setText("A"); node nodeB=new node(); nodeB.setText("B"); node nodeC=new node(); nodeC.setText("C"); node nodeD=new node(); nodeD.setText("D"); node nodeE=new node(); nodeE.setText("E"); List<node>lstB=new ArrayList(); lstB.add(nodeC); lstB.add(nodeD); nodeB.setChildList(lstB); List<node>lstA=new ArrayList(); lstA.add(nodeB); lstA.add(nodeE); nodeA.setChildList(lstA); return nodeA; } }
遍历并保存路径
/** * */ package Servlet; import java.util.ArrayList; import java.util.Arrays; import java.util.HashMap; import java.util.Iterator; import java.util.List; import java.util.Map; import java.util.Stack; /** * @author lei * */ public class IteratorNodeTool { Map<String,List> pathMap=new HashMap();//记录所有从根节点到叶子结点的路径 private void print(List lst)//打印出路径 { Iterator it=lst.iterator(); while(it.hasNext()) { node n=(node)it.next(); System.out.print(n.getText()+"-"); } System.out.println(); } public void iteratorNode(node n,Stack<node> pathstack) { pathstack.push(n);//入栈 List childlist=n.getChildList(); if(childlist==null)//没有孩子 说明是叶子结点 { List lst=new ArrayList(); Iterator stackIt=pathstack.iterator(); while(stackIt.hasNext()) { lst.add(stackIt.next()); } print(lst);//打印路径 pathMap.put(n.getText(), lst);//保存路径信息 return; }else { Iterator it=childlist.iterator(); while(it.hasNext()) { node child=(node)it.next(); iteratorNode(child,pathstack);//深度优先 进入递归 pathstack.pop();//回溯时候出栈 } } } public static void main(String[] args) { Stack <node>pathstack=new Stack(); node n=node.getInitNode(); IteratorNodeTool tool=new IteratorNodeTool(); tool.iteratorNode(n, pathstack); } }
java 遍历树结点 同时保留所有从根到叶子结点的路径
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。