二叉树的前中后序遍历
这篇主要是放这里提醒自己这些基础算法要能用白纸手写出来。
讲遍历之前我先找找以前有没有画树的图拿来用一下。
太好了，有啊，下面就统一用这张图：
最左下角那个是“H”啊，小了点。
前序遍历
前序遍历主要思想是什么呢？从根节点开始，前序遍历访问左子树，遇到空节点则返回，然后再前序遍历访问右子树，遇到空节点则返回。
说的会比较抽象一点，直接看： 对上图进行前序遍历，结果为： A B D H I E J K C F L G
当然，也可以直接看代码：
虽然是我现场手写，不过我有信心不会错啊
void PreOrderTraverse(Tree T)
{
if(T == NULL)
return;
cout<<T.data; //打印节点信息
PreOrderTraverse(T->leftChild); //这一步会一直走到没有左儿子为止
PreOrderTraverse(T->rightChild); //没有左儿子就去看一眼右儿子，顺便看看有没有左外孙
//如果都没有，那就跳回到他爸，让他爸去找他弟弟
}我已经写的这么通俗易懂了，我日后要是自己看不懂，那我就是二货。
当然，如果学习过进程和线程会比较好想象个中奥妙。
中序遍历
中序遍历主要思想是什么呢？从根节点开始，中序遍历左子树，遇到空节点则返回后访问，然后再中序遍历右子树，遇到空节点则返回后访问。
我也不想绕弯子，省的到时候我自己都看不懂是什么东西了。 前序遍历和中序遍历的差别就在于什么时候访问。后序遍历也是一个德行。
看代码，其实差别也很细微。
void MidOrderTraverse(Tree T)
{
if(T == NULL)
return;
MidOrderTraverse(T->leftChild); //这一步会一直走到没有左儿子为止
cout<<T.data; //打印节点信息 //也就这行换到这里
MidOrderTraverse(T->rightChild); //没有左儿子就去看一眼右儿子，顺便看看有没有左外孙
//如果都没有，那就跳回到他爸，让他爸去找他弟弟
}所以中序遍历的顺序是： H D I B J E K A L F C G
后续遍历
后续遍历更加不废话了，直接上代码好了：
void LastOrderTraverse(Tree T)
{
if(T == NULL)
return;
LastOrderTraverse(T->leftChild); //这一步会一直走到没有左儿子为止
LastOrderTraverse(T->rightChild); //没有左儿子就去看一眼右儿子，顺便看看有没有左外孙
cout<<T.data; //打印节点信息 //也就这行换到这里
}顺序：H I D J K E B L F G C A
注：
如果对于以上顺序有疑义，可以自己一步一步画出来，画完还有疑义，可以在下面评论咱一起讨论讨论。
已知遍历排序求树
数据结构考试就喜欢考这种题目。 首先要明确：那棵树，肯定是二叉树。 然后我们来分析。
前序：A B D H I E J K C F L G 中序：H D I B J E K A L F C G 后序：H I D J K E B L F G C A
一般不会给你三个，也不会只给一个，还没那么小气哈。 不管给哪两个，来分析一下：
首先肯定要把根节点找出来，明眼人一看就知道是A，别问我为什么。
接下来分三种情况来讨论：
- 如果给了前、中序排列
//给了中序那就好办了
//一：看中序排列中的根节点位置在哪里，根节点前面都属于根的左子树及其后代，后面你懂得。
//二：将中序序列分两段：（H、D、I、B、J、E、K）和（L、F、C、G）
//三：明眼人一看就知道根节点左子树的“根节点”是：B
//别问我为啥，问就是看前序序列的第二位
//四：重复二三，直到根节点左子树排出来为止
//五：同上，排出右子树如果觉得看不懂，自己动手试一下。
- 如果给了后、中序排列
//一、二步同上
//其实第三步原理是一样的，不过我们的脑子习惯了从前到后，所以，让我帮你们转个弯。
//像对中序分割一样，将后序序列也分割了。
//从中序排列的分割中我们知道根节点的右子树有哪些成员，所以后序序列这样分：
//（H I D J K E B）（L F G C）
//现在就很明显可以看出根节点左子树的“根节点”是谁了吧
//重复以上步骤还是那句话，要是觉得晕，自己操作一遍。
- 如果给了前后序序列
这个书上说不行，我也曾自己想了个方法来想推翻这个结论，即前序的第n个数不等于后序的倒数第n个数，则前序的那第n个数必定是当前节点的左子节点，然后将序列截开，截开方式和上面一样不多说。 但是后来发现，上面那个结论是没错，但那只是一半，它的令一半没办法，即前序的第n个数等于后序的倒数第n个数，那就麻烦了，因为并不能武断的说当前节点那就没有左子节点，第n个数就是右节点。
通过一个简单的反例便可以推翻： 一颗歪脖子树，有节点 A B C D,一路向左。那么前序遍历就是ABCD，后序遍历就是DCBA，按照我原先的想法，前序的第二个数是B，后序的第二个数也是B，那这时候怎么办，B会是A的右子节点？显然不是。
然后我右深入想了一下，如果A B C D，一路向右，它的前序也是ABCD，它的后序依旧DCBA，和一路向左一样啊！！！
由此得出结论，如果是给了前后序序列，那是真的不行。