一棵树是n(n >；当n=0时，有限集=0)的节点称为空树。在任何非空树中，它具有以下特征:
1，只有一个特定的节点叫根。
2.当n >时；1，其余节点可分为m(m >；0)不相交的有限集，每个集合本身就是一棵树，称为根的子树。
相互依赖的节点
树的最大层次树被称为树的高度或深度。
树的每个节点最多有2个子节点。
一种特殊形式的树。树的每个节点最多有2个子节点。
二叉树的两个子节点，一个叫左子，一个叫右子。这两个子节点的顺序是固定的。
二叉树有两种特殊形式:完全二叉树和完全二叉树。
全二叉树:一棵二叉树的所有非叶节点都有左右子，所有叶节点都连接在同一层。简而言之，满二叉树的每个分支都是满的。
完全二叉树:对于一棵有n个节点的二叉树，按层次顺序编号，所有节点从1到n编号，如果这棵树的所有节点与一棵深度相同的完全二叉树的从1到n编号的节点位置相同，那么这棵二叉树就是完全二叉树。
如果一棵树是完全二叉树，那么它一定是完全二叉树。反之，不一定。
存储在内存中:
为什么是这样的设计？定位子节点和父节点更方便。
如果父节点的下标是parent，那么左边子节点的下标是2 parent+1，右边子节点的下标是2 parent+2。
另一方面，如果leftChild节点下标是leftchild，那么父节点下标是(leftChild-1)/2。
稀疏二叉树，用数组表示会浪费空间。
二叉树的应用:搜索操作和保持相对顺序。
1，搜索
二叉查找树在二叉树的基础上增加了以下条件:
如果左子树不为空，则左子树上所有节点的值都小于根节点的值；
如果右子树不为空，则右子树上所有节点的值都大于根节点的值；
左右子树也是二分搜索法树。
对于节点分布相对均衡的二叉查找树，如果节点总数为n，那么搜索节点的时间复杂度为O(logn)，与树的深度相同。
2、保持相对顺序(插入)
二叉查找树的特性保证了二叉树的顺序，所以又有了一个名字:二叉排序树。
在插入过程中，可能需要二叉树进行自平衡，比如下面这种情况:
如图所示，不仅树看起来很怪异，查询节点的时间复杂度也退化为O(n)。
自我平衡二叉树的方法有很多，比如红黑树，AVL树，树堆。
二叉树的遍历:
从节点之间的位置关系来看:
*序遍历:输出顺序:根节点，左子树，右子树。
*按中间顺序遍历:输出顺序:左子树、根节点、右子树。
*后序遍历:输出顺序:左子树，右子树，根节点。
*序列遍历:按照根节点到叶节点的层次关系，逐层水平遍历每个节点。
从更宏观的角度来看:
*深度优先遍历(前中后遍历，前中后是相对根节点)
*广度优先遍历(顺序遍历)
二叉堆:本质上是一个完整的二叉树。
二叉堆本质上是一棵完整的二叉树，可以分为两种类型:
最大堆:任一父节点的值大于或等于其左右子节点的值；
最小堆:任何父节点的值小于或等于其左右子节点的值。
二进制堆的根节点称为堆顶。最大堆的顶部是整个堆中最大的元素，最小堆的顶部是整个堆中最小的元素。
虽然二进制堆是一棵完整的二叉树，但是它的存储方式不是链式存储，而是顺序存储，如下图所示:
假设父节点的下标是parent，其左子节点的下标是2 * parent+1，其右子节点的下标是2 * parent+2。
二进制堆的三个操作(假设最小堆):
1.插入节点:时间复杂度O(logn)
插入一个节点是通过浮动来完成的:当一个二进制堆被插入到一个节点中时，插入位置是一个完整二叉树的最后一个位置，该节点与其父节点进行比较。如果节点比它的父节点小，它应该与其父节点交换，直到堆的顶部位置被比较。
2.删除节点:时间复杂度O(logn)
删除一个节点是通过“下沉”来完成的:要删除的节点被视为堆的顶部，只看到该节点及其下面的部分。因为堆的顶部元素将被删除，所以使用最后一个节点元素来替换堆的顶部元素，并将被替换的元素与其左右子树进行比较。如果左右子节点中最小的一个小于该节点，则该节点“下沉”直到叶节点。
3.构建二进制堆:时间复杂度O(n)
构建二叉堆，即把一棵无序的完全二叉树调整成二叉堆，本质上是让所有非叶节点一次性“下沉”。
优先级队列不再遵循先进先出的原则，而是分为两种情况:
最大优先级队列，不考虑队列顺序，是目前最大的元素优先级队列；
最小优先级队列，不考虑队列顺序，是目前最小的元素优先级队列。
二进制堆节点“浮”和“沉”的时间复杂度为O(logn)，那么优先级队列排队和出队的时间复杂度为O(logn)。
/QQ _ 28958301/文章/详情/91590545