【数据结构】- 二叉树国内外概念上的一些分歧
我们要讨论的二叉树类型
Full Binary Tree（满二叉树），最大的分歧就是对满二叉树概念的分歧，在百度百科中对满二叉树定义的引用：Node has exactly zero or tow children.，即节点要么0个度（叶子节点）要么2个度。但仅仅只是满足这一个条件就会造成下面这样的树也是满二叉树。而我们国内对满二叉树的定义则是最后一层非叶子结点的左右子节点都必须是满的，也就是整棵树的节点为(2^h)-1个节点，而每层节点个数的计算是第i层节点个数为2^(i-1)个节点。按照国际上对满二叉树的理解与我们国内对满二叉树的理解其实是有些扭曲的，国际上的满二叉树其实更加符合另外一种树的特性：霍夫曼树（哈夫曼树）。而我们对满二叉树的理解其实符合另外一种树，就是下面会讲到的：Perfect Binary Tree(完美二叉树)。
# 下面这种形式也是满二叉树，是不是和我们的认知不一样呢？
# 1
# / \
# 1 1
# / \
# 1 1
# / \
# 1 1
Complete Binary Tree（完全二叉树），完全二叉树在所有数图形中都是以：一棵完全二叉树的两棵子树，至少有一棵是满二叉树。的形式出现。按照国际理解我们姑且将：一棵完全二叉树的两颗子树都是满二叉树。的这种情况成为该树是一个课满二叉树。这里我参考了一篇知乎文章：完全二叉树的节点数，你真的会算吗？文章里作者写了一个统计树节点的方法，将原来的算法复杂度从O(NlogN)降低到O(logNlogN)，这里有趣的地方就是根据完全二叉树最少有一个满二叉子树（满二叉树节点个数：(2^h)-1）的特性将计算次数降低了一个对数的量级。文章中的Java代码我已经复制到下方，有兴趣的朋友可以查看原文章的讲解过程。
public int countNodes(TreeNode root) {
TreeNode l = root, r = root;
// 记录左、右子树的高度
int hl = 0, hr = 0;
while (l != null) {
l = l.left;
hl++;
}
while (r != null) {
r = r.right;
hr++;
}
// 如果左右子树的高度相同，则是一棵满二叉树
if (hl == hr) {
return (int)Math.pow(2, hl) - 1;
}
// 如果左右高度不同，则按照普通二叉树的逻辑计算
return 1 + countNodes(root.left) + countNodes(root.right);
}
Perfect Binary Tree（完美二叉树），这里完美二叉树就是我们国内所说的满二叉树的形式，但是在国内搜索引擎上很少专门讲解这个类型的二叉树，本质上它是一种特殊的满二叉树。我们通常所谈论到的满二叉树只要知道在国外叫做完美二叉树即可，在使用上遵循二叉树的规则就可以了。毕竟我们在使用原地排序——堆排序的时候，树的结构是随着新增元素的增加而不断改变的，也就是说这棵树在国际概念中它的类型是在完全二叉树和满二叉树之间来回变动的。
但求甚解过程中遇到有趣的事情
基于满二叉树的原地快速排序，这个满二叉树实现的原地快排是在百度百科的介绍中看到的：满二叉树。我找到了这个算法来源的学术论文（基于满二叉树的原地快速排序）有兴趣的可以下载pdf来看一看。这篇论文是2006年重庆邮电大学软件学院副教授写的学术论文，我不知道这篇文章有没有过时，反正在国内搜索引擎能够搜索到的只有这篇论文讲基于二叉树来实现快速排序。如果在外网搜索也搜索不到这个概念，大多数都是：A Connection Between Binary Search Trees and Quicksort、Analogy between Binary Search Tree and Quicksort Algorithm这种讲二叉搜索树与快速排序之间的关联关系，并没有提出基于满二叉树来实现的快速排序。很遗憾我看这个论文并没有看懂，但是我会继续探索这个算法遇到高人再请教。这个算法里面提到了算法的原地性，就是一个排序算法在调整的过程中所使用的额外存储空间并不受问题规模的影响，而是一个保持在一个固定的常量，这个时候就可以说这个算法是原地的，通常我们使用的堆排序就是原地排序，而基于满二叉树实现的快速排序性能要优于堆排序算法。
基于完全三叉树堆排序的波前扩展有限差分地震波走时快速算法，在对满二叉树求解的过程中我还意外看到这篇关于二叉树堆改进为三叉树堆的实际应用案例的论文，论文在线地址：基于完全三叉树堆排序的波前扩展有限差分地震波走时快速算法。在这个案例中计算地震波的时候需要高效的运算获取最小堆中的堆顶值，这里做的数据结构改进其实不是很多，结合案例中取出最小值后立马又需要插入新的值，这里将二叉堆中取出值后将堆底节点临时复制到堆顶的这个操作换成讲计算出的新值插入到堆顶，这样就省去了一次下沉的操作。还有一个操作就是扩展为多叉进行测试，得到的记过是二叉、三叉、四叉中三叉性能表现最好，总体性能上比二叉树堆提高了20%。这个实验对树据结构改进可以很好的套用在其他类似的场景中，对学习树和了解树很有帮助。
