随笔——如何优雅的遍历树结构

2019-08-29 Algorithm Java

  在编程生涯中我们会碰上各式各样的数据结构，简单的如数组、列表、字典，复杂一点的如树结构、图等等，本文将基于Java8讲述如何优雅的实现树的遍历、打印、平铺、聚合操作。

树结构描述

  本文围绕的树结构大体样例如下所示，这种结构常用于我们Web系统的菜单数据结构的存储，在数据库我们一般是平铺存储，但是使用时需要聚合成树状结构，在平时的实体设计中，关于子项的key不一定就叫childrens，所以本文最终设计的工具类也需要设计的更为通用

private Integer id;
private String name;
private Integer parentId;
private List<Node> childrens;

常用的遍历方式

递归

public static void traversing(List<Node> root) {
    for (Node node : root) {
        List<Node> childres = node.getChildrens();
        if (childres != null && childres.size() > 0) {
            traversing(childres);
        }
    }
}

栈

public static void traversing(List<Node> root) {
    Stack<Node> stack = new Stack<>();
    root.forEach(stack::push);
    while (!stack.isEmpty()) {
        Node o = stack.pop();
        List<Node> childrens = o.getChildrens();
        if (childrens != null && childrens.size() > 0) {
            childrens.forEach(stack::push);
        }
    }
}

如何通用

思考

  要做到工具通用就要考虑哪一块是变化的部分，在我们的树结构实体模型中有几个核心的字段，这几个字段每个人在设计自己业务模型中都可能不一样，但却是必然存在的

  • 子节点字段
  • 节点ID字段
  • 父节点ID字段

需要统一这种变化的部分我们一般会有两种解决办法

  1. 建立一个TreeNode接口，写上三个函数让用户设计实体时必须去实现此接口才能用你的工具类
  2. 利用函数式编程的思想将这几个获取操作抽象成参数传递，显然，这种办法对用户来说是更加友好的，所以我们这次会基于此方案来实现工具类

在实现之前我们需要先了解一下Java中的函数式编程接口

Java8 function api介绍

Java8的java.util.function包下提供了很多支持函数式编程的类，可以帮我们很好的抽象变化的部分，我们先看一下function api的归纳，Java8主要提供了以下类来支持函数式编程，其中标了重点的是这次编写工具所使用到的类。

类 描述
BiConsumer<T,U> 代表了一个接受两个输入参数的操作，并且不返回任何结果
BiFunction<T,U,R> 代表了一个接受两个输入参数的方法，并且返回一个结果
BinaryOperator 代表了一个作用于于两个同类型操作符的操作，返回了操作符同类型的结果
BiPredicate<T,U> 代表了一个两个参数的boolean值方法
BooleanSupplier 代表了boolean值结果的提供方
Consumer 代表了接受一个输入参数并且无返回的操作
DoubleBinaryOperator 代表了作用于两个double值操作符的操作，并且返回了一个double值的结果
DoubleConsumer 代表一个接受double值参数的操作，并且不返回结果
DoubleFunction 代表接受一个double值参数的方法，并且返回结果
DoublePredicate 代表一个拥有double值参数的boolean值方法
DoubleSupplier 代表一个double值结构的提供方
DoubleToIntFunction 接受一个double类型输入，返回一个int类型结果
DoubleToLongFunction 接受一个double类型输入，返回一个long类型结果
DoubleUnaryOperator 接受一个参数同为类型double,返回值类型也为double
Function<T,R> 接受一个输入参数，返回一个结果
IntBinaryOperator 接受两个参数同为类型int,返回值类型也为int
IntConsumer 接受一个int类型的输入参数，无返回值
IntFunction 接受一个int类型输入参数，返回一个结果
IntPredicate 接受一个int输入参数，返回一个布尔值的结果
IntSupplier 无参数，返回一个int类型结果
IntToDoubleFunction 接受一个int类型输入，返回一个double类型结果
IntToLongFunction 接受一个int类型输入，返回一个long类型结果
IntUnaryOperator 接受一个参数同为类型int,返回值类型也为int
LongBinaryOperator 接受两个参数同为类型long,返回值类型也为long
LongConsumer 接受一个long类型的输入参数，无返回值
LongFunction 接受一个long类型输入参数，返回一个结果
LongPredicate 接受一个long输入参数，返回一个布尔值类型结果
LongSupplier 无参数，返回一个结果long类型的值
LongToDoubleFunction 接受一个long类型输入，返回一个double类型结果
LongToIntFunction 接受一个long类型输入，返回一个int类型结果
LongUnaryOperator 接受一个参数同为类型long,返回值类型也为long
ObjDoubleConsumer 接受一个object类型和一个double类型的输入参数，无返回值
ObjIntConsumer 接受一个object类型和一个int类型的输入参数，无返回值
ObjLongConsumer 接受一个object类型和一个long类型的输入参数，无返回值
Predicate 接受一个输入参数，返回一个布尔值结果
Supplier 无参数，返回一个结果
ToDoubleBiFunction<T,U> 接受两个输入参数，返回一个double类型结果
ToDoubleFunction 接受一个输入参数，返回一个double类型结果
ToIntBiFunction<T,U> 接受两个输入参数，返回一个int类型结果
ToIntFunction 接受一个输入参数，返回一个int类型结果
ToLongBiFunction<T,U> 接受两个输入参数，返回一个long类型结果
ToLongFunction 接受一个输入参数，返回一个long类型结果
UnaryOperator 接受一个参数为类型T，返回值类型也为T

