二叉排序树构造算法（数据结构堆(Heap)&排序&二叉树）
在我们描述堆之前 ，我们首先要明白一个概念 ，什么是树？
树的概念及结构
1.树的概念
树是一种非线性的数据结构 ，它是由n（n>=0）个有限结点组成一个具有层次关系的集合 。把它叫做树是因为它看起来像一棵倒挂的树 ，也就是说它是根在上 ，而叶在下的 。
有一个特殊的结点 ，称为根结点 ，根节点没有前驱结点 。除根节点外 ，其余结点被分成m(m > 0)个互不相交的集合T1 、T2 、…… 、Tm ，其中每一个集合Ti(1 <= i <= m)又是一棵结构与树类似的子树 。每棵子树的根结点有且只有一个前驱 ，但可以有0个或多个后继 。
由此可知 ，树是递归定义的 。
下面介绍一些与树相关的概念（以上面的树为例）：
（1）结点的度：一个节点含有的子树的个数称为该节点的度；如上图：A的为6 ，即B 、C 、D 、E 、F 、G 。
（2）叶结点：度为0的节点称为叶结点；如上图：B 、C 、H 、I 、K 、L 、M 、N 、P 、Q 为叶结点 。
（3）双亲结点或父结点：若一个节点含有子结点 ，则这个结点称为其子结点的父结点；如上图：A是B的父结点 。
（4）孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点；如上图：B是A的孩子节点 。
（5）兄弟结点：具有相同父结点的结点互称为兄弟结点； 如上图：B 、C是兄弟结点 。
（6）树的度：一棵树中 ，最大的节点的度称为树的度； 如上图：树的度为6 。
（7）结点的层次：从根开始定义起 ，根为第1层 ，根的子结点为第2层 ，以此类推 。
（8）树的高度或深度：树中结点的最大层次； 如上图：树的高度为4 。
（9）节点的祖先：从根到某一结点所经分支上的所有结点；如上图：D 、A是H的祖先；A是所有结点的公共祖先 。
（10）子孙：以某节点为根的子树中任一节点都称为该节点的子孙 。如上图：所有节点都是A的子孙 。
（11）森林：多棵互不相交的树的集合称为森林 。
2.树的表示方法
树由于不是线性结构 ，所以相对线性表 ，要存储 、表示就相对麻烦 ，实际中树有很多种表示方式 ，如：双亲表示法 ，孩子表示法 、孩子兄弟表示法等等 。这里简单地介绍其中最常用的孩子兄弟表示法 。
孩子兄弟表示法就是用孩子结点来找到下一层的结点 ，用兄弟结点来找到这一层其余的结点 ，结构如下 。
二叉树
1.二叉树概念及结构
概念：一棵二叉树是结点的一个有限集合 ，该集合为空 ，或者是由一个根节点加上两棵称为左子树和右子树的二叉树组成 。
二叉树的特点：
（1）每个结点最多有两棵子树 ，即二叉树不存在度大于2的结点 。
（2）二叉树的子树有左右之分 ，其子树的次序不能颠倒 。结构
特殊的二叉树：（1）满二叉树(Perfect Binary Tree)
每一层的结点数都达到最大值 ，则这个二叉树就是满二叉树 。
也就是说 ，如果一个二叉树的层数为K（根节点是第1层） ，且结点总数是(2^k) -1 ，则它就是满二叉树 ，也称为完美二叉树（2）完全二叉树(Complete Binary Tree)
完全二叉树是由满二叉树而引出来的 。对于深度为K的 、有n个结点的二叉树 ，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树 。 满二叉树是一种特殊的完全二叉树 。
完全二叉树的叶子结点只能出现在最下层和次下层 ，且最下层的叶子结点从左到右连续；前K-1层是满的二叉树 。换句话说 ，完全二叉树从根结点到倒数第二层满足完美二叉树 ，最后一层可以不完全填充 ，其叶子结点都靠左对齐 。
（3）完满二叉树(Full Binary Tree)
换句话说 ，所有非叶子结点的度都是2 。（只要你有孩子 ，你就必然是有两个孩子 。）
注：Full Binary Tree又叫做Strictly Binary Tree 。
什么是堆？
堆（英语：heap)是计算机科学中一类特殊的数据结构的统称 。堆通常是一个可以被看做一棵树的数组对象 。堆总是满足下列性质：
堆中某个节点的值总是不大于或不小于其父节点的值；
堆总是一棵完全二叉树 。将根节点最大的堆叫做最大堆或大根堆 ，根节点最小的堆叫做最小堆或小根堆 。常见的堆有二叉堆 、斐波那契堆等 。
堆是非线性数据结构 ，相当于一维数组 ，有两个直接后继 。
堆的定义如下：n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时 ，称之为堆 。
(ki <= k2i,ki <= k2i+1)或者(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4...n/2)
若将和此次序列对应的一维数组（即以一维数组作此序列的存储结构）看成是一个完全二叉树 ，则堆的含义表明 ，完全二叉树中所有非终端结点的值均不大于（或不小于）其左 、右孩子结点的值 。由此 ，若序列{k1,k2,…,kn}是堆 ，则堆顶元素（或完全二叉树的根）必为序列中n个元素的最小值（或最大值） 。
注意： 在二叉树中 ，若当前节点的下标为 i ， 则其父节点的下标为 i/2 ，其左子节点的下标为 i*2 ，其右子节点的下标为i*2+1；堆的插入：
每次插入都是将先将新数据放在数组最后 ，由于从这个新数据的父结点到根结点必然为一个有序的序列 ，现在的任务是将这个新数据插入到这个有序序列中——这就类似于直接插入排序中将一个数据并入到有序区间中 。我们通过一个插入例子来看看插入操作的细节 。我们将数字 16 插入到这个堆中：
堆的数组是：[ 10, 7, 2, 5, 1 ] 。
第一步是将新的元素插入到数组的尾部 ，数组变成：[ 10, 7, 2, 5, 1, 16 ]；
相应的树变成了：
16被添加最后一行的第一个空位 。
不行的是 ，现在堆属性不满足 ，因为2在16的上面 ，我们需要将大的数字在上面（这是一个最大堆）
为了恢复堆属性 ，我们需要交换16和2 。
现在还没有完成 ，因为10也比16小 。我们继续交换我们的插入元素和它的父节点 ，直到它的父节点比它大或者我们到达树的顶部 。这就是所谓的shift-up ，每一次插入操作后都需要进行 。它将一个太大或者太小的数字“浮起 ”到树的顶部 。
最后我们得到的堆：
现在每一个父节点都比它的子节点大 。
堆的删除：
堆中每次都只能删除堆顶元素 。为了便于重建堆 ，实际的操作是将最后一个数据的值赋给根结点 ，然后再从根结点开始进行一次从上向下的调整 。调整时先在左右子结点中找最小的 ，如果父结点比这个最小的子结点还小说明不需要调整了 ，反之将父结点和它交换后再考虑后面的结点 。相当于根结点数据的“下沉 ”过程 。我们将这个树中的 (10) 删除：
现在顶部有一个空的节点 ，怎么处理？
当插入节点的时候 ，我们将新的值返给数组的尾部 。现在我们来做相反的事情：我们取出数组中的最后一个元素 ，将它放到树的顶部 ，然后再修复堆属性 。
现在来看怎么shift-down(1) 。为了保持最大堆的堆属性 ，我们需要树的顶部是最大的数据 。现在有两个数字可用于交换7和2 。我们选择这两者中的较大者称为最大值放在树的顶部 ，所以交换7和1 ，现在树变成了：
继续堆化直到该节点没有任何子节点或者它比两个子节点都要大为止 。对于我们的堆 ，我们只需要再有一次交换就恢复了堆属性：
最大堆：
1.构造最大堆
原始数据为a[] = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7} ，采用顺序存储方式 ，对应的完全二叉树如下图所示：
基本思想：
首先将每个叶子节点视为一个堆 ，再将每个叶子节点与其父节点一起构造成一个包含更多节点的对 。所以 ，在构造堆的时候 ，首先需要找到最后一个节点的父节点 ，从这个节点开始构造最大堆；直到该节点前面所有分支节点都处理完毕 ，这样最大堆就构造完毕了 。
假设树的节点个数为n ，以1为下标开始编号 ，直到n结束 。对于节点i ，其父节点为i/2；左孩子节点为i*2 ，右孩子节点为i*2+1 。最后一个节点的下标为n ，其父节点的下标为n/2 。
我们边针对上边数组操作如下图所示 ，最后一个节点为7 ，其父节点为16 ，从16这个节点开始构造最大堆；构造完毕之后 ，转移到下一个父节点2 ，直到所有父节点都构造完毕 。
代码实现如下：
给定一个整形数组a[]={16,7,3,20,17,8} ，对其进行堆排序 。
堆排序是借助堆来实现的选择排序 ，思想同简单的选择排序 ，以下以大顶堆为例 。注意：如果想升序排序就使用大顶堆 ，反之使用小顶堆 。原因是堆顶元素需要交换到序列尾部 。
首先 ，实现堆排序需要解决两个问题：
1. 如何由一个无序序列键成一个堆？
2. 如何在输出堆顶元素之后 ，调整剩余元素成为一个新的堆？
第一个问题 ，可以直接使用线性数组来表示一个堆 ，由初始的无序序列建成一个堆就需要自底向上从第一个非叶元素开始挨个调整成一个堆 。
第二个问题 ，怎么调整成堆？首先是将堆顶元素和最后一个元素交换 。然后比较当前堆顶元素的左右孩子节点 ，因为除了当前的堆顶元素 ，左右孩子堆均满足条件 ，这时需要选择当前堆顶元素与左右孩子节点的较大者（大顶堆）交换 ，直至叶子节点 。我们称这个自堆顶自叶子的调整成为筛选 。
从一个无序序列建堆的过程就是一个反复筛选的过程 。若将此序列看成是一个完全二叉树 ，则最后一个非终端节点是n/2取底个元素 ，由此筛选即可 。举个栗子：
49,38,65,97,76,13,27,49序列的堆排序建初始堆和调整的过程如下：
动图演示:
（1）动画从一排数字开始（2）先将一排数字放入数组（这个数组看做堆） ，显然这个堆是不满足条件的
（3）从最后一个父节点开始对堆进行调整（heapify）使其满足堆的性质（绿色代表调整好了 ，浅蓝色表示正在调整）
（4）堆构建结束后将堆顶元素与最后一个节点交换 ，将最大值放在最后（红色元素） ，剩下的n-1个元素堆的性质被破坏 ，需要重新做一次heapify使前n-1个元素满足堆的性质 ，从而循环（4）这个过程实现堆排序
首先根据该数组元素构建一个完全二叉树 ，具体过程如下(从左到右 ，从上到下按顺序一步一步的详细过程)：
2.最大堆插入节点
最大堆的插入节点的思想就是先在堆的最后添加一个节点 ，然后沿着堆树上升 。跟最大堆的初始化过程大致相同 。
3.最大堆堆顶节点删除
最大堆堆顶节点删除思想如下：将堆树的最后的节点提到根结点 ，然后删除最大值 ，然后再把新的根节点放到合适的位置 。
最小堆
整体操作和最大堆类似 ，这里不做赘述 。
应用场景：
海量数据中找出前k大数（topk问题）
先拿10000个数建堆 ，然后依次添加剩余元素 ，如果大于堆顶的数（10000中最小的） ，将这个数替换堆顶 ，并调整结构使之仍然是一个最小堆 ，这样 ，遍历完后 ，堆中的10000个数就是所需的最大的10000个 。建堆时间复杂度是O（mlogm） ，算法的时间复杂度为O（nmlogm）（n为10亿 ，m为10000） 。
优化的方法：可以把所有10亿个数据分组存放 ，比如分别放在1000个文件中 。这样处理就可以分别在每个文件的10^6个数据中找出最大的10000个数 ，合并到一起在再找出最终的结果 。
下面整理一下这方面的问题：
top K问题
在大规模数据处理中 ，经常会遇到的一类问题：在海量数据中找出出现频率最好的前k个数 ，或者从海量数据中找出最大的前k个数 ，这类问题通常被称为top K问题 。例如 ，在搜索引擎中 ，统计搜索最热门的10个查询词；在歌曲库中统计下载最高的前10首歌等 。
针对top K类问题 ，通常比较好的方案是分治+Trie树/hash+小顶堆（就是上面提到的最小堆） ，即先将数据集按照Hash方法分解成多个小数据集 ，然后使用Trie树活着Hash统计每个小数据集中的query词频 ，之后用小顶堆求出每个数据集中出现频率最高的前K个数 ，最后在所有top K中求出最终的top K 。例如：有1亿个浮点数 ，如果找出其中最大的10000个？
最容易想到的方法是将数据全部排序 ，然后在排序后的集合中进行查找 ，最快的排序算法的时间复杂度一般为O（nlogn） ，如快速排序 。但是在32位的机器上 ，每个float类型占4个字节 ，1亿个浮点数就要占用400MB的存储空间 ，对于一些可用内存小于400M的计算机而言 ，很显然是不能一次将全部数据读入内存进行排序的 。其实即使内存能够满足要求（我机器内存都是8GB） ，该方法也并不高效 ，因为题目的目的是寻找出最大的10000个数即可 ，而排序却是将所有的元素都排序了 ，做了很多的无用功 。第二种方法为局部淘汰法 ，该方法与排序方法类似 ，用一个容器保存前10000个数 ，然后将剩余的所有数字——与容器内的最小数字相比 ，如果所有后续的元素都比容器内的10000个数还小 ，那么容器内这个10000个数就是最大10000个数 。如果某一后续元素比容器内最小数字大 ，则删掉容器内最小元素 ，并将该元素插入容器 ，最后遍历完这1亿个数 ，得到的结果容器中保存的数即为最终结果了 。此时的时间复杂度为O（n+m^2） ，其中m为容器的大小 ，即10000 。
第三种方法是分治法 ，将1亿个数据分成100份 ，每份100万个数据 ，找到每份数据中最大的10000个 ，最后在剩下的100*10000个数据里面找出最大的10000个 。如果100万数据选择足够理想 ，那么可以过滤掉1亿数据里面99%的数据 。100万个数据里面查找最大的10000个数据的方法如下：用快速排序的方法 ，将数据分为2堆 ，如果大的那堆个数N大于10000个 ，继续对大堆快速排序一次分成2堆 ，如果大的那堆个数N大于10000个 ，继续对大堆快速排序一次分成2堆 ，如果大堆个数N小于10000个 ，就在小的那堆里面快速排序一次 ，找第10000-n大的数字；递归以上过程 ，就可以找到第1w大的数 。参考上面的找出第1w大数字 ，就可以类似的方法找到前10000大数字了 。此种方法需要每次的内存空间为10^6*4=4MB ，一共需要101次这样的比较 。
第四种方法是Hash法 。如果这1亿个书里面有很多重复的数 ，先通过Hash法 ，把这1亿个数字去重复 ，这样如果重复率很高的话 ，会减少很大的内存用量 ，从而缩小运算空间 ，然后通过分治法或最小堆法查找最大的10000个数 。
第五种方法采用最小堆 。首先读入前10000个数来创建大小为10000的最小堆 ，建堆的时间复杂度为O（mlogm）（m为数组的大小即为10000） ，然后遍历后续的数字 ，并于堆顶（最小）数字进行比较 。如果比最小的数小 ，则继续读取后续数字；如果比堆顶数字大 ，则替换堆顶元素并重新调整堆为最小堆 。整个过程直至1亿个数全部遍历完为止 。然后按照中序遍历的方式输出当前堆中的所有10000个数字 。该算法的时间复杂度为O（nmlogm） ，空间复杂度是10000（常数） 。
实际运行：
实际上 ，最优的解决方案应该是最符合实际设计需求的方案 ，在时间应用中 ，可能有足够大的内存 ，那么直接将数据扔到内存中一次性处理即可 ，也可能机器有多个核 ，这样可以采用多线程处理整个数据集 。 下面针对不容的应用场景 ，分析了适合相应应用场景的解决方案 。（1）单机+单核+足够大内存
如果需要查找10亿个查询次（每个占8B）中出现频率最高的10个 ，考虑到每个查询词占8B ，则10亿个查询次所需的内存大约是10^9 * 8B=8GB内存 。如果有这么大内存 ，直接在内存中对查询次进行排序 ，顺序遍历找出10个出现频率最大的即可 。这种方法简单快速 ，使用 。然后 ，也可以先用HashMap求出每个词出现的频率 ，然后求出频率最大的10个词 。（2）单机+多核+足够大内存
这时可以直接在内存总使用Hash方法将数据划分成n个partition ，每个partition交给一个线程处理 ，线程的处理逻辑同（1）类似 ，最后一个线程将结果归并 。 该方法存在一个瓶颈会明显影响效率 ，即数据倾斜 。每个线程的处理速度可能不同 ，快的线程需要等待慢的线程 ，最终的处理速度取决于慢的线程 。而针对此问题 ，解决的方法是 ，将数据划分成c×n个partition（c>1） ，每个线程处理完当前partition后主动取下一个partition继续处理 ，知道所有数据处理完毕 ，最后由一个线程进行归并 。（3）单机+单核+受限内存
这种情况下 ，需要将原数据文件切割成一个一个小文件 ，如次啊用hash(x)%M ，将原文件中的数据切割成M小文件 ，如果小文件仍大于内存大小 ，继续采用Hash的方法对数据文件进行分割 ，知道每个小文件小于内存大小 ，这样每个文件可放到内存中处理 。采用（1）的方法依次处理每个小文件 。（4）多机+受限内存
这种情况 ，为了合理利用多台机器的资源 ，可将数据分发到多台机器上 ，每台机器采用（3）中的策略解决本地的数据 。可采用hash+socket方法进行数据分发 。从实际应用的角度考虑 ，（1）（2）（3）（4）方案并不可行 ，因为在大规模数据处理环境下 ，作业效率并不是首要考虑的问题 ，算法的扩展性和容错性才是首要考虑的 。算法应该具有良好的扩展性 ，以便数据量进一步加大（随着业务的发展 ，数据量加大是必然的）时 ，在不修改算法框架的前提下 ，可达到近似的线性比；算法应该具有容错性 ，即当前某个文件处理失败后 ，能自动将其交给另外一个线程继续处理 ，而不是从头开始处理 。
top K问题很适合采用MapReduce框架解决 ，用户只需编写一个Map函数和两个Reduce 函数 ，然后提交到Hadoop（采用Mapchain和Reducechain）上即可解决该问题 。具体而言 ，就是首先根据数据值或者把数据hash(MD5)后的值按照范围划分到不同的机器上 ，最好可以让数据划分后一次读入内存 ，这样不同的机器负责处理不同的数值范围 ，实际上就是Map 。得到结果后 ，各个机器只需拿出各自出现次数最多的前N个数据 ，然后汇总 ，选出所有的数据中出现次数最多的前N个数据 ，这实际上就是Reduce过程 。对于Map函数 ，采用Hash算法 ，将Hash值相同的数据交给同一个Reduce task；对于第一个Reduce函数 ，采用HashMap统计出每个词出现的频率 ，对于第二个Reduce 函数 ，统计所有Reduce task ，输出数据中的top K即可 。
直接将数据均分到不同的机器上进行处理是无法得到正确的结果的 。因为一个数据可能被均分到不同的机器上 ，而另一个则可能完全聚集到一个机器上 ，同时还可能存在具有相同数目的数据 。
以下是一些经常被提及的该类问题 。
（1）有10000000个记录 ，这些查询串的重复度比较高 ，如果除去重复后 ，不超过3000000个 。一个查询串的重复度越高 ，说明查询它的用户越多 ，也就是越热门 。请统计最热门的10个查询串 ，要求使用的内存不能超过1GB 。
（2）有10个文件 ，每个文件1GB ，每个文件的每一行存放的都是用户的query ，每个文件的query都可能重复 。按照query的频度排序 。
（3）有一个1GB大小的文件 ，里面的每一行是一个词 ，词的大小不超过16个字节 ，内存限制大小是1MB 。返回频数最高的100个词 。
（4）提取某日访问网站次数最多的那个IP 。
（5）10亿个整数找出重复次数最多的100个整数 。
（6）搜索的输入信息是一个字符串 ，统计300万条输入信息中最热门的前10条 ，每次输入的一个字符串为不超过255B ，内存使用只有1GB 。
（7）有1000万个身份证号以及他们对应的数据 ，身份证号可能重复 ，找出出现次数最多的身份证号 。
重复问题
在海量数据中查找出重复出现的元素或者去除重复出现的元素也是常考的问题 。针对此类问题 ，一般可以通过位图法实现 。例如 ，已知某个文件内包含一些电话号码 ，每个号码为8位数字 ，统计不同号码的个数 。本题最好的解决方法是通过使用位图法来实现 。8位整数可以表示的最大十进制数值为99999999 。如果每个数字对应于位图中一个bit位 ，那么存储8位整数大约需要99MB 。因为1B=8bit ，所以99Mbit折合成内存为99/8=12.375MB的内存 ，即可以只用12.375MB的内存表示所有的8位数电话号码的内容 。
递归序：
value ==null ; return
node.left
node.right
1,2,4,4(left==null),4(right ==null),2,5,5(left==null),5(right ==null),2,1,3,6,6,6,3,7,7,7,3,1
先序（头 、左 、右）第一次出现：1 ，2 ， 4 ，5 ，3 ，6 ，7
中序（左 、头 、右）第二次出现：4 ，2 ，5 ，1 ，6 ，3 ，7
后序 （左 、右 、头）第三次出现：4 ，5 ，2 ，6 ，7 ，3 ，1
任何递归函数都可以改为非递归函数 。
先序遍历：
先把头节点放到栈里面 ，
1.每次在栈中弹出一个节点current
2.打印current
3.先压右 再压左 ，如果有的话 。没有什么都不做 。
4.重复上面操作 。
1节点 弹出 ，打印1 ，先压3 再压2 ，弹出2 ，打印2 ，先压5 ，再压4 ，弹出4 ，打印4 ，没有什么都不做 。弹出5.
后序遍历：
1.当前节点current 弹出
2.把当前节点放到收集栈
3.先压左 ，再压右 ，没有左右直接走
4.周而复始
5.收集完之后 ，单独打印收集栈里面的 。
中序遍历：
先左 ，再头 ，再右
每棵子树 ，整棵树左边界进栈 ，依次弹出的过程中 ，打印 ，对弹出节点的右树重复 。
4 ，2 ，5 ，1 ，6 ，3 ，7
1 ，2 ，4 进栈 ，每一次弹一个节点 ，4弹出 ，打印4 ，4 没有右树 ，弹出2 ，打印 ，2有右树5 ，5 进栈 ，5 弹出 ，打印5 ，5没有右树 ，弹出1 ，打印1 ，1有右树3 ，3 ，6 进栈 。
弹出6 ，打印6 ，6没有右树 ，弹出3 ，打印3 ，3有右树7 ，弹出7 打印7 ， 7无右树 ，整个栈弹空 。
二叉树的先序遍历 ，就是深度遍历 。
宽度遍历用队列 ，先进先出 。
先左 后右 ，
求一棵二叉树的最大宽度：
创心域SEO版权声明：以上内容作者已申请原创保护，未经允许不得转载，侵权必究！授权事宜、对本内容有异议或投诉，敬请联系网站管理员，我们将尽快回复您，谢谢合作！