树的遍历

节点结构：

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    
    public TreeNode() {
    }
    
    public TreeNode(int x) {
        val = x;
    }
}

先序遍历

递归

public void preOrder(TreeNode tree) {
    if (tree == null) 
        return;
    processNode(tree); // 处理节点的逻辑抽象
    preOrder(tree.left);
    preOrder(tree.right);
}

非递归

public void preOrder(TreeNode tree) {
    if (tree == null)
        return;
    Stack<TreeNode> s = new Stack<>();
    s.push(tree); 
    while (!s.isEmpty()) {
        TreeNode node = s.pop();
        processNode(node); // 处理节点的逻辑抽象
        if (node.right != null) { // 先入栈右子节点
            s.push(node.right);
        }
        if (node.left != null) {
            s.push(node.left);
        }
    }
}

后序遍历

递归

public void postOrder(TreeNode tree) {
    if (tree == null) 
        return;
    postOrder(tree.left);
    postOrder(tree.right);
    processNode(tree); // 处理节点的逻辑抽象
}

非递归

public void postOrder(TreeNode tree) {
    if (tree == null)
        return;
    Stack<TreeNode> s1 = new Stack<>();
    Stack<TreeNode> s2 = new Stack<>();
    s1.push(tree); 
    while (!s1.isEmpty()) {
        tree = s1.pop();
        s2.push(tree);
        if (tree.left != null) {
            s1.push(tree.left); // 先入栈左子节点
        }
        if (tree.right != null) { 
            s1.push(tree.right);
        }
    }
    while (!s2.isEmpty()) {
        processNode(s2.pop()); // 处理节点的逻辑抽象
    }
}

中序遍历

递归

public void inOrder(TreeNode tree) {
    if (tree == null) 
        return;
    inOrder(tree.left);
    processNode(tree); // 处理节点的逻辑抽象
    inOrder(tree.right);
}

非递归

public void inOrder(TreeNode tree) {
    Stack<TreeNode> s = new Stack<>();
    while (tree != null || !s.isEmpty()) {
        while (tree != null) {
            s.push(tree);
            tree = tree.left;
        }
        if (!s.isEmpty()) {
            tree = s.pop();
            processNode(tree); // 处理节点的逻辑抽象
            tree = tree.right;
        }
    }
}

层序遍历

public void levelOrder(TreeNode tree) {
    if (tree == null)
        return;
    Queue<TreeNode> q = new LinkedList<>();
    q.add(tree);
    while (!q.isEmpty()) {
        tree = q.poll();
        processNode(tree); // 处理节点的逻辑抽象
        if (tree.left != null)
            q.add(tree.left);
        if (tree.right != null)
            q.add(tree.right);
    }
}

类库

有了上述遍历算法实现后，我们建立类库，主要是：（1）通过泛型增加程序的通用性，（2）面向接口编程，（3）能够被实际开发生产使用。

@FunctionalInterface
public interface Node<T> {
    T getValue();
}

import lombok.*;

@Data
@NoArgsConstructor
@AllArgsConstructor
@RequiredArgsConstructor
public class TreeNode<T> implements Node<T> {
    @NonNull protected T value;
    protected TreeNode left;
    protected TreeNode right;
}

@FunctionalInterface
public interface Visitor<T> {
    void process(Node<T> node);
}

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

@FunctionalInterface
public interface TreeVisitor<T> extends Visitor<T> {

    default void preOrder(TreeNode<T> tree) {
        preOrder(tree, false);
    }

    default void preOrder(TreeNode<T> tree, boolean recursive) {
        if (recursive)
            preOrderRecursive(tree);
        else
            preOrderNonRecursive(tree);
    }

    default void preOrderRecursive(TreeNode<T> tree) {
        if (tree == null)
            return;
        process(tree);
        preOrderRecursive(tree.getLeft());
        preOrderRecursive(tree.right);
    }

    default void preOrderNonRecursive(TreeNode<T> tree) {
        if (tree == null)
            return;
        Stack<TreeNode<T>> s = new Stack<>();
        s.push(tree);
        while (!s.isEmpty()) {
            TreeNode<T> node = s.pop();
            process(node);
            if (node.right != null) { // 先入栈右子节点
                s.push(node.right);
            }
            if (node.left != null) {
                s.push(node.left);
            }
        }
    }

    default void postOrder(TreeNode<T> tree) {
        postOrder(tree, false);
    }

    default void postOrder(TreeNode<T> tree, boolean recursive) {
        if (recursive) 
            postOrderRecursive(tree);
        else
            postOrderNonRecursive(tree);
    }

    default void postOrderRecursive(TreeNode<T> tree) {
        if (tree == null)
            return;
        postOrderRecursive(tree.left);
        postOrderRecursive(tree.right);
        process(tree);
    }

    default void postOrderNonRecursive(TreeNode<T> tree) {
        if (tree == null)
            return;
        Stack<TreeNode<T>> s1 = new Stack<>();
        Stack<TreeNode<T>> s2 = new Stack<>();
        s1.push(tree);
        while (!s1.isEmpty()) {
            tree = s1.pop();
            s2.push(tree);
            if (tree.left != null) {
                s1.push(tree.left); // 先入栈左子节点
            }
            if (tree.right != null) {
                s1.push(tree.right);
            }
        }
        while (!s2.isEmpty()) {
            process(s2.pop());
        }
    }
    
    default void inOrder(TreeNode<T> tree) {
        inOrder(tree, false);
    }

    default void inOrder(TreeNode<T> tree, boolean recursive) {
        if (recursive)
            inOrderRecursive(tree);
        else
            inOrderNonRecursive(tree);
    }
    
    default void inOrderRecursive(TreeNode<T> tree) {
        if (tree == null)
            return;
        inOrderRecursive(tree.left);
        process(tree);
        inOrderRecursive(tree.right);
    }

    default void inOrderNonRecursive(TreeNode<T> tree) {
        Stack<TreeNode<T>> s = new Stack<>();
        while (tree != null || !s.isEmpty()) {
            while (tree != null) {
                s.push(tree);
                tree = tree.left;
            }
            if (!s.isEmpty()) {
                tree = s.pop();
                process(tree);
                tree = tree.right;
            }
        }
    }

    default void levelOrder(TreeNode<T> tree) {
        if (tree == null)
            return;
        Queue<TreeNode<T>> q = new LinkedList<>();
        q.add(tree);
        while (!q.isEmpty()) {
            tree = q.poll();
            process(tree);
            if (tree.left != null)
                q.add(tree.left);
            if (tree.right != null)
                q.add(tree.right);
        }
    }
}

在测试中使用上面的类库：

import org.junit.jupiter.api.Test;

public class TestClass {
    @Test
    void test1() {
        TreeVisitor<Integer> visitor = (n) -> System.out.println(n.getValue());
        TreeNode<Integer> left = new TreeNode<>(2);
        TreeNode<Integer> right = new TreeNode<>(3);
        TreeNode<Integer> root = new TreeNode<>(1, left, right);

        visitor.inOrder(root);
    }

    @Test
    void test2() {
        TreeVisitor<Integer> visitor = node -> {
            TreeNode<Integer> tn = (TreeNode<Integer>) node;
            System.out.println(tn.getLeft());
        };
        TreeNode<Integer> left = new TreeNode<>(2);
        TreeNode<Integer> right = new TreeNode<>(3);
        TreeNode<Integer> root = new TreeNode<>(1, left, right);

        visitor.inOrder(root);
    }
}