数据结构之二叉树-轻识

树的基本定义

之前实现符号表中，不难看出，符号表的增删查操作，随着元素个数N的增多，其耗时也是线性增多的，时间复杂度都是O(n)，为解决这个问题，需要学习树这种数据结构。

树是由n个有限结点组成的一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树。

树具有以下特点：

每个结点有零个或多个子结点；
没有父结点的结点为根结点；
每一个非根结点只有一个父结点；
每个结点及后代结点整体上可以看作是一棵树，称为当前结点的父结点的一颗子树。

树的相关术语

结点的度：

一个结点含有子树的个数称为该结点的度。

叶结点：

度为0的结点称为叶结点。

分支结点:

度不为0的结点为分支结点。

结点的层次：

从根结点开始，根结点的层次为1，根的直接后继为2.

结点的层序编号：

将树中的结点，按照从上到下，从左到右的次序排成一个线性序号。

树的度：

树中所有结点的度的最大值。

树的高度(深度)：

树中结点的最大层次。

森林：

m（m>0）个互不相交的树的集合。将一颗非空树的根结点去掉，树就变成了森林。

孩子结点：

一个结点的之间后继称为该结点的孩子结点。

双亲结点（父结点）：

一个结点的直接前驱称为该结点的双亲结点。

兄弟结点：

同一双亲的孩子结点之间互称为兄弟结点。

二叉树的基本定义

二叉树就是度不超过2的树。（每个结点最多有两个子结点）

满二叉树：

一个二叉树，如果每一个层的结点树都达到最大值，则这个二叉树就是满二叉树。

完全二叉树:

叶结点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树。

二叉查找树创建

二叉树的结点类

类图：

代码实现：

static class Node<K,V>{
    private Node<K,V> left;
    private Node<K,V> right;
    private K key;
    private V value;

    public Node(K key,V value,Node<K,V> left,Node<K,V> right){
        this.key = key;
        this.value = value;
        this.left = left;
        this.right = right;
    }
}

二叉查找树类图

二叉查找树代码实现

public class BinaryTree<K extends Comparable<K>, V> {
    //记录树中元素个数
    private int size;
    //记录树的根节点
    private Node<K, V> root;

    /**
     * 构造方法
     */
    public BinaryTree() {
        this.size = 0;
        this.root = null;
    }

    /**
     * 向树中插入一个键值对
     *
     * @param key
     * @param value
     */
    public void put(K key, V value) {
        root = put(root, key, value);
    }

    /**
     * 给指定树上添加一个键值对，并返回新树
     *
     * @param node
     * @param key
     * @param value
     * @return
     */
    private Node<K, V> put(Node<K, V> node, K key, V value) {
        //如果是第一个结点，则作为根节点添加到树中
        if (node == null) {
            size++;
            return new Node<>(key, value, null, null);
        }
        int cmp = key.compareTo(node.key);
        if (cmp < 0) {
            //如果不是第一个结点，从根结点开始查找，如果比根节点的key小，就找根节点的左子树
            node.left = put(node.left, key, value);
        } else if (cmp > 0) {
            // 如果比根节点的key大则找根节点的右子树
            node.right = put(node.right, key, value);
        } else {
            //如果等于其中一个结点的key值，则更新对应的值。
            node.value = value;
        }
        return node;
    }

    /**
     * 根据key从树中查找对应的值
     *
     * @param key
     * @return
     */
    public V get(K key) {
        return get(root, key);
    }

    private V get(Node<K, V> node, K key) {
        if (node == null) {
            return null;
        }
        //从根结点开始
        int cmp = key.compareTo(node.key);
        if (cmp < 0) {
            //如果要查找的key小于当前结点的key，则继续查找当前节点左子树
            return get(node.left, key);
        } else if (cmp > 0) {
            //如果要查找的key大于当前结点的key，则继续查找当前节点右子树
            return get(node.right, key);
        } else {
            //如果要查找的key等于当前结点的key，则返回当前节点的值
            return node.value;
        }

    }

    /**
     * 删除树中对应key的结点
     *
     * @param key
     */
    public void remove(K key) {
        remove(root, key);
    }

