二叉树的构建
二叉树的遍历
- 深度优先遍历
- 广度优先遍历

二叉树（Binary Tree）是指树中的所有节点的度都不大于2的树，也就是说，二叉树中的所有节点最多只有2个子节点。二叉树的每个节点有左树和右树之分，而节点的左树和右树同样也是二叉树。

二叉树有几个特殊的类型：

满二叉树，二叉树中只包含度为0和2的节点，并且度为0的节点都在同一层上，这样的二叉树就被称为满二叉树。
完全二叉树，深度为k，有n个节点的二叉树，除第k层以外，其他各层的节点数都达到最大数量，第k层只有叶子节点，且第k层的叶子节点是从左至右依次排布，即为完全二叉树。完全二叉树的特点是叶子节点只可能出现在层级最大的两层上。
扩充二叉树，对已有二叉树进行扩充，直到所有的节点都变为度数为2的分支节点。
平衡二叉树，树的任意节点的左右两个子树的高度差的绝对值不超过1。

完全二叉树可以存放在一位数组中，堆排序所使用的数据结构也是完全二叉树。以下分别是完全二叉树和满二叉树、平衡二叉树的示意。
二叉树类型.svg

二叉树的构建

要在代码中构建一个二叉树，首先就要从构建二叉树所用的数据结构开始。要构建一个二叉树，最简单的方法是构建一个节点类。

public class Node {
    private Node leftChild;
    private Node rightChild;
    private Node parent;
    private Integer value;
    public Node(Integer value) {
        this.value = value;
    }
    public void attachLeftChild(Node child) {
        this.leftChild = child;
        this.leftChild.setParent(this);
    }
    public void attachRightChild(Node child) {
        this.rightChild = child;
        this.rightChild.setParent(this);
    }
    public Optional<Node> getLeftChild() {
        return Optional.ofNullable(this.leftChild);
    }
    public Optional<Node> getRightChild() {
        return Optional.ofNullable(this.rightChild);
    }
    public bool isLeaf() {
        return Objects.isNull(this.leftChild) && Objects.isNull(this.rightChild);
    }
    public Optional<Node> getParent() {
        return Optional.ofNullable(this.parent);
    }
    public void setParent(Node parent) {
        this.parent = parent;
    }
    public Integer getValue() {
        return this.value;
    }
}

这样的一个节点类是最简单的二叉树节点实现，它能够保存自己的值，也可以持有左孩子和右孩子，还可以回溯自己的父级节点。有了这个节点类，接下来就可以来用它构造一棵二叉树了。

二叉树的遍历

二叉树的遍历是指不重复的访问二叉树中的所有节点，二叉树的遍历最常用的方法是采用递归。因为二叉树是在深度和广度两个方向上延伸的，所以对于二叉树的遍历就有深度优先和广度优先两种遍历策略。

深度优先遍历

深度优先遍历就是先沿着层级增加的路径，按一定顺序逐一访问深层级的节点。根据二叉树中每个根节点、左孩子和右孩子的访问顺序不同，二叉树的深度优先遍历可以分为前序遍历、中序遍历和后序遍历。

前序遍历

前序遍历是指使用先访问根节点，再访问左子树，最后访问右子树的顺序。以下是前序遍历方法。

public class BinaryTree {
    public void preOrderTraversal(Node pointer) {
        System.out.println(pointer.getValue());
        pointer.getLeftChild.ifPresent(this::preOrderTraverse);
        pointer.getRightChild.ifPresent(this::preOrderTraverse);
    }
}

中序遍历

中序遍历是指使用先访问左子树，再访问根节点，最后访问右子树的顺序。以下是中序遍历方法。

public class BinaryTree {
    public void inOrderTraversal(Node pointer) {
        pointer.getLeftChild().ifPresent(this::inOrderTraverse);
        System.out.println(pointer.getValue());
        pointer.getRightChild().ifPresent(this::inOrderTraverse);
    }
}

后序遍历

后序遍历是指使用先访问左子树，再访问右子树，最后访问根节点的顺序。以下是后序遍历方法。

public class BinaryTree {
    public void postOrderTraversal(Node pointer) {
        pointer.getLeftChild().ifPresent(this::postOrderTraverse);
        pointer.getRightChild().ifPresent(this::postOrderTraverse);
        System.out.println(pointer.getValue());
    }
}

不使用递归的遍历方法

在使用递归进行二叉树遍历的时候，递归的特点使得我们可以以非常清晰的条理完成整棵二叉树的遍历，但是递归的缺点就是在二叉树深度较大的时候，会非常消耗系统资源。所以在追求性能或者比较均衡的实现的时候，可以借助栈来实现不使用递归的遍历。以下以前序遍历为例来展示不使用递归的二叉树遍历方法。

public class BinaryTree {
    public void preOrderTraversal(Node root) {
        LinkedList<Node> queue = new LinkedList<>();
        queue.push(root);
        while (!queue.isEmpty()) {
            Node pointer = queue.pollLast();
            System.out.println(pointer.getValue());
            pointer.getRightChild().ifPresent(queue::push);
            pointer.getLeftChild().ifPresent(queue::push);
        }
    }
}

栈是一个FILO的结构，所以在完成前序遍历的时候，需要先将最后遍历的右子树压栈。如果要使用FIFO结构的队列，则可以直接使用递归遍历中的顺序将遍历任务逐步排入。

广度优先遍历

相比深度优先遍历，广度优先遍历就比较容易理解了。广度优先遍历实际上就是逐层扫描树，一层一层的遍历，直到最大深度。广度优先遍历一般都采用一个队列来完成遍历任务，递归在广度优先中并不好用。使用队列来实现广度优先遍历的原理是将每一个节点的左孩子和右孩子依次排入队列，这样在进行处理时就会首先计算一层的节点。以下依旧提供一个简单的示例。

public class BinaryTree {
    public void breadthFirstTraversal(Node root) {
        LinkedList<Node> queue = new LinkedList<>();
        queue.push(root);
        while (!queue.isEmpty()) {
            Node pointer = queue.pollFirst();
            System.out.println(pointer.getValue());
            pointer.getLeftChild().ifPresent(queue::push);
            pointer.getRightChild().ifPresent(queue::push);
        }
    }
}