工具类设计

  1. 利用Function<T,R>来抽象子节点/节点Key/节点父节点Key的获取逻辑
  2. 利用Consumer<T>来抽象遍历到节点后的逻辑操作，比如打印/插入其他数据结构
  3. 利用BiConsumer<T,U>来抽象节点的写入操作，如聚合树时的子节点写入操作
  4. 节点遍历方面使用栈来实现，防止在树结构深度比较大时爆栈
/**
 * @author JianhuiChen
 * @description 树状结构工具类 提供通用树结构的平铺/聚合方法
 * @date 2019-08-29
 */
public class TreeUtil {

    /**
     * 遍历树结构
     *
     * @param root              节点树结构
     * @param loadChildrenNodes 加载树的子节点列表函数 接收一个节点 返回节点的子结构
     * @param behavior          遍历到的节点行为
     * @param <T>               树节点对象
     */
    public static <T> void traversing(List<T> root, Function<T, List<T>> loadChildrenNodes, Consumer<T> behavior) {
        Stack<T> stack = new Stack<>();
        root.forEach(stack::push);
        while (!stack.isEmpty()) {
            T o = stack.pop();
            behavior.accept(o);
            List<T> childrens = loadChildrenNodes.apply(o);
            if (childrens != null && childrens.size() > 0) {
                childrens.forEach(stack::push);
            }
        }
    }

    /**
     * 平铺树结构
     *
     * @param root              节点树结构
     * @param loadChildrenNodes 加载树的子节点列表函数 接收一个节点 返回节点的子结构
     * @param <T>               树节点对象
     * @return 平铺结构
     */
    public static <T> List<T> tileTree(List<T> root, Function<T, List<T>> loadChildrenNodes) {
        List<T> list = new ArrayList<>();
        traversing(root, loadChildrenNodes, list::add);
        return list;
    }

    /**
     * 打印树信息
     *
     * @param list              树结构列表
     * @param loadChildrenNodes 加载树的子节点列表函数 接收一个节点 返回节点的子结构
     * @param <T>               树节点对象
     */
    public static <T> void printTree(List<T> list, Function<T, List<T>> loadChildrenNodes) {
        System.out.println("---------- Tree Nodes Print ----------");
        traversing(list, loadChildrenNodes, System.out::println);
        System.out.println("---------- Tree Nodes Print ----------");
    }

    /**
     * 聚合树结构
     *
     * @param list          节点列表结构
     * @param loadKey       节点唯一key读取 接收一个节点 返回节点的唯一key
     * @param loadParentKey 节点父节点key读取 接收一个节点 返回节点的父节点key
     * @param write         节点子项写入函数 接收待写入节点与节点子项 负责将子节点写入
     * @param <T>           节点对象
     * @param <R>           节点唯一key对象
     * @return 树结构
     */
    public static <T, R> List<T> polymerizationTree(List<T> list, Function<T, R> loadKey, Function<T, R> loadParentKey, BiConsumer<T, List<T>> write) {
        List<T> root = list.stream().filter(o -> loadParentKey.apply(o) == null).collect(Collectors.toList());
        Stack<T> stack = new Stack<>();
        root.forEach(stack::push);
        while (!stack.isEmpty()) {
            T o = stack.pop();
            R key = loadKey.apply(o);
            List<T> childrens = list.stream()
                    .filter(k -> key.equals(loadParentKey.apply(k)))
                    .collect(Collectors.toList());
            write.accept(o, childrens);
            if (childrens.size() > 0) {
                childrens.forEach(stack::push);
            }
        }
        return root;
    }

    public static void main(String[] args) {
        List<Node> listNodes = new ArrayList<>();
        listNodes.add(new Node(1, "根节点1", null));
        listNodes.add(new Node(2, "根节点2", null));
        listNodes.add(new Node(3, "根节点3", null));
        listNodes.add(new Node(4, "1-1", 1));
        listNodes.add(new Node(5, "1-2", 1));
        listNodes.add(new Node(6, "2-1", 2));
        listNodes.add(new Node(7, "3-1", 3));
        listNodes.add(new Node(8, "1-1-1", 4));
        listNodes.add(new Node(9, "1-1-2", 4));
        printTree(listNodes, Node::getChildrens);
        // 聚合
        List<Node> treeNodes = polymerizationTree(listNodes, Node::getId, Node::getParentId, Node::setChildrens);
        printTree(treeNodes, Node::getChildrens);
        // 平铺
        listNodes = tileTree(treeNodes, Node::getChildrens);
        printTree(listNodes, Node::getChildrens);
    }

    private static class Node {
        private Integer id;
        private String name;
        private Integer parentId;
        private List<Node> childrens;

        public Node(Integer id, String name, Integer parentId) {
            this.id = id;
            this.name = name;
            this.parentId = parentId;
        }

        public Integer getId() {
            return id;
        }

        public void setId(Integer id) {
            this.id = id;
        }

        public String getName() {
            return name;
        }

        public void setName(String name) {
            this.name = name;
        }

        public Integer getParentId() {
            return parentId;
        }

        public void setParentId(Integer parentId) {
            this.parentId = parentId;
        }

        public List<Node> getChildrens() {
            return childrens;
        }

        public void setChildrens(List<Node> childrens) {
            this.childrens = childrens;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "id=" + id +
                    ", name='" + name + '\'' +
                    '}';
        }
    }
}

推荐阅读