设一个序列，任意一个元素的前序（如果有）都比该元素小，后序（如果有）都比该元素大，像这样：

将他们组合起来，得到一个多层的结构：

这种结构称为 树 。 其中，每个元素都称为节点。

用线连接的下层节点称为子节点，上图中节点 1 的子节点是 3 和 5 ，节点 3 的子节点的 2 和 4 ，节点 5 没有子节点。 用线连接的上层节点称为父节点，节点 2 和 4 的父节点是 3 ，节点 3 和 5 的父节点是 1 ，节点 1 没有父节点。

最上层的节点没有父节点，称为根节点，最下层的节点没有子节点，称为 叶节点。如果一棵树的根节点也是叶节点，那么这棵树仅有一个节点。

每个节点及与之连接的所有节点又可看成是一颗独立的树，称为该节点的子树，上图中 1,3,5 和 3,2,4 都可以构成独立的子树。

树的根节点是第一层，根节点的子节点是第二层，以此类推，组成树中节点的层次。若某节点在第 $l$ 层，那么他的子树的根节点在第 $l+1$ 层。树中节点的最大层次称为树的深度。如上图所示，根节点 1 在第一层，3 和 5 在第二层， 2 和 4 在第三层，树的深度是 $3$ 。

若一棵树的节点不是有序的，称为无序树 ，否则称有序树。上图的树是一颗有序树。若一颗树的最大子节点数为 $2$ ，则称这棵树是一个二叉树，如上图中的树就是一颗二叉树。

二叉树

二叉树是的任意一个节点的子树（如果有）都不超过 $2$ 颗。其定义如下：

public class Tree<T> {
    
    // 根节点
    private Node root;
    
    // 节点定义
    private class Node {
        
        // 节点的值
        private T value;
        
        // 左子节点
        private Node left;
        
        // 右子节点
        private Node right;
    }
}