树
有许多逻辑关系并不是简单的线性关系。在实际场景中，常常存在着一对多，甚至是多对多的情况。树和图就是典型的非线性关系数据结构。
树和二叉树
树
树的定义如下：
树是n（n >= 0）个节点的有限集。当n = 0时，称为空树。在任意一个非空树中，有如下特点：
1 . 有且仅有一个特定的称为根的节点；
2 . 当n > 1时，其余节点可分为m（m > 0）个互不相交的有限集，每一个集合本身又是一个树，并称为根的子树；
如下，就是一个标准的树结构：
1
/ \
2 3
/ \ \
4 5 6
/|\
7 8 9
在上图中，节点1是根节点；节点5、6、7、8、9是树的末端，没有“孩子”，被称为叶子节点。子节点2和3以及两者下面的部分是根节点1的子树。节点4的上一级节点，是节点4的父节点；从节点4衍生出来的节点，是节点4的孩子节点；和节点4统计，由同一个父节点衍生出来的节点5，是节点4的兄弟节点。
树的最大层级数，被称为树的高度或深度。上面这个树的高度是4；
二叉树
二叉树是树的一种特殊形式。二叉，顾名思义，这种树的每个节点最多有两个孩子节点。注意，这里是最多有两个，也可能只有一个，或者没有孩子节点。
二叉树节点的两个孩子节点，一个被称为左孩子，一个被称为右孩子。这两个孩子节点的顺序是固定的，就像人的左手就是左手，右手就是右手。
二叉树还有两种特殊形式，一个叫做满二叉树，另一个叫做完全二叉树。
满二叉树
一个二叉树的所有非叶子节点都存在左右孩子，并且所有叶子节点都在同一层级上，那么这个树就是满二叉树。简单来说，满二叉树的每一个分支都是满的。
1
/ \
2 3
/ \ / \
4 5 6 7
/ \ / \ / \ / \
8 9 10 11 12 13 14 15
完全二叉树
对一个有n个节点的二叉树，按层级顺序编号，则所有节点的编号从1到n。如果这个树所有节点和同样深度的满二叉树的编号为从1到n的节点位置相同，则这个二叉树为完全二叉树。
1
/ \
2 3
/ \ / \
4 5 6 7
/ \ / \ /
8 9 10 11 12
在上面图中，二叉树编号从1到12的12个节点，和前面满二叉树的编号从1到12的节点位置完全对应。因此这个树是完全二叉树。
完全二叉树的条件没有满二叉树那么苛刻，满二叉树要求所有分支都是满的，而完全二叉树只需要保证最后一个节点之前的节点都齐全即可。
二叉树使用的存储结构：
1 . 链式存储结构；
2 . 数组；
链式存储是二叉树最直观的存储方式。链表是一对一的存储方式，每一个链表节点拥有data变量和一个指向下一个节点的next指针。二叉树稍微复杂一些，一个节点最多可以指向左右两个孩子，所以二叉树的每一个节点包含三个部分：
1 . 存储数据的data变量；
2 . 指向左孩子的left指针；
3 . 指向右孩子的right指针；
使用数组存储时，会按照层级顺序把二叉树的节点放到数组中对应的位置上。如果某一个节点的左孩子或者右孩子空缺，则数组的相应位置也空出来。
假设一个父节点的下标是parent，那么它的左孩子节点下标就是2 * parent + 1，右孩子节点下标就是2 * parent + 2；反过来，假设一个左孩子节点的下标是leftChild，那么它的父节点下标就是（leftChild -1） / 2；对于一个稀疏的二叉树来说，用数组表示法是非常浪费空间的。
二叉树的应用
二叉树最主要的应用还在于进行查找操作和维持相对顺序这两个方面。
查找
我们在这里介绍一种特殊的二叉树：二叉查找树；这种二叉树的主要作用就是进行查找操作。
二叉查找树在二叉树的基础上增加了以下几个条件：
1 . 如果左子树不为空，则左子树上所有节点的值均小于根节点的值；
2 . 如果右子树不为空，则右子树上所有节点的值均大于根节点的值；
3 . 左右子树也都是二叉查找树；
6
/ \
3 8
/ \ / \
2 4 7 9
/
1
对于一个节点分布相对均衡的二叉查找树来说，如果节点总数是n，那么搜索节点的时间复杂度就是O(logn)，和树的深度是一样的。
维持相对顺序
二叉查找树要求左子树小于父节点，右子树大于父节点，正是这样保证了二叉树的有序性。因此，二叉查找树还有另一个名字，二叉排序树。
二叉树的遍历
二叉树是典型的非线性数据结构，便利时需要把非线性关联的节点转化为一个现形的序列，以不同的方式来遍历，遍历出的序列顺序也不同。
二叉树的遍历有四种：
1 . 前序遍历；
2 . 中序遍历；
3 . 后序遍历；
4 . 层序遍历；
从更宏观的角度来看，二叉树的遍历归结为两大类：
1 . 深度优先遍历（前序遍历、中序遍历、后序遍历）；
2 . 广度优先遍历（层序遍历）；
深度优先遍历
深度优先，就是偏向于纵深，“一头扎到底”的访问方式。
前序遍历
二叉树的前序遍历，输出顺序是根节点、左子树、右子树。
上图就是一个二叉树的前序遍历，每个节点左侧的序号代表该节点的输出顺序。
中序遍历
二叉树的中序遍历，输出顺序是左子树、根节点、右子树；
上图就是一个二叉树的中序遍历，每个节点左侧的序号代表该节点的输出顺序。
首先访问根节点的左孩子，如果这个左孩子还拥有左孩子，则继续深入访问下去，一直找到不再有左孩子的节点，并输出该节点。
后序遍历
二叉树的后序遍历，输出顺序是左子树、右子树、根节点；
上图就是一个二叉树的后序遍历，每个节点左侧的序号代表了该节点的输出顺序。
广度优先遍历
如果说深度优先遍历是一个方向上“一头扎到底”，那么广度优先遍历就是现在各个方向上各走出一步，再在各个方向上走出第二步、第三步...一直到各个方向全部走完。
层序遍历，就是二叉树按照从根节点到叶子节点的层次关系，一层一层横向遍历各个节点。
上图就是一个二叉树的层序遍历，每个节点左侧的序号代表该节点的输出顺序。
二叉堆
二叉堆本质上是一种完全二叉树，分为两个类型：
1 . 最大堆；
2 . 最小堆；
最大堆的任何一个父节点的值，都大于或等于它左、右孩子节点的值。
最小堆的任何一个父节点的值，都小于或等于它左、右孩子节点的值。
二叉堆的根节点叫做堆顶。
最大堆和最小堆的特点决定了，最大堆的堆顶是整个堆中的最大元素，最小堆的堆顶是整个堆的最小元素。
对于二叉堆有如下操作：
1 . 插入节点；
2 . 删除节点；
3 . 构建二叉堆；
这几种操作都基于堆的自我调整。所谓堆的自我调整，就是把一个不符合堆性质的完全二叉树，调整成一个堆。
构建二叉树：就是把一个无序的完全二叉树调整为二叉堆，本质上就是让所有非叶子节点依次下沉。
二叉堆事实现堆排序及优先队列的基础。
优先队列
队列的特点是先进先出。入队列，将新元素置于队尾；出队列，对头元素最先被移出。
优先队列不再遵循先入先出的原则，而是分为两种情况：
1 . 最大优先队列，无论入队顺序如何，都是当前最大的元素优先出队；
2 . 最小优先队列，无论入队顺序如何，都是当前最小的元素优先出队；
优先队列的实现
可以用最大堆来实现最大优先队列，这样的话，每次入队操作就是堆的插入操作，每一次出队操作就是删除堆顶节点。
二叉堆节点“上浮”和“下沉”的时间复杂度都是O(logn)，所以优先队列入队和出队的时间复杂度也是O(logn)。
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-----------------------last line for now-----------------------