// // // // // // // // //
///2013.5.13
// // // // // // // // //
想了很久，
虽然之前在[C++1000个问答]中也讲了很多数据结构，
但总是想到哪里写到哪里，
有时跟数据结构一点边都不沾。
况且能给同学们写博客教程的时间不多了，
实习之后就不大可能再写这些基础教程。
趁着最后一点时间，
帮大家把数据结构系统讲一下，
能让大家到达不至于对其陌生的程度，
我就很欣慰了。
さぁ、いこう。
【衡量一个算法的优劣】
通常来说，
使用O(Big-O)来衡量一个算法的复杂程度。
没有特指的情况下，
O(函数)指代在不同数据量的情况下算法最慢的运行时间的变化(Scale)。
一般有两种通用字母来表示：n与c。
n代表数据元素的数量，
c代表一个常数。
常用的有以下几种(从快到慢)：
O(c),
O(log2n),
O(n),
O(nlog2n),
O(n*n),
O(n*n*n),
O(2的n次方)。
【Big-O图示】
【Big-O理解误区】
关于Big-O的有两个常见的理解误区：
1.假设有一个O(n2)的算法，
循环n次之后，
它的复杂程度变为O(n2 + n)。
错，应为O(n2)。
2.假设有一个O(n)算法,
其内部由一个n次迭代组成，
那将它的这n次迭代减少为n/2次，
那它的复杂程度变为O(n/2)。
错，因为O(n)。
大家一定要谨记算法的复杂程度只是根据"数据增加时算法的时间增量"而决定的。
因此增加数据或是乘上某个常数都不会改变算法的Big-O。
【什么是Bit Vector】
Bit Vector就是传说中的位向量了。
其存储的内容只有两种数：0和1
如下所示：
0100010001100010
有人会问，
为啥不用bool数组呢？
其实这是因为计算机内部架构的问题，
即使bool数组也只能存放0和1，
但是其大小却依然是与int数组相同(8或16或32或64位字节)。
正因如此，
我们才引入了位向量这一概念。
【数组与单链表与双链表的各种操作复杂程度】
如图：
【什么是数组的快删】
这个是比较有技巧的一种方法，
正如上图所示，
其运行效率为最快的O(c),
但这种操作有很高的限制：数组元素不能有排序。
假设有一个长度为7的数组a,
我们想删除第五个元素a[4],
那么我们就将最后一个元素a[6]覆盖到a[4]上，
然后将数组总数减一即可。(数组总数需要我们手动记录)
代码如下：
count--;
a[4] = a[count];
尽管限制很高，
但是正因这种技巧有很高的运行效率，
所以也是蛮有用的。
【数组与链表与双向链表的占用空间比较】
你可能会认为如果拥有同等数据量，
这三种容器的内存占据大小是相同的，
但实际上却并非如此。
假设有一个容纳1000个单位的int集合。
以数组，链表，双向链表的形式将分别占用：
4000，8000，12000个字节。
为什么？
因为链表中每一个单位除了拥有数据之外还有一个指针(在32位中占据4字节)
所以它的实际空间占用大小为：1000*4 + 1000*4 = 8000
而双向链表则是有两个指针，
自然又扩大了4000字节，所以占据了12000个字节。
【获取数据的内存访问过程(以数组为例)】
首先我们需要知道计算机中的内存层，如下所示：
一般在内存中，
计算机会从寄存器中获取数据，
但是寄存器本身容量是很小的，
就如上图所示，
也就那么几百个字节(或者稍大)。
怎么办呢？
于是就出现了L(n)级缓存。
内存大小随着n递增的同时，
访问速度也渐渐变慢。
假设我们要获取一个数组的第1200位元素，
那计算机会现在寄存器中查找，
木有的话再在L1缓存中查找，
木有的话再在L2缓存中查找…以此类推。
然后在某一级中找到了这个元素，
那么就在上一级开辟出相应的空间，
再一级一级进行数据移动，
直到将所需数据移至寄存器中。
至于为什么需要讲这种事情，
这是因为，
在极其注重速度与效率的数绝结构中，
是否能正确并有效的访问内存，
决定了你是否能将数据结构运用地淋漓尽致。
【阐释理解内存处理的真实意义】
假设我们有一个简单系统，
它的L1缓存能够存放8个单位数据，
而我们又有一个16个单位的数组。
假设你想访问这个数组的第一个元素，
那么处理器会加载这个数组的前八位到L1缓存中，
在这个时候，
如果你想访问第二~第八个元素，
速度与第一个是一样快的(因为都加载完毕)。
但如果你想访问这个数组的最后一个元素(第十六个元素)，
并且你对之前的数据进行了修改，
那么，
处理器就需要先将L1缓存中的8个数据放回到内存中，
然后再加载这个数组的后半段数据到L1缓存。
实际上，
真正的访问数组的过程就是这样。
而并非，
是理论中的能使用"恒等速度"来访问数组任意元素。
与此同时，
我们更要注意这个弊端的最大化缺陷：
当我们使用随机算法访问大型数组时，
整个过程的访问时间被延长数倍。
因此，
你应当记住的是，
争取尽可能的按照顺序来访问数组，
不然，
尽管处理器移动内存的时间虽然不长，
但数亿次(或更多)次移动内存的开销将会令运行效率下降数倍。
【未指定长度的多维数组的声明】
众所周知，
在使用二维数组的时候可以不用声明第一个维度，就像这样：
int a[][10];
那么，
大家有没有想过三维的数组是否也可以省略维数呢？
如果可以，
是a[][][10]还是a[][10][10]呢？
答案是后者。
a[][][10]的做法是不可以的。
也就是说，
N维数组必须指定N-1个(后)维度。
这是因为，
其实数组在内存中只是一堆连在一起的内存，
不管再长的数组本质上都是一维数组，
指定维度只是告诉编译器这个一维数组
要从哪里被切割，以及被切割成几段。
其实省略维数在声明一个数组时意义并不大，
相比之下，
能使这一点更为有用的地方是在函数参数中使用数组。
例如:
int someFunc(int array[][10])
这样子，
我们既可以传进a[3][10]，
也可以传进b[10][10]作为实参。
另外说一个小偏方：
不知道大家是否还记得，
在C中，
a[2]还有个写法是*(a + 2);
∵由加法结合律可得，
∴*(a + 2) == *(2 + a)，
∴可得a[2] == 2[a]。
不过不推荐大家这么写，
原因有两点：
1.理解性不强，实用价值低。
2.团队合作中，容易让合作者杀人。
【数组与树的意义】
正好提到数组这一节，
顺便把之前对数组的理解与大家分享一下。
假如说我们想要创建一个8行7列的动态二维数组，
我们可以这样做：
char** a = new char*[8];
for(int i = 0;i <= 8;i++)
a[i] = new char[7];
那么，
跟昨天问题一样，
如果我们想要创建动态N维数组怎么办呢？
答案很简单，
模仿上例再一层一层迭代就OK。
但在这里，
我想说的是树的思想在数组中的体现。
假设有这样一个数组——
int a[2][3][4][5][6];
我们创建的顺序是从左到右来创建，
与此类似地，
树的创建不也是从上到下么？
数组a有2个父节点，
每个父节点下有3个子节点，
这3个子节点下又分别有4个子节点，
……以此类推。
像这样，
我们就可以将一个多维数组慢慢地拆解为一个树。
昨天笔者说多维数组本质就是一个长序列，
而但将这个序列竖起来看(意义上)，
多维数组又像是一棵树。
如果能够像这样，
在内存层次，
与理解层次，
都对数组发展成较为全面的认识，
那么相信大家对数组运用能力会更上一层。
【阐述内存意义之链表】
在上上次的内容中提到关于数组的内存理解意义。
各位可以看这里回顾一下：http://blog.csdn.net/elezeor/article/details/8922372#t8
那我们这次再简要阐述一下链表的内存意义，
链表在内存中的分布如下图所示：
图中的阴影部分都是非链表内存(有可能是垃圾内存)。
恩…诸位还记得上次在数组时说过的寄存器加载内存的问题么？
简而言之就是调用内存中相距较远的两个元素需要重新加载内存块。
从这幅图来看，
动态链表的情况就是数组最糟糕的情况时的1000倍糟糕程度。
除此之外，还不要忘记链表的创建与删除开销是要大于数组的，
因为多了指针之类的东西。( http://blog.csdn.net/elezeor/article/details/8922372#t6 )
当然，
如果每个元素需要进行大量的操作从而可以忽略移动内存的消耗的话，
那倒没有太大问题。
但如果对元素的操作较少，数量又比较多的话，
动态链表的表现就要比数组糟糕很多。
最简单的一个例子，
比如说游戏中常见的粒子效果，
在制作过程中一般都要指定一个粒子最大数目用来创建数组，
——而不是创建链表。
但链表的随机内存也不是没有好处：
这样遍历节点与随机获取节点的速度是相同的，
这让链表在发展不均衡的数组面前倍儿有面子。
【补充：遍历节点与随机获取节点解释】
我在这里只是讨论寄存器加载数组，与加载链表的区别。
假设：有一个500单位大小的寄存器(也许没这么大的，但我们假设)、
我们要第一次加载第1个元素，第二次加载第2个元素。第三次加载第999个元素。
第一次到第二次视为遍历。
第二次到第三次视为随机。
如果使用数组，
那么第二次到第三次肯定会比第一次慢，
因为寄存器要先释放前五百个元素，
再加载后面的五百个元素。
这时寄存器中才有第999个元素。
如果使用链表，
第二次到第三次不一定比第一次慢，
因为链表内存不连贯，
也许第2个元素在第999号单位的地址上。
第一次到第二次也同理。
因此，
在此前提下，
链表遍历获取元素(从第1个到第2个)与随机获取元素(第2个到第999个)的时间是有机会相等的。
但这在数组中是不可能相等的。
【高效的Queue : 环形队列】
想象有这样一个问题：
我们想要使用数组来实现一个队列，
在使用前我们先指定数组大小，
然后对其进行各种操作。
我们期望各项操作的速度是相同的，都是O(c)，
但是使用数组也就意味着其包含数组的弊端：
Pop时的速度，并非O(c),而是O(n)。
为什么呢？
别忘了，
我们队列的实现是要Pop第一个元素，
因此无论何时这个数组的首元素都不能为空，
——即使是将首元素删除时。
因此我们需要进行移位，
在每一次Pop之后将后面全部元素都向前移动一位，
这样就能保证首元素不会为空。
因此如果删除后数组长度为n，
就要移动n个元素，
由此Pop操作的时间复杂程度为O(n)。
于是，
为了弥补这一问题，
环形队列登场了。
相比普通队列，
环形队列只是增添了一个变量——首元素序号。
没错，
到这里你肯定就明白了：
每次Pop时，
我们不再进行元素移位，
而是将这个首元素序号+1即可，
这样就可以弥补队列数组的缺陷了。
但是，
环形数组存在两个比较重要的问题，
它们是什么呢？
请见下次分解。
【环形队列的两个重要问题】
问题1：尾部续接。
如下图所示，
假设我们的这个环形队列具有七个单位长度，
其中第一个已经Pop了，因此首索引指向第二个元素。
那如果此时我们再在后面添加四个元素会怎样？
因为结尾部分只剩三个空位，多出来的那个元素放在哪里呢？
没错，
正如你所想的那样，
这就像一个环，
最后那个元素会被插入到第一个空位中。
因此这样导致的直接后果就是我们在Enqueue元素时，
需要使用一点小技巧，
——使用"模"来确定位置。
代码如下所示：
typedef int Datatype;
bool Enqueue(Datatype data)
{
if(size != count)
{
array[(count + front)%size] = data;
count ++;
return true;
}
return false;
}
其中第七行的：(count + front)%size 就是解决这个问题的关键步骤了。
问题2：扩容。
正如大家所看到的那样，
这是一个圆环，
圆环的固有属性之一就是圆满。
因此环形数组队列同样具有这个属性：几乎没有办法原地扩容。
总而言之，
最简单的扩容方法就是创建一个新队列，
然后从首元素一个挨着一个地拷贝过去。
【稀松数据(Sparse Data)】
计划接下来要讲哈希表(Hash Table)。
但是在讲解之前需要先证明一下使用哈希表的必要性：
假设我们具有一个类叫做Human，
获取这个类的实例需要使用一个专属的身份证号，
而这个身份证号是在构造时随机生成的范围从0~1,000,000的一个数字。
我们此刻拥有以下三个实例(及其身份证号)：
Human_1: 945,253
Human_2: 433,455
Human_3: 36,549
它们彼此相隔甚远，分布疏松。
那我们该用什么数据结构来存储这三个实例呢？
使用数组吗？
那就会成为下图这样：
明明只有三个数据，
却占据了1,000,000个单位的空间。
很浪费吧？
那使用链表呢？
不错，不用担心空间问题了。
但是如果有100,000个实例，
我们想调用其中的第59,915个怎么办？
一个一个迭代么？
也不行。
看来之前介绍过的数据结构都不合适。
于是，
为存储及处理稀疏数据，
哈希表就应运而生了。
【基础的哈希表】
首先需要记住的，
是哈希表具有两大特点：
1.在一个合理的内存空间内快速地存储基于Key值的稀疏数据。
2.快速地判断某一个Key是否在此表内。
哈希表的存值过程如下：
1.设置哈希表的大小N。
2.将Key值通过某种算法处理后放入表中某个位置。
这个某种算法是什么呢？
一般来说最常用的是"取模"。
以上一个示例为例：
Human_1: 945,253
Human_2: 433,455
Human_3: 36,549
假设我们开辟的哈希表T大小为10，
Human_1的存储位置就是945,256 % 10 = 6。
那Human_1就存放在T[6]中。
同理，
433,455 % 10 = 5，
36,549 % 10 = 9,
那么Human_2与Human_3分别被存放在T[5]以及T[9]中。
上述的这个哈希表非常简单，
相信大家都能够理解。
同时请大家记住：
一个理想的哈希表查找元素的时间为O(c)，
这是非常难得的。
但实际上这个示例存在某种缺陷，
是什么呢？
请见后文。
【哈希表的冲突】
假设我们想将104和25,344放到这个哈希表中会怎样呢？
因为104 % 10 = 4，25,344 % 10 = 4，
所以这两个数字的存储位置将会发生冲突。
实际上，
尽管作为一个简单的例子，
但仅仅取模处理之后再存入哈希表也是非常危险的。
于是我们需要进一步处理，
而这次处理需要委托为一些函数——哈希函数(Hashing functions)。
其实很多人不理解哈希是什么意思，
一个人的名字吗？
并非如此。
"哈希"一词用在料理上就是指混杂各种食材，
而用在计算机上也很相似：
将各种数据通过某种方法进行"搅拌".
最简单的一种哈希函数叫做“数位相加”，
顾名思义，
将一个数字从个位加到最高位得到存储位置：
1 + 0 + 4 = 5,
2 + 5 +3 +4 +4 = 18。
第一个没有问题，
但第二个已经越界了(容量为10)。
为了应对到这种情况，
有两种办法：
1.扩容。
假设我们的Key区间为1~100,000，
那我们需要一个容量为45的哈希表，
为什么呢?
∵ 9 + 9 + 9 + 9 + 9 = 45。
2.详见下文。
【数位相加Bug的第二种解决方案】
上次提到为解决哈希冲突问题，
我们采用的一种方法是数位相加。
但是这种方法会出现越界Bug，
于是，
我们尝试扩容来解决这个问题。
除此之外，
还有另一种解决办法——双哈希。
顾名思义，
就是对第一次哈希的结果再进行一次哈希运算。
还是以上述两个数字为例：
104与25,344数位相加的结果分别为5与18,
对5与18再此数位相加得到的结果为5与9，
这样两个数字就都小于最大容量了。
当然，
双哈希不一定两次都要使用同一种算法，
比如说，
第一次使用数位相加，
第二次使用取模运算也是可以的。
【字符串的哈希函数】
上面提及了如何对int类型的Key值进行哈希处理。
那么其他类型的Key值怎么办呢？
比如说，
同样也很常见的String类型？
处理String类型的哈希函数一般是这样做的：
给字符串中每个位置的字符乘上一个常数，
然后将所得结果相加。
示例代码如下：
unsigned long int stringHash(const char* s)
{
int length = strlen(s);
unsigned long int hash = 0;
for(int i = 0;i < length;++i)
{
hash += (i + 1)*s[i];
}
return hash;
}
可以看到，
与int类型的哈希函数相比，
这个又增加了一个乘以常数的操作。
在这个示例中，
对每个位置的字符所乘的常数为所在位数+1，
其实这个并没有什么限定，
只要不产生容易相同的哈希数即可。
比如说"Elezor"这个词，
这样的运算结果为
(69*1) + (108*2) + (101*3) + (122*4) + (111*5) + (114*6) = 2315
除此之外，
因为增加一步乘上常数操作，
因此即使顺序颠倒，
例如rozelE或是Eezorl神马的，
也不会发生位置冲突。
【哈希碰撞的错误方案】
写这个内容前我思考过，
与大家分享虎毒之帖，
这样做是否会适得其反？
但因担心国内书籍的鱼龙混杂，
教与大家如何甄别错误的方案也不失为一种正确的做法。
(1)线性溢值法(Linear Overflow)
它解决哈希值冲突的思想非常明确：
如果出现冲突，
则将当前索引向后移一位，
直到找到可以插入的位置。
写成代码就是如下所述：
while(a[hashIndex] != NULL)
{
hashIndex++;
}
a[hashIndex] = hashValue;
这种做法就是拉低了整条街(哈希)的智商。
大家可以想象一下：
假如想要获取一个值，
那应该去这个值(本该存在)的索引查找，
结果木有，
那就看看它的后一位呗，
还是木有，
那再看看它的后一位吧，
……
直到地狱尽头。
之前提到过，
哈希表的速度是O(c)，
但是这样做，
无疑又回到了O(n)，
毫无意义。
(2)平方和溢值法。
它的思想跟上面那个相似，
不过它的后续索引并非增加1，
而是依次增加从1到n的平方和的长度！
例如说有一个值想要放到位置5去，
但发生了冲突，
于是使用平方和溢值法插入：
第一步：5 + 1*1 = 6,
第二步：6 + 2*2 = 10,
第三步：10 + 3*3 = 19,
第四步：19 + 4*4 = 35,
……
怎么样？
这种方法将已被线性溢值法拉低智商的哈希表再拉低一条街。
因为除了速度之外还有一个更重要的问题：
即使你遍历完一遍却依然不知道表中是否存在这个Key！
【链表溢值法】
即使忽略速度，
上述两种做法也有硬伤：
占用了属于其他元素的位置。
这就相当于用一个Bug方案去解决另一个Bug，
——只是将Bug的发生顺序稍稍偏移了一下而已，
并没有真正意义上的解决问题。
而有一种方案能够更为合适地解决哈希碰撞问题：
链表溢值法(Linked Overflow)。
它是这样做的：
为每个哈希表中的元素创建一个链表，
当发生碰撞时就依次存至链表下一位(而当前哈希表中索引不变)。
——也就是说，
在这种方案中，
每个元素位并非存储一个值，
而是存储一个链表(的头指针)。
就像下图这样：
也许有人会问：
这样做不是间接扩容了么？
并非如此，
——链表的内存是不连续的。
如果你对此抱有疑问，
但使用链表也有一点弊端：
——搜索元素仍然需要遍历。
从某种意义上讲，
这种方案的检索时间为O(n)，而不是O(c)。
但是实际上使用的时候，
遍历链表所耗费的时间几乎可以忽略不算：
如果一个索引位置拥有数百个元素，
那我想或许你该考虑换的是哈希函数(例如从"取模"换至"数位相加")，
而不是它。
因此使用链表溢值法的最佳条件是拥有一个合适的哈希函数，
来防止哈希表位置存储元素数目产生不对称(例如1位置有0个值，而2位置有10,000个)。
在这种条件下，
每个链表所具有的元素也是相对均衡的。
因此遍历所耗费的时间几乎可以忽略不计。
更何况，
它还拥有一个另一个优势：
当前元素并不不会占用其他元素的存储位置。
既然提到到这里了，
就小小地说一句：其实众所周知的桶，
概念就是它。
【RTTI之dynamic_cast】
RTTI的全称为RunTimeTypeInformation，
简而言之，
是让编译器在运行时进行类型转换的。
提到RTTI不得不说的就是dynamic_cast关键字。
比如说:
BaseClass *base;
base = new ChildClass();
我们想要基类指针base调用子类特有的方法，
base -> doChildMethod();
如果不加任何关键词进行修饰的话，
编译器一般会报错。
于是我们可以使用dynamic_cast来对父类指针进行"转换":
ChildClass* p = 0;
p = dynamic_cast<ChildClass*>(base);
p -> doChildMethod();
这种转换被称为"向下转换"。
在Java中我们听到过这个词汇，
但那时我们是使用括号来进行转换的：
(ChildClass*)base -> doChildMethod();
其实在C++中也有相同的做法，
并且确实也被广泛使用，
那二者的区别是什么呢？
我们又该如何选择呢？
且听下回分解。
最终决定用这个标题。
因为不管是在C还是C++中，
如果需要向下转型，
人们使用这种方法更为普遍：
(ChildClass*)base -> doChildMethod();
与上述的dynamic_cast相比，
它具有双刃性：
正面：
这种方法更快。
两点原因：
1.它不需要检索RTTI table。
2.它不需要为错误的转型提供异常解决方案。
反面：
这种方法超级危险。
注意，不是一般危险，
是超级危险！！！
本质上来讲，
这种转型方式是继承自C语言的，
它的意思就是——强制将当前类型进行转化，而不管是否正确。
还记得指针指向未知地址可能产生的严重Bug吗？
内存溢出还好，更有甚者会误修改其他数据！
因此在任何情况下都不推荐大家在C++中使用这种转型方式。
之前在StackOverFlow上看到一个朋友的疑惑，
他很奇怪很多人说dynamic_cast的表现不好，
但是他自己尝试却没有发现性能差太多。
这是因为，
测试数据还不够。
假如说尝试1,000,000次dynamic_cast与强制转换,
就会明显看到二者差别。
处于效率考虑，
在很多正式的大型项目中都争取不使用dynamic_cast。
那或许会有人问，
dynamic_cast慢，强制转换不安全，
那向下转型该用什么？
答案是，
不到万不得已，
最好不要向下转型。
尤其是当需要大量使用向下转型的时候，
或许你该考虑重写架构了。
【RTTI之typeid】
RTTI中能够在运行时获取对象信息的运算符为typeid。
其用法如下：
#include <typeinfo>
typeid(object);
首先最需要强调的一点是：
这是一个运算符，
而不是函数。
因为它的参数同样可以是某一类型，
而不只是对象。
其返回的是一个std::type_info的引用。
因此我们可以这样写：
const std:type_info& info = typeid(std::type_info);
其实对于一般的数据我们并不需要获取其类型，
但是对于像是多态的指针之类的东西，
这个玩意就稍微有一点作用了，
例如输出某个指针指向对象的名字：
std::cout << typeid(*ptr).name() << std::endl;
尽管在《Thinking in C++》中它的使用比较广泛，
但严格来说，
我们对其的使用也只能是尽其所能，
——千万不要使用某些自创的“小技巧”。
能够在运行时获取对象的名字，
尽管这是一件听起来就很有趣的事情，
但是需要提醒大家的是，
typeid属于RTTI，
对于那些在运行时已经编译好全部的内容，
它是鞭长莫及的。
【RTTI的限制】
在准备使用RTTI之前，
有以下几点需要注意：
1.RTTI仅适用于多态类型。
在C++中，
多态的意义为：
有父类或包含至少一个虚函数。
2.typeid不能应用于引用。
即使是指针的引用也不可以。
3.鉴于RTTI一点额外的消耗，
并非全部编译器都默认开启RTTI。
比如说，
全国大学通配的VC6.0就默认关闭。
最后，
是最重要的一点：
慎重使用RTTI。
要知道，
RTTI的优先级要低于多态与模板，
产生的结果就是——
RTTI从某种意义上来讲，
很像goto(没错，就是那个goto)。
用它的一些特性取巧很容易，
但是非常危险，
所以，
还是那句话：
除非你知道自己在做什么，
否则不要创造RTTI的新用法。
【树的遍历之深度优先遍历】
首先需要知道二叉树具有五种遍历方式：
先序，后序，中序，逆中序，广度优先遍历。
前四种统称为深度优先遍历，
它与最后一种又作为多叉树的遍历方式。
先序遍历：
根->左->右。
后序遍历：
左->右->根。
中序遍历：
左->根->右。
逆中序遍历：
右->根->左。
不同的遍历方式相互组合起来，
称为树的序列化。
这种序列化是具有一般规律的：
用语言描述有歧义，
就给个公式吧——
((先序 || 后序) && 中序)
之所以没有先序与后序组合的方式，
是因为那样的序列化将会产生歧义。
为何会产生歧义呢？
此处先按下不表，
之后再详谈此问题。
【树的深度优先遍历图示】
为方便大家记忆深度遍历，
特意制作了一张图以供大家理解参考。
【各种遍历方式的用途】
先序遍历：
1.它用于复制节点与值，
并且可以完全地拷贝一个二叉树。
2.用于制作前缀表达式，例如+15，
中序遍历:
由于其自身返回值有序的特性，
它可以通过比较的方式来建立一个二叉搜索树。
后序遍历：
1.主要用来删除，并且释放节点，
这一点相信大家从名字就可以推测出来。
2.用于生成一个二叉树的后缀表现形式，
这个是与前缀相对应的，
【深度遍历图示】
今天我们用图来表现一下深度遍历的完整顺序，
方便大家加深记忆：
有树如图(图片来自维基百科)：
先序遍历的顺序为：
F,B,A,D,C,E,G,I,H
中序遍历的顺序为：
A,B,C,D,E,F,G,H,I
后序遍历的顺序为：
A,C,E,D,B,H,I,G,F
1.中序遍历的窍门是尽最大可能避开右。
2.后序遍历的窍门是尽最大可能避开根。
3.即使只有一个子节点，也是一个分支树。
【广度遍历(BFT)简介】
广度遍历很好理解，
就是将某一层别横向遍历完成之后，
再去遍历下一层，
用图像表示就是如下图所示：
坦白来讲，
我并没有使用过广度遍历来遍历一棵树，
因为相比之下，
遍历图使用深度遍历更为人所熟知。
(尽管某些图也算作树……)
著名的BFS尽管使用率没有DFS高，
但是其仍然具有特定的使用价值：
大家试想一下，
假如一棵树非常深(Close to Infinte)，
那么使用深度遍历毫无疑问是并不高效的，
因此在这种情况下使用广度遍历更为合适。
因此一般的文件查找系统使用广度遍历要较为常见。
除此之外，
BFS也适用于寻找无权图的最短路径查找。
当然，这些都是后话了，
毕竟这不是BFS(Breadth-fist Search)，而是BFT(Breadth-first Traversal)。
【二叉树编程思路集锦(1)】
讲了这么多理念，
大部分都只是铺垫，
在计算机语言中，
只有编程才是检验无Bug的唯一标准。
考虑到大部分的代码较为简单，
以及为了摆脱语言所限制，
再此给出二叉树编程问题的一些思路，
期望有助于各位。
Caution：
涉及到数据结构的编程，
一定要有检查其是否为空的觉悟，
诸君切记！！！！！
Hints:
二叉树的编程几乎全部使用递归，
诸君切记！！！！！
1.三种遍历：
只需要将遍历顺序中的根改为"处理节点"，
在这之前千万别忘了检查根是否为空！
然后左右子树改为"递归左右子树"即可。
2.统计节点总数。
先检查是否为空或者只有根结点。
然后递归统计左右子树节点，
再将其相加。
3.查找第k层节点数：
先检查第k层是否存在或是唯一。
然后递归统计第k-1层的全部节点的左右子树数目，
将其相加。
4.查找叶节点总数：
先检查当前节点是否为空(返回0)，
否则如果没有左右子树则返回一。
迭代此过程，相加。
如上所述，
大部分的编程都是先检查再递归最后叠加，
不过不要看整个过程单一，
但是真正使用起来才会发现递归在方便的同时，
自身也存在逻辑眩晕综合症，
不要被它搞混了。
