首页 > 代码库 > 蓝桥杯——说好的进阶之多叉树的遍历
蓝桥杯——说好的进阶之多叉树的遍历
多叉树,简单地说,与二叉树类似的,但叉可能要多的树形结构;类似于计算机文件目录。
static class MyTree { private Map map = new HashMap(); public void add(char parent, char child) { List<Character> t = (List<Character>) map.get(parent);// child list if (t == null) { t = new Vector<Character>(); map.put(parent, t); // } t.add(child); } public List<Character> getChild(char x) { return (List<Character>) map.get(x); } } //深度优先 static void Dfs(MyTree tree,char x) { List<Character> child=tree.getChild(x); Stack<Character> stack=new Stack<Character>(); stack.push(x); while(!stack.isEmpty()) { System.out.print(stack.peek()+" "); List<Character> tmp = tree.getChild(stack.pop()); if(tmp!=null) for(int i=0;i<tmp.size();i++) { stack.push(tmp.get(tmp.size()-i-1)); } } System.out.println(); } //广度优先 static void Bfs(MyTree tree, char x) { List<Character> t=tree.getChild(x); List<Character> lst=new Vector<Character>(); lst.add(x); while(lst.size()>0) { System.out.print(lst.get(0)+" "); List<Character> tmp=tree.getChild(lst.remove(0)); if(tmp!=null) { for(int j=0;j<tmp.size();j++) lst.add(tmp.get(j)); } } System.out.println(); } public static List<String> showTree(MyTree tree, char x) { List<Character> t = tree.getChild(x); // get child list List<String> r = new Vector<String>(); if (t == null) { r.add("" + x); return r; } for (int i = 0; i < t.size(); i++) { List<String> ri = showTree(tree, t.get(i)); for (int j = 0; j < ri.size(); j++) { String pre = "| "; if (j == 0) { if (i == 0) pre = x + "--"; else pre = "|--"; } else { if (i == ri.size() - 1) pre = " "; else pre = "| "; } r.add(pre + ri.get(j)); } } return r; } public static void main(String[] args) { MyTree a = new MyTree(); a.add(‘a‘, ‘b‘); a.add(‘b‘, ‘e‘); a.add(‘b‘, ‘f‘); a.add(‘a‘, ‘c‘); a.add(‘a‘, ‘d‘); a.add(‘d‘, ‘g‘); a.add(‘d‘, ‘i‘); a.add(‘g‘, ‘h‘); a.add(‘f‘, ‘j‘); a.add(‘f‘, ‘k‘); List<String> lst = showTree(a, ‘a‘); for (int i = 0; i < lst.size(); i++) { System.out.println(lst.get(i)); } System.out.println(); // Bfs(a, ‘a‘); Dfs(a, ‘a‘); }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。