    /**
     * 删除指定树下面对应key的结点
     *
     * @param node
     * @param key
     * @return
     */
    private Node<K, V> remove(Node<K, V> node, K key) {
        //如果树为null
        if (node == null) {
            return null;
        }
        //如果树不为null
        //从根结点开始
        int cmp = key.compareTo(node.key);
        if (cmp < 0) {
            //如果要查找的key小于当前结点的key，则继续查找当前节点左子树
            node.left = remove(node.left, key);
        } else if (cmp > 0) {
            //如果要查找的key大于当前结点的key，则继续查找当前节点右子树
            node.right = remove(node.right, key);
        } else {
            //元素个数-1
            size--;
            //如果要查找的key等于当前结点的key，则删除当前结点
            //如果左子树为null或者是叶子结点
            if (node.left == null) {
                return node.right;
            }
            //如果右子树为null或者是叶子结点
            if (node.right == null) {
                return node.left;
            }
            //如果左子树和有子树都不为空，找到右子树中最小的结点代替需要删除的结点
            Node<K, V> minNode = node.right;
            Node<K, V> minPreNode = node.right;
            while (minNode.left != null) {
                if (minNode.left.left == null) {
                    minPreNode = minNode;
                }
                minNode = minNode.left;
            }
            //删除minNode的父节点的指向
            minPreNode.left = null;
            //让minNode的右子树等于该删除结点的右子树
            minNode.left = node.left;
            //左子树等于该删除结点的左子树
            minNode.right = node.right;
            //让该删除结点的父节点指向x
            node = minNode;
        }
        return node;
    }

    public int size() {
        return size;
    }

    static class Node<K, V> {
        private Node<K, V> left;
        private Node<K, V> right;
        private K key;
        private V value;

