三叉树的垂直输出（Java实现）
这是2020酷家乐的笔试真题
三叉树的结构如下图。
要求：
任选一种编程语言，实现功能。
写函数，垂直输出元素值。
输出的结果如下：
A,B,D, A,C,G, A,C,K,
代码实现，利用深度优先搜索和回溯法求解
首先构建节点类
class Node{ String value;//节点值，如果节点值为null，则其没有子节点 Node left;//左子节点 Node middle;//中间子节点 Node right;//有子节点 public Node(String value) { this.value = value; } @Override public String toString() { return value; } }
然后深度优先搜索
package Day43; import java.util.ArrayList; import java.util.Stack; /** * @Author Zhongger * @Description 三叉树的垂直输出 * @Date 2020.3.15 */ public class PrintTreeVerticalSolution { public static void main(String[] args) { Node root = new Node("A"); Node b = new Node("B"); Node c = new Node("C"); Node d = new Node("D"); Node g = new Node("G"); Node k = new Node("K"); root.left=b; root.right=c; b.right=d; c.left=g; c.right=k; printTreeVertical(root); } public static void printTreeVertical(Node root){ Stack<Node> stack = new Stack<>(); if (root==null){ return; } stack.push(root); trace(stack);//递归处理 } public static void trace(Stack<Node> stack){ if (stack.isEmpty()){ return; } Node current = stack.peek();//当前元素 //叶子节点，表示一次遍历完成后，就可以输出了 if (current.left==null&¤t.middle==null&¤t.right==null){ ArrayList<Node> list = new ArrayList<>(stack); System.out.println(list); //输出路径 StringBuffer stringBuffer = new StringBuffer(100); for (final Node temp : list) { stringBuffer.append(temp.value).append(","); } System.out.println(stringBuffer.toString()); //删除一个元素 stack.pop(); System.out.println(stack.toString()); return; } //把每个条件都遍历一遍 if (current.left!=null){ stack.push(current.left); trace(stack); } if (current.middle!=null){ stack.push(current.middle); trace(stack); } if (current.right!=null){ stack.push(current.right); trace(stack); } } }
答案虽然输出有些偏差，但是体现了思想就可以了。
评分标准：
1、体现深度遍历算法 +10分
2、栈式结构，stack、list均可 +4分
3、循环或递归，判断好边界 +6分
4、视答案完成度略微扣分
