函数式编程-高阶函数-二叉树

定义

• 所谓高阶，就是他是其他函数的使用者
• 柯里化就是 闭包 + 高阶函数的结合使用

内循环

需求

内循环-代码示例

对于调用者，不需要知道具体的遍历逻辑，只需要提供具体的处理逻辑就可以了

public static void main(String[] args) {

    List<Integer> list = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9);
    //需求： 逆序遍历集合，只项负责元素处理，不能改变集合
    hiOrder(list, System.out::println);
}


// 高阶函数的第二个参数是一个函数  暴露给调用者，让调用者自己去实现具体的业务逻辑
public static <T> void hiOrder(List<T> list, Consumer<T> consumer) {
    // 逆序遍历
    // 这种比遍历方式是针对ArrayList的，底层是数组结构
    // 面对的如果是链表结构，这种方式就不适用了
    // for (int i = list.size() - 1; i >= 0; i--) {
    //     System.out.println(list.get(i));
    // }

    // 这种方式是面向所有集合的，不管是数组还是链表
    // 迭代器器是可以传递参数的，可以指定从哪个位置开始遍历 从0开始 或者 从size开始
    ListIterator<T> integerListIterator = list.listIterator(list.size());
    while (integerListIterator.hasPrevious()) {
        T previous = integerListIterator.previous();
        consumer.accept(previous);
    }
}

二叉树遍历

需求

初步代码

• 定义一个二叉树类
• 根节点
• 节点类
• 遍历方式枚举类
• 主遍历：根据遍历方式选择遍历方法
• 前序遍历方法
• 中序遍历方法
• 后续遍历方法

public class BinaryTree {


    TreeNode root;

    public record TreeNode(int val, TreeNode left, TreeNode right) {
    }

    // 遍历方式
    public enum Order {
        // 前序遍历
        PREORDER,
        // 中序遍历
        INORDER,
        // 后序遍历
        POSTORDER
    }

    // 前序遍历记录一下完整的路径 另外两种就只记录遍历的路径
    public static void  traversal(Order order, TreeNode node, StringBuilder path, Consumer<TreeNode> consumer) {
    }


    // 前序遍历
    public static void preorderTraversal(TreeNode node, StringBuilder path, Consumer<TreeNode> consumer) {

    }

    // 中序遍历
    public static void inorderTraversal(TreeNode node, StringBuilder path, Consumer<TreeNode> consumer) {

    }

    // 后序遍历
    public static void postorderTraversal(TreeNode node, StringBuilder path, Consumer<TreeNode> consumer) {

    }


    // 主函数
    public static void main(String[] args) {
    }
}

主遍历方法

// 前序遍历记录一下完整的路径 另外两种就只记录遍历的路径
public static void  traversal(Order order, TreeNode node, StringBuilder path, Consumer<TreeNode> consumer) {
    switch (order) {
        case PREORDER -> preorderTraversal(node, path,consumer);
        case INORDER -> inorderTraversal(node, path,consumer);
        case POSTORDER -> postorderTraversal(node, path,consumer);
    }
}

前序遍历方法

// 前序遍历
public static void preorderTraversal(TreeNode node, StringBuilder path, Consumer<TreeNode> consumer) {
   if (node == null) {
       return;
   }
   // 第一次访问到这个节点 保存节点值
   consumer.accept(node);
   // 递归遍历左子树
   if (node.left != null) {
       preorderTraversal(node.left, path,consumer);
       consumer.accept(node); // 左子树遍历完了，记录当前节点 作为返回标记
   }
   // 递归遍历右子树
   if (node.right != null) {
       preorderTraversal(node.right, path,consumer);
       consumer.accept(node); // 右子树遍历完了，记录当前节点 作为返回标记
   }
}

中序遍历方法

// 中序遍历
public static void inorderTraversal(TreeNode node, StringBuilder path, Consumer<TreeNode> consumer) {
    if (node == null) {
        return;
    }
    // 递归遍历左子树
    if (node.left != null) {
        inorderTraversal(node.left, path,consumer);
    }
    // 保存节点值
    consumer.accept(node);
    // 递归遍历右子树
    if (node.right != null) {
        inorderTraversal(node.right, path,consumer);
    }
}

后序遍历方法

// 后序遍历
 public static void postorderTraversal(TreeNode node, StringBuilder path, Consumer<TreeNode> consumer) {
     if (node == null) {
         return;
     }
     // 递归遍历左子树
     if (node.left != null) {
         postorderTraversal(node.left, path,consumer);
     }
     // 递归遍历右子树
     if (node.right != null) {
         postorderTraversal(node.right, path,consumer);
     }
     // 保存节点值
     consumer.accept(node);
 }

主函数

• 其实将 处理逻辑抽象为 Consumer的时候，使用到了柯里化，因为path 变量明显不是作为参数传递给函数对象的，但是却出现在方法体重重作为逻辑的一部分
  

// 一个树的值 1 2 3 4 5 6
// 前序遍历 1 2 3 4 5 6 值左右
// 中序遍历 4 2 1 5 3 6 左值右
// 后序遍历 4 2 5 6 3 1 左右值
public static void main(String[] args) {
    TreeNode node6 = new TreeNode(6, null, null);
    TreeNode node5 = new TreeNode(5, null, null);
    TreeNode node4 = new TreeNode(4, null, null);
    TreeNode node3 = new TreeNode(3, node5, node6);
    TreeNode node2 = new TreeNode(2, node4, null);
    // 根节点 1
    TreeNode node1 = new TreeNode(1, node2, node3);

    // 定义一个StringBuilder 保存遍历的路径
    StringBuilder path = new StringBuilder();
    // 定义一个Consumer 存储对节点的操作  这个地方无意间就使用了柯里化 path就是外界的一个不可变参数
    Consumer<TreeNode> consumer = node -> path.append(node.val).append("-");
    traversal(Order.PREORDER,node1,path,consumer);
    // 去掉最后一个-
    path.deleteCharAt(path.length() - 1);
    System.out.println(path.toString());
}