        public Node(K key, V value, Node<K, V> left, Node<K, V> right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

}

二叉查找树其他便捷方法

查找二叉树中最小的键

比如我们经常需要查找排名第一的记录。

/**
 * 获取树中最小的键
 * @return
 */
public K min(){
    return min(root).key;
}

/**
 * 获取指定树中最小键所在的结点
 * @param node
 * @return
 */
private Node<K,V> min(Node<K,V> node){
    //树中最小的键是左子树中最左边的结点，可递归查找左子树
    if(node.left == null){
        return node;
    }
    return min(node.left);
}

查找二叉树中最大的键

比如我们经常需要查找最后一名的记录。

/**
 * 获取树中最大的键
 * @return
 */
public K max(){
    return max(root).key;
}

/**
 * 获取指定树中最大键所在的结点
 * @param node
 * @return
 */
private Node<K,V> max(Node<K,V> node){
    //树中最大的键是右子树中最右边的结点，可递归查找右子树
    if(node.right == null){
        return node;
    }
    return max(node.right);
}

二叉树的基础遍历

很多情况下，我们可能需要像遍历数组一样遍历树，但是树状结构和线性结构不一样，它没办法从头开始依此向后遍历，那么应该怎么遍历树。

我们可以把树简单理解成根节点、左子树和右子树组成，按照结点什么时候被访问，可以把二叉树的遍历分为以下三种方式：

前序遍历
先访问根节点，再访问左子树，最后访问有右子树
中序遍历
先访问左子树，再访问根节点，最后访问右子树
后续遍历
先访问左子树，再访问右子树，最后再访问根节点

前序遍历

前序遍历API：

public Queue preErgodic()：使用前序遍历，获取整个树中所有的键

private void preErgodic(Node node,Queue keys)：使用前序遍历，把指定树node中的所有键放入到keys队列中

实现步骤

把当前结点的key放入到队列中
找到当前结点的左子树，如果不为空，递归遍历左子树
找到当前节点的右子树，如果不为空，递归遍历右子树

代码：

/**
 * 前序遍历
 * -根左右
 *
 * @return
 */
public Queue<K> preErgodic() {
    Queue<K> keys = new Queue<>();
    preErgodic(root, keys);
    return keys;
}

/**
 * 使用前序遍历，把指定树node中的所有键放入到keys队列中
 * 根左右
 * @param node
 * @param keys
 */
private void preErgodic(Node<K, V> node, Queue<K> keys) {
    if (node == null) {
        return;
    }
    //把node结点的key放入keys中
    keys.enqueue(node.key);
    //递归遍历node结点的左子树
    if (node.left != null) {
        preErgodic(node.left, keys);
    }
    //递归遍历node结点的右子树
    if (node.right != null) {
        preErgodic(node.right, keys);
    }
}

中序遍历

中序遍历API：

public Queue midErgodic()：使用中序遍历，获取整个树中所有的键

private void midErgodic(Node node,Queue keys)：使用中序遍历，把指定树node中的所有键放入到keys队列中

实现步骤

找到当前结点的左子树，如果不为空，递归遍历左子树
把当前结点的key放入到队列中
找到当前节点的右子树，如果不为空，递归遍历右子树

代码：

/**
 * 中序遍历
 * - 左根右
 * @return
 */
public Queue<K> midErgodic() {
    Queue<K> keys = new Queue<>();
    midErgodic(root, keys);
    return keys;
}

/**
 * 使用中序遍历，把指定树node中的所有键放入到keys队列中
 * 左根右
 * @param node
 * @param keys
 */
private void midErgodic(Node<K, V> node, Queue<K> keys) {
    if (node == null) {
        return;
    }
    //递归遍历node结点的左子树
    if (node.left != null) {
        midErgodic(node.left, keys);
    }
    //把node结点的key放入keys中
    keys.enqueue(node.key);
    //递归遍历node结点的右子树
    if (node.right != null) {
        midErgodic(node.right, keys);
    }
}

后续遍历

后序遍历API：

public Queue afterErgodic()：使用后序遍历，获取整个树中所有的键

private void afterErgodic(Node node,Queue keys)：使用后序遍历，把指定树node中的所有键放入到keys队列中

实现步骤

找到当前结点的左子树，如果不为空，递归遍历左子树
找到当前节点的右子树，如果不为空，递归遍历右子树
把当前结点的key放入到队列中

代码：

/**
 * 后序遍历
 * - 左右根
 *
 * @return
 */
public Queue<K> afterErgodic() {
    Queue<K> keys = new Queue<>();
    afterErgodic(root, keys);
    return keys;
}

/**
 * 使用后序遍历，把指定树node中的所有键放入到keys队列中
 * 左右根
 *
 * @param node
 * @param keys
 */
private void afterErgodic(Node<K, V> node, Queue<K> keys) {
    if (node == null) {
        return;
    }
    //递归遍历node结点的左子树
    if (node.left != null) {
        afterErgodic(node.left, keys);
    }
    //递归遍历node结点的右子树
    if (node.right != null) {
        afterErgodic(node.right, keys);
    }
    //把node结点的key放入keys中
    keys.enqueue(node.key);
}

二叉树的层序遍历

从根结点（第一层）开始，依此向下，获取每一层所有结点的值。有二叉树如下：

那么层序遍历的结果是：EBGADFHC

层序遍历API：

public Queue layerErgodic()：使用层序遍历，获取整个树的键

实现步骤：

创建队列存储每一层的结点
使用循环从队列中弹出一个结点

获取当前结点的key
如果当前节点的左子节点不为空，则把左子节点放入队列
如果当前节点的右子节点不为空，则把右子节点放入队列

代码：

/**
 * 使用层序遍历，把指定树node中的所有键放入到keys队列中
 *
 * @return
 */
public Queue<K> layerErgodic() {
    //定义两个队列，一个用来存放key，一个用来存放结点
    Queue<K> keys = new Queue<>();
    Queue<Node<K, V>> nodes = new Queue<>();
    //默认，在队列中放入根结点
    nodes.enqueue(root);
    while (!nodes.isEmpty()) {
        //从队列中弹出结点，把key放入keys中
        Node<K, V> node = nodes.dequeue();
        keys.enqueue(node.key);
        //判断当前结点是否还有左子树，如果有则放入nodes中
        if (node.left != null) {
            nodes.enqueue(node.left);
        }
        //判断当前结点是否还有右子树，如果有则放入nodes中
        if (node.right != null) {
            nodes.enqueue(node.right);
        }
    }
    return keys;
}

二叉树的最大深度问题

需求：

给定一棵树，请计算树的最大深度。(树的根结点到最远叶子结点的最长路径上的结点数)

上面这棵树的最大深度为4

实现：

最大深度API:

public int maxDepth()：计算整个树的最大深度

private int maxDepth(Node node)：计算指定树node的最大深度

实现步骤：

如果根结点为null，则最大深度为0
计算左子树的最大深度
计算右子树的最大深度
比较左子树和右子树的最大深度，取较大值+1即为整个树的最大深度

代码：

/**
 * 获取整个树的最大深度
 *
 * @return
 */
public int maxDepth() {
    return maxDepth(root);
}

/**
 * 获取指定树的最大深度
 *
 * @param node
 * @return
 */
private int maxDepth(Node<K, V> node) {
    if (node == null) {
        return 0;
    }
    //node左子树的最大深度
    int maxL = 0;
    //node右子树的最大深度
    int maxR = 0;
    //计算node结点左子树的最大深度
    if (node.left != null) {
        maxL = maxDepth(node.left);
    }
    //计算node结点右子树的最大深度
    if (node.right != null) {
        maxR = maxDepth(node.right);
    }
    //比较左子树和右子树的最大深度，取较大值+1，返回
    return maxL > maxR ? maxL + 1 : maxR + 1;
}

折纸问题

需求：

请把一段纸条竖着放在桌子上，然后从纸条的下边向上边对折1次，压出折痕后展开，此时折痕是凹下去的，即折痕突起方向为纸条的背面。如果连续对折2次，压出折痕后展开，此时有三条折痕，从上到下依次是下折痕，下折痕，上折痕。

分析：

我们把对折后的纸张翻过来，让粉色朝下，这时把第一次对折产生的折痕为根节点，第二次对折产生的下折痕就是该节点的左子节点，上折痕为右子节点，这样就可以使用树形结构来描述对折后产生的折痕。

这颗树的特点是：

根结点为下折痕
左子结点为下折痕
右子结点为上折痕

代码实现：

public class PageFoldingTest {

