說到數的遍歷樹,長期以來的第一印象都是通過遞歸去實現。然而今天看了某位前輩的代碼,才發現使用棧去實現遍歷是那么簡單。理論上通過數組也是可以實現同等功能的,畢竟Stack也是通過數據去實現的。
package com.sysway.ui.widget;import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;public class Traversal {/*** 通過棧實現對根節點下所有葉節點的遍歷* @param root 根節點* @return 葉節點集合*/private static List<TreeNode> traversalByStack(TreeNode root) {List<TreeNode> results = new ArrayList<TreeNode>();Stack<TreeNode> stack = new Stack<TreeNode>();stack.push(root); // 將元素推入棧中while (!stack.isEmpty()) {TreeNode node = stack.pop(); // 取出棧頂元素,并將該元素從棧中刪除if (node.isLeaf()) { // 如果是葉節點results.add(node);}else {List<TreeNode> childrens = node.getChildrens(); // 取非葉節點的所有子節點stack.addAll(childrens); // 將所有子節點加入棧}}return results;}/*** 通過遞歸實現對根節點下所有葉節點的遍歷* @param root 根節點* @return 葉節點集合*/private static List<TreeNode> traversalByRecursion(TreeNode node) {List<TreeNode> results = new ArrayList<TreeNode>();if (node.isLeaf()) {results.add(node);}else {for (TreeNode children : node.getChildrens()) {results.addAll(traversalByRecursion(children));}}return results;}public static void main(String[] args) {TreeNode node1 = new TreeNode("1");TreeNode node2 = new TreeNode("2");TreeNode node3 = new TreeNode("3");TreeNode node4 = new TreeNode("4");TreeNode node5 = new TreeNode("5");TreeNode node6 = new TreeNode("6");node1.addChildren(node2, node3);node2.addChildren(node4, node5);node5.addChildren(node6);List<TreeNode> leafs = traversalByStack(node1);System.out.println("---------Stack");for (TreeNode leaf : leafs) {System.out.println(leaf.getData());}List<TreeNode> leafs2 = traversalByRecursion(node1);System.out.println("---------Recursion");for (TreeNode leaf : leafs2) {System.out.println(leaf.getData());}}}class TreeNode {private List<TreeNode> childrens;private String data;public TreeNode(String data) {this.data = data;}public void addChildren(TreeNode... children) {if (children == null || children.length < 1) {return;}if (childrens == null) {childrens = new ArrayList<TreeNode>();}childrens.addAll(Arrays.asList(children));}public List<TreeNode> getChildrens() {return childrens;}public String getData() {return data;}public boolean isLeaf() {return childrens == null || childrens.isEmpty();}
}
樹的結構如圖:
輸出結果如下:
---------Stack
3
6
4
---------Recursion
4
6
3
特別鳴謝yanan!
?