宁波品牌网站建设公司,wordpress 图片裁剪,营销型网站建设有哪些平台,网络文化经营许可证全国有多少张说到数的遍历树#xff0c;长期以来的第一印象都是通过递归去实现。然而今天看了某位前辈的代码#xff0c;才发现使用栈去实现遍历是那么简单。理论上通过数组也是可以实现同等功能的#xff0c;毕竟Stack也是通过数据去实现的。
package com.sysway.ui.widget;import jav…说到数的遍历树长期以来的第一印象都是通过递归去实现。然而今天看了某位前辈的代码才发现使用栈去实现遍历是那么简单。理论上通过数组也是可以实现同等功能的毕竟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 ListTreeNode traversalByStack(TreeNode root) {ListTreeNode results new ArrayListTreeNode();StackTreeNode stack new StackTreeNode();stack.push(root); // 将元素推入栈中while (!stack.isEmpty()) {TreeNode node stack.pop(); // 取出栈顶元素并将该元素从栈中删除if (node.isLeaf()) { // 如果是叶节点results.add(node);}else {ListTreeNode childrens node.getChildrens(); // 取非叶节点的所有子节点stack.addAll(childrens); // 将所有子节点加入栈}}return results;}/*** 通过递归实现对根节点下所有叶节点的遍历* param root 根节点* return 叶节点集合*/private static ListTreeNode traversalByRecursion(TreeNode node) {ListTreeNode results new ArrayListTreeNode();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);ListTreeNode leafs traversalByStack(node1);System.out.println(---------Stack);for (TreeNode leaf : leafs) {System.out.println(leaf.getData());}ListTreeNode leafs2 traversalByRecursion(node1);System.out.println(---------Recursion);for (TreeNode leaf : leafs2) {System.out.println(leaf.getData());}}}class TreeNode {private ListTreeNode 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 ArrayListTreeNode();}childrens.addAll(Arrays.asList(children));}public ListTreeNode 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
