树这种数据结构模拟了自然界中树的概念，自然界中的树有根、叶子、枝干，数据结构中的树也是如此，只不过是倒过来。

• 节点：每一个元素
• 根节点：树的顶点（没有元素的节点）
• 叶子节点：每个分支的末端节点（没有子元素的节点）
• 兄弟节点：具有同一个父节点的子节点
• 高度：节点到叶子节点的最长路径
• 深度：根节点到这个节点所经历的边的个数
• 层：节点的深度加1

定义

二叉树每个节点最多有两个「分叉」，即两个子节点，分别是左子节点和右子节点，不过，二叉树并不要求每个节点都有两个子节点，有的节点只有左子结点，有的节点只有右子节点。

根据左右子节点的饱和度，又从二叉树中分出两种特殊的二叉树：

• 满二叉树：所有分支节点都有左右子节点，并且所有叶子节点都在同一层上
• 完全二叉树：一棵深度为 k 的有 n 个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树

特性

• 在第 i 层最多有 2i-1 个节点。
• 深度为 k 的二叉树最多有 2k-1 个节点。
• 对于任何一个二叉树，叶子节点数为 n0，度为 2 的节点数为 n2，则 n0 = n2+1。

存储

• 通过数组存储
• 通过链表存储

链表存储

Golang 示例：

// 二叉树
type TreeNode struct {
    Val int
    Left *TreeNode
    Right *TreeNode
}

// 初始化节点
func NewTreeNode(data int) *TreeNode {
    return &TreeNode{
        Val: data,
        Left: nil,
        Right: nil,
    }
}