二叉树

定义

二叉树是一棵树，其中每个节点都不能有多于两个的儿子。

实现

二叉树的节点就是由element（元素）的信息加上两个到其他节点的引用（left和right）组成的结构。二叉树可以由根节点表示。

class Node<E extends Comparable<E>> {
    E value;
    Node<E> left;
    Node<E> right;
    Node(E value) {
        this.value = value;
        left = null;
        right = null;
    }
}

二叉树的各种遍历

深度优先遍历
深度优先遍历又可以分为前序遍历，中序遍历，后序遍历，这里介绍递归和非递归两种方式实现三种深度优先遍历。

递归方式：

/**
     * 先序遍历二叉树（递归）
     * @param node
     */
    public void preOrderTraverse(Node<E> node) {
        System.out.print(node.value + " ");
        if (node.left != null)
            preOrderTraverse(node.left);
        if (node.right != null)
            preOrderTraverse(node.right);
    }

    /**
     * 中序遍历二叉树（递归）
     * @param node
     */
    public void inOrderTraverse(Node<E> node) {
        if (node.left != null)
            inOrderTraverse(node.left);
        System.out.print(node.value + " ");
        if (node.right != null)
            inOrderTraverse(node.right);
    }

    /**
     * 后序遍历二叉树（递归）
     * @param node
     */
    public void postOrderTraverse(Node<E> node) {
        if (node.left != null)
            postOrderTraverse(node.left);
        if (node.right != null)
            postOrderTraverse(node.right);
        System.out.print(node.value + " ");
    }

非递归方式
深度优先遍历的实现一般使用Stack。

 /**
     * 先序遍历二叉树（非递归）
     * @param root
     */
    public void preOrderTraverseNoRecursion(Node<E> root) {
        LinkedList<Node<E>> stack = new LinkedList<Node<E>>();
        Node<E> currentNode = null;
        stack.push(root);
        while (!stack.isEmpty()) {
            currentNode = stack.pop();
            System.out.print(currentNode.value + " ");
            if (currentNode.right != null)
                stack.push(currentNode.right);
            if (currentNode.left != null)
                stack.push(currentNode.left);
        }
    }

    /**
     * 中序遍历二叉树（非递归）
     * 算法:
     * 1.遍历到最左节点, 入栈路径上的左节点;
     * 2.出栈并打印当前节点, 对此节点的右节点重复上述过程;
     * @param root
     */
    public void inOrderTraverseNoRecursion(Node<E> root) {
        LinkedList<Node<E>> stack = new LinkedList<Node<E>>();
        Node<E> currentNode = root;
        while (currentNode != null || !stack.isEmpty()) {
            // 一直循环到二叉树最左端的叶子结点(currentNode是null)
            while (currentNode != null) {
                stack.push(currentNode);
                currentNode = currentNode.left;
            }
            currentNode = stack.pop();
            System.out.print(currentNode.value + " ");
            currentNode = currentNode.right;
        }
    }

    /**
     * 后序遍历二叉树（非递归）
     * 算法:
     * 1. 遍历到最左节点, 入栈路径上的节点;
     * 2. 出栈当前节点, 有如下两种处理情况
     *    A) 直接打印的情况: 当前节点的右节点为null(说明当前节点是个左节点) 或者 当前节点的右节点为上一个打印的节点(说明当前节点是个根节点, 且左右分支都已经打印完毕)
     *    B) 重新入栈, 先处理右节点(重复上述过程)的情况: 当前节点的右节点不为null且尚未打印
     * @param root
     */
    public void postOrderTraverseNoRecursion(Node<E> root) {
        LinkedList<Node<E>> stack = new LinkedList<Node<E>>();
        Node<E> currentNode = root;
        Node<E> lastOutput = null;
        while (currentNode != null || !stack.isEmpty()) {
            // 一直循环到二叉排序树最左端的叶子结点(currentNode是null)
            while (currentNode != null) {
                stack.push(currentNode);
                currentNode = currentNode.left;
            }
            currentNode = stack.pop();

            // 当前结点没有右结点 或者 当前节点的右节点是上一个已经输出的结点, 则输出当前结点
            while (currentNode.right == null || currentNode.right == lastOutput) {
                System.out.print(currentNode.value + " ");
                lastOutput = currentNode;
                if (stack.isEmpty()) {
                    return; // root已输出, 则遍历结束
                }
                currentNode = stack.pop();
            }

            stack.push(currentNode); // 还有右结点没有遍历, 不能立刻打印, 所以重新入栈, 先处理右节点
            currentNode = currentNode.right;
        }
    }

广度优先遍历
广度优先遍历一般使用队列Queue。

/**
     * 广度优先遍历二叉树，又称层次遍历二叉树
     * @param root
     */
    public void breadthFirstTraverse(Node<E> root) {
        Queue<Node<E>> queue = new LinkedList<Node<E>>();
        Node<E> currentNode = null;
        queue.offer(root);
        while (!queue.isEmpty()) {
            currentNode = queue.poll();
            System.out.print(currentNode.value + " ");
            if (currentNode.left != null)
                queue.offer(currentNode.left);
            if (currentNode.right != null)
                queue.offer(currentNode.right);
        }
    }