树
概念
与 线性表 表示的一 一对应的线性关系不同，树表示的是数据元素之间更为复杂的非线性关系。
直观来看，树是以分支关系定义的层次结构。树在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可以用树的形象来表示。
简单来说，树表示的是一对多的关系。
定义（逻辑结构）
树(Tree)是n( n>=0 )个结点的有限集合，没有结点的树称为空树，在任意一颗非空树中：
- 有且仅有一个特定的称为根(root)的结点
- 当n>1的时，其余结点可分为 m( m>0 ) 个互不相交的有限集T1，T2，..., Tm，其中每一个集合 Ti 本身又是一棵树，并且称之为根的子树。
注意：树的定义是一个递归定义，即在树的定义中又用到树的概念。
二叉树
二叉树是一颗树，它的特点是每个结点至多有两颗子树（结点的度最大为 2 ）。并且，子树有左右之分，其次序不能颠倒（有序）。
二叉树有一下 5 种形态：
满二叉树
如果二叉树中除了叶子结点，每个结点的度都为 2，则此二叉树称为满二叉树。
完全二叉树
如果二叉树中除去最后一层节点为满二叉树，且最后一层的结点依次从左到右分布，则此二叉树被称为完全二叉树。
二叉树的重要信息
二叉树的存储
顺序存储
二叉树的顺序存储，是通过数组实现。我们将一棵树，按照完全二叉树进行编号，将编号为 i 的元素存放到数组索引为 i 的地方。如图：
缺点：当树比较稀疏时，将极大的浪费内存空间。在最坏的情况下，一颗只有 k 个结点的单支树，却需要一个长度为 2^k 的数组来存储。
非顺序存储
二叉树的非顺序存储，是以链表的形式来存储数据元素以及数据元素之间的关系。如图：
struct TreeNode {
struct TreeNode* left;
char key;
struct TreeNode* right;
}
链表的形式十分灵活，因此我们一般使用链表来实现二叉树。
二叉树的遍历
深度优先遍历
若限定先左后右：
-
先序（根）遍历---根左右
-
中序（根）遍历---左根右
-
后序（根）遍历---左右根
三者的区别主要在于访问根节点的先后顺序。
广度优先遍历
又叫层级遍历，简单来说，就是从下到上，从左到右依次遍历。
广度优先遍历是通过队列实现的，步骤：
1、将根结点入队
2、判断队列是否为空
是：结束遍历
否：出队列
判断出队列的结点是否有左孩子，有的话将左孩子入队
判断出队列的结点是否有右孩子，有的话将右孩子入队
回到 2
BST（二叉搜索树）
BST：Binary Search Tree
相关操作
插入
查找
删除
