三叉树的垂直输出
三叉树的结构如上图。
要求:
1、任选一种编程语言,写代码,实现功能。
写函数,垂直输出元素值。
A,B,D,
A,C,G,
A,C,K,
A,C,G,
A,C,K,
public class Main { public static void main(String[] args) { Node node = new Node("A"); node.left = new Node("B"); node.right = new Node("C"); node.left.right = new Node("D"); node.right.left = new Node("G"); node.right.right = new Node("k"); dfs(node,""); } private static class Node { public String value; public Node left; public Node middle; public Node right; public Node(String value) { this.value = value; } } static void dfs(Node node, String prefix) { if (node.left != null)dfs(node.left, prefix + node.value); if (node.middle != null) dfs(node.middle, prefix + node.value); if (node.right != null)dfs(node.right, prefix + node.value); if (node.left == null && node.middle == null && node.right == null) System.out.println(prefix + node.value); } }
//回溯法 public void vertical(node root){ Set<String> res = new HashSet<>(); travel(root,new StringBuilder(), res,0); for(String s : res){ for(char c : s.toCharArray()){ System.out.print(c + ","); } System.out.println(); } } public void travel(node node, StringBuilder sb, Set<String> res, int layer){ if(node==null){ return; } sb.append(node.value); if(node.left==null && node.middle==null && node.right==null){ res.add(sb.toString()); sb.deleteCharAt(layer); return; } travel(node.left, sb, res,layer+1); travel(node.middle, sb, res,layer+1); travel(node.right, sb, res,layer+1); sb.deleteCharAt(layer); }