|
|
马上注册，结交更多好友，享用更多功能^_^
您需要 登录 才可以下载或查看，没有账号？立即注册
x
本帖最后由 陈功 于 2014-5-25 02:23 编辑
经过两周的努力，数据结构和算法快搞完了，由于时间紧还有很多代码没敲，只能等找到工作了在来慢慢消化。
学数据结构不得不提到树，提到树的操作不能不提到树的遍历，可以说遍历是最基础的东西，如果你还分不清
树的前序遍历，中序遍历，后续遍历的话，希望看我的帖子能搞定：
先给个转载个帖子大家回顾下树的基础：http://www.cnblogs.com/yc_sunniwell/archive/2010/06/27/1766233.html
11
图片我不知道怎么搞大点，你们另存为下来看吧！不好意思：图中还有空指针的地方还没画出来，D和C那里，不过不影响你们阅读：
遍历的原则：
1：左子树先于右子树遍历；
2：绿色路径(表示遍历是走的顺序)遇到空节点返回；
3：每个节点都会被遍历到三遍(这点很重要，A,B,G等周围蓝色的数字表示）
图中可以看到绿色的路径先是从A开始往左往下走，遇到空指针返回，回到A节点再往右边走，走到最后返回走，最后回到A。箭头表示走的顺序；
再看图中的A,B,G等根（或者叶）（还有的我没画出来），每一个节点（我就这样说了吧，本来是叫根或者叶的，你们懂就行了）绿色的线都经过它们3次，图中蓝色的数字表示。
前序遍历：对于前序遍历就表示绿色的路径在第一次经过节点时（蓝色数字为1的地方）就遍历，那么它的顺序就为
：A B D G J E C F H
这里我们可以看到它是从左到右开始遍历的，绿色路径遇到空就返回，同时是在第一次经过节点时遍历。
中序遍历：中序遍历就树在绿色路径第二次访问到节点时（蓝色数字为2的地方）遍历它既可，它的顺序就是
：G J D B E A C H F
后续遍历：就是树在绿色路径第三次访问到节点的时候（蓝色数字为3的地方）遍历，顺序的话
：J G D E B H F C A
这个顺序应该是对的，不对的话可以跟我说下，如果实在还不理解，我只好拿出我的终极武器了：
请观看严蔚敏的数据结构视频第19集20分钟处。这老师讲的真的很好，推荐看看。
|
|
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2014-5-25 02:16:25
置顶卡
千斤顶
显身卡
发表于 2014-5-25 08:00:15
楼主