二叉树 Binary Tree

为什么要有树结构

• 对于大量的输入数据，链表的线性访问时间 太慢，不宜使用
• 树结构本身是一种天然的组织结构
• 将数据使用树结构存储后，出奇的高效

二叉树的定义

• 和链表一样，动态数据结构
• 二叉树具有唯一根节点
• 二叉树每个节点最多有两个孩子，一个孩子都没有的节点通常称为叶子节点
• 二叉树每个节点最多只有一个父亲节点，整个二叉树中只有一个节点是没有父亲节点的，就是根节点

class Node {
    E e;
    Node left;//左孩子
    Node right;//右孩子
}

二叉树具有天然递归结构

链表也具有天然的递归结构，但由于链表是线性的，所以对于链表相关的操作，使用循环的方式完全可以处理；但对于树来说，使用递归的写法要比非递归的写法要简单很多的

• 每个节点的左子树也是二叉树
• 每个节点的右子树也是二叉树

每一棵二叉树它的左侧和右侧又分别连接了两颗二叉树，这两颗二叉树都是节点个数更小的两颗二叉树。

• 二叉树不一定是满二叉树，满二叉树是指除了叶子节点之外，都有两个孩子
• 一个节点也可以二叉树，只有一个节点也可以是链表
• null 空也可以是二叉树，空节点也可以是链表