express 阮一峰:如何学好数据结构？

（转）
前面的话：轻舟曾经热衷于把自己复习时候遇到的问题和总结的经验分享给大家，不过
来了交大以后，发现这里卧虎藏龙，自己只不过是溪底小虾一个。于是放弃了以前出数
据结构笔记的打算，不过，最近又有许多同学问起我数据结构的事情，这里就把以前总
结的笔记的前言帖出来，但绝对不会有后续部分，希望大家见谅。

学习数据结构这门课程至少要经历三个过程，方可真正
的掌握这门课程，得到一个满意的成绩。这个过程简单来说就是三个字：活→死→活。
首先，是一个学“活”的过程，就要要求我们对书中的每一个算法，能够在脑海中
建立起相应的模型，而不是死板的算法。比如树的遍历非递归算法，在入栈与出栈的过程
中，我们就要在脑海中形成访问树每个结点的过程，真正掌握住这个算法。这样，全书复
习下来，你的脑海中就有了整个数据结构的模型概念，对任何一个陌生的算法，将不感到
生疏和害怕。
有些同学到了此处就觉得数据结构已经学好，可以万事大吉了，其实这还远远不够
，如果参加考试，往往会拿不到高分，甚至还会纳闷，为何自己数据结构学的这样好，成
绩却不尽如人意，因此产生了批卷老师判错的想法。所以第二个过程，就是一个学“死”
的过程，这个过程要求，要记住书中的算法（功利一点就是要背诵会所报考学校的考试要
求的算法）。有的学校有别的特殊要求，也一并背会。如上海交通大学喜欢考平均复杂度
的分析这样的题目，我们在书上可以找到这样的分析一共十一个，全部背会，就免去了在
考场上分析的麻烦，如果连答案都能记住，那么，也不会因为粗心失分了。这一过程也许
有些枯燥，但却是最重要的过程，比如说背会了树的后序遍历非递归，遇到了像求某个结
点的所有祖先，两个结点的共同祖先这样的题，不用想，直接套用。这样才是考试的高分
的关键：在考场上，遇到考题，不用思考，直接从脑海中找匹配的算法，直接引用。
有了第二个过程的辛苦，我们就可以得到一个比较高的分数了，如果还想提高，就
要进行第三个过程，再学“活”的过程。这一个过程中就要要求我们，在第二步的基础上
，多进行思考，看看有哪些算法有共性，比如说：树的前序非递归遍历算法和图的深度优
先遍历算法是不是类似啊，有些什么不同，有些什么相同，为什么会相同；森林转化为二
叉树和图的生成树的算法也是这样，等等。总结出这种共性，这样就能正确有效的记忆算
法，同时，遇到难题不至于慌乱，能够从容下手解题。
对于总结共性问题上，这里举一小个例子，(呵呵，我当初总结出这个，并且和ka
oyan.com斑竹一具讨论确定后三天，就在2002年交大第一题考出类似东东）比如树的遍
历，不管是递归还是非递归
，也不管是线索树，还是头结点有父母信息的树，它的遍历其实就是一个寻找到遍历的第
一个结点，然后再寻找它的后继结点的过程，我们归纳到此处，就可以试着总结一下三种
遍历的后继结点是哪个，有几种情况：
对于前序遍历，它的后继如下：
（1）若有左孩子，则后继是左孩子；
（2）若无左孩子，有右孩子，则后继是右孩子；
（3）若既无左孩子，又无右孩子，则是一片叶子；再讨论：
（a）若是其父母的左孩子，且父母有右孩子，则后继是父母的右孩子。
（b）若是其父母的左孩子，且父母无右孩子；
（c）若是其父母的右孩子。
b，c都表示这是某个节点的左子树前序遍历的最后一个节点，则需要找第一个有右子
树的“左祖先”（定义“左祖先”，即找第一个使得当前节点在这个祖先的左子树上），
然后后继就是这个祖先的右孩子。
对于中序遍历，它的后继如下：
（1）如有右孩子，后继是右孩子的最左下节点；
（2）若无右孩子，且是父母的左孩子，则后继就是父母；
（3）若无右孩子，且是父母的右孩子，则一直上溯到第一个“左祖先”（定义如前）
则后继就是这个祖先。若无这样的祖先，说明已经遍历完毕。
对于后序遍历，它的后继如下：
（1）若是父母的右孩子，则后继是父母；
（2）若是父母的左孩子，且父母无右子树，则后继是父母；
（3）若是父母的左孩子，父母有右子树，则后继是父母右子树的最先访问到的节点（
指向父母的右子树后，一直往左，若不行的话，往右一步，一直到叶子）
总结完了，想一想，我们还能得到哪些提示？经常有一类型题目，要求求某个结点
的直接前驱。其实求前序遍历的前驱和求后序遍历的后继是一样的，只不过把左换成右而
已，前序遍历的求后继和后序遍历的求前驱、中序遍历的求前驱和中序遍历求后继都有这
样的对称关系。因此，总结出共性的东西，许多题目就可以迎刃而解了。问一问读到这里
的读者，你现在能够自己在脑子里面，非常轻松地像上面那样，把这个例子里面的情况都
条理清楚地分析总结出来吗？如果现在还不行，到考试之前，你必须掌握到这种程度，才
能得到一个自己很满意的分数。
经过以上的三个过程复习，相信读者对数据结构的掌握就可以到达比较高的水平了
，如果参加考试，获得一个比较满意的成绩也很有希望了。当然，达到这一
步并不容易，大量的练习是真正掌握的必由之路。因此，我们建议大家能够下功夫把本书
中的题目完整地做一遍。能够真正把本书中的所有题都掌握，绝不仅仅意味着仅会了书中
这几百道题目，而是意味着对数据结构这门课程的理解，以及对问题的分析能力都有很大
的提高，这样在考场上即使遇到未曾见过的题目，也就可以从容应对了！

多看书，多写程序。
最主要的是要多写程序，光看没什么用的。

你一定要从最基本开始，学数据最重要是学习数的查看