关于二叉树的遍历有很多的方法, 下面介绍两个经典的遍历算法: BFS和DFS。一个是深度优先遍历, 一个是广度有优先遍历。 这两种遍历算法均属于盲目的遍历算法, 一般而言, 启发式的遍历搜索算法比较好一些。 。 关于各种遍历算法的对比, 将会在后面逐一提及。 这里不在赘述。
由于树是一个非线性的数据结构, 显然不能像linked list , 或者Array那样通过从头像最末尾移动去实现遍历每一个元素, 我们使用的是BFS和DFS算法。
例如下面的一个二叉树:
所谓的树遍历(Tree traversal)就是 process of visiting each node in the tree exactly once in some order。
这里, visiting的含义就是reading/processing data in a node, 例如打印节点的数据(data)。
根据树的节点被遍历的order, 主要有两个经典的遍历算法: BFS(breadth first search)和DFS(depth first search)(这也是在图这个数据结构中常用的遍历图的算法)。
我们可以将Trees视为一种特殊的graph data structures。
BFS: 遍历树节点的顺序是逐层逐层的将所有的节点遍历完。
DFS: 深度优先遍历,
不难看出, BFS主要有三种遍历形式, preorder, inorder, 还有post order的形式(尽管L和R看起来可以交换顺序, 这样就变成了6种, 但是in convention, 我们认为一般从左子树开始, 所以姑且认为有3种, 而非6种)下面一一介绍:
Preorder traversal of the binary tree:
访问的顺序为:
遍历到A节点时候, 打印A的数据, 然后查看左子树。 此时A的左子树为NULL, 于是开始查看A的右子树:
后由于这个节点是叶节点A, A的右子树也是NULL, 于是返回到节点B(递归返回), 查看节点B的右子树, B有右子树, 所以开始遍历右子树:
对于节点D, 同样的:
接下来, 返回到节点D, 访问其右子树:
于是到达E点, 同样的打印出数据, 访问左子树, 为NULL, 再访问右子树, 同样为NULL, 递归返回到根节点处:
最终我们访问完了根节点F的所有left subtree 的节点, 开始去访问F的right subtree, 先到J点, 打印出J节点数据, 让后访问左子树, 到达G点, 发现没有左子树, 访问G的右子树。
于是访问G的子树, 到达I节点, 打印出I的数据, 访问I的左子树, 不是NULL, 到达H ,打印出H的data, 由于H是叶子节点, 所以左右子树均为NULL, 递归返回到I, 返现I的右子树也是NULL, 返回到J:
看到J的右子树不是NULL, 访问K节点, 打印出数据K的左右子树均为NULL, 所以最终所有的节点均被访问了:
DFS中的: Inorder Traversal 如下:
接下来, 到达A, 发现A的左子树为NULL, 接下来打印出数据, 开始访问A的右子树, 亦为NULL, 所以返回到节点B处, 打印出B的数据, 然后访问节点B的右子树, 于是到达节点C, 访问节点C的左子树, 为NULL, 所以打印出节点C的数据, 然后访问节点C的左子树, 也是NULL, 于是就返回到D:
递归返回到节点D的时候, 打印出节点D的数据, 开始访问节点D的右子树, 到达E, 同样有:
等等, 省略中间步骤, 最终遍历完所有的节点:
NOTE: 之所以叫做inorder, 是因为如果是一个BST, 我们最终打印出来的顺序是一个排好序的(从小到达的)数据。
PostOrder traversal, 同理, 很容易理解。 具体的访问节点的顺序如下:
C++ Binary Tree Traversal,布布扣,bubuko.com
原文:http://blog.csdn.net/a130737/article/details/37991453