    public static void main(String[] args) {
        //模拟折纸过程，产生树
        Node<String> tree = createTree(2);
        //遍历树，打印每个结点
        printTree(tree);
    }

    //通过模拟对折N次，产生树
    public static Node<String> createTree(int n){
        Node<String> root = null;
        if(n<=0){
            return null;
        }
        //第一次对折
        root = new Node<>("down",null,null);
        //不是第一次对折
        for (int i = 1; i < n; i++) {
            //定义一个辅助队列，通过层序遍历的思想，找到叶子结点，给叶子结点添加子结点
            Queue<Node<String>> queue = new Queue<>();
            queue.enqueue(root);
            //循环遍历队列
            while (!queue.isEmpty()) {
                //从队列中弹出一个结点
                Node<String> temp = queue.dequeue();
                //如果有左子结点，则把右子结点放入队列中
                if (temp.left != null){
                    queue.enqueue(temp.left);
                }
                //如果有右子结点，则把右子结点放入队列中
                if (temp.right != null){
                    queue.enqueue(temp.right);
                }
                //如果同时没有右子结点和左子结点，则证明该结点是叶子结点，只需要给该结点添加左子结点和右子结点即可
                if(temp.left == null && temp.right == null){
                    temp.left = new Node<>("down",null,null);
                    temp.right = new Node<>("up",null,null);
                }
            }
        }
        return root;
    }

    //打印树中每个结点，中序遍历。
    public static void printTree(Node<String> tree){
        if(tree == null){
            return;
        }
        Queue<Node<String>> queue = new Queue<>();
        //打印左子树的每个结点
        if(tree.left != null){
            printTree(tree.left);
        }
        //打印当前结点
        System.out.print(tree.item+"\t");
        //打印右子树的每个结点
        if(tree.right != null){
            printTree(tree.right);
        }
    }

    //结点类
   private static class Node<T>{
        //存储元素
        private T item;
        private Node<T> left;
        private Node<T> right;

        public Node(T item, Node<T> left, Node<T> right) {
            this.item = item;
            this.left = left;
            this.right = right;
        }
    }
}