acm第7周总结

本周重点还是阅读了搜索有关的资料，还看了一些有关二叉树的知识。

在看搜索题目的过程中，也遇到了一些二叉树的搜索题目，在这里选取一道题来复习一下本周学习的二叉树的一些知识。

洛谷p1030

该题用到的树的知识点主要是二叉树的先序、中序、后序遍历。

首先先来说一下这三种不同的排序分别是怎么遍历二叉树的。

先序遍历:根结点->左子树->右子树

性质:

序列的第一个一定是根结点

中序遍历:左子树->根结点->右子树

性质:

只要知道根结点，就能通过根结点在中序遍历的位置区分出左子树和右子树

后序遍历:左子树->右子树->根结点

序列的最后一个一定是根结点

接下来用下图举个例子来详细的说明一下这三种遍历方式。

 先序遍历:

先访问根结点A，再访问左子树(即BDE组成的数)，在左子树中，再把B作为根结点，访问B，再访问B之下的左子树(即D组成的树)，由于D子树为空，所以碰到了死胡同，所以就返回上一个结点B(此处用到了递归)，然后再遍历B的右子树(即E组成的树)，而E子树也为空，所以整个左子树(即BDE)遍历完毕，返回A结点，再用同样的方式遍历右子树。

即遍历顺序为ABDECF

中序遍历:

根据中序遍历的要求先遍历A的左子树，输出顺序为DBE，然后访问根结点A，再按中序遍历的要求遍历右子树，即右子树输出顺序为CF，所以整个遍历顺序为DBEACF

后序遍历:

根据后序遍历的要求先遍历A的左子树，输出DEB，再按后序遍历要求遍历A的右子树，输出FC，最后再访问A，整个遍历顺序为DEBFCA

了解了这三种遍历方法及性质，再来看这道题

该题的思路主要是先利用后序排列的性质找到第一个根结点A，再根据中序遍历的性质将剩余部分分为两个子树B和DC，再根据后序遍历这两个树的顺序B和DC找到接下来的结点即B和C，由于B在前所以先访问B，再访问C，最后只剩下D再访问D，就可得先序排列ABCD，该题有尝试做过，但是以我目前的水平，不看看题解是做不出来的，这说明就算是知道了做题的思路，要想用代码的形式将思路展现出来还是比较困难的，这还需要大量基础知识点的积累。

此外，在看题的过程中，我还醒悟了一点，就是递归与回溯之间的区别，之前这个地方理解的比较模糊，就是觉得从一个结点递归回上一个结点，就是回溯了，其实不是这样的，只有在递归时把该结点走过的痕迹清除掉才能算是回溯，否则就是普通的递归。