[Day14]程序菜鸟自学C++资料结构演算法 – 二元树的走访Binary Tree Traversal

前言：昨天介绍完了二元树的两种储存方式，今天要来介绍如何读取二元树，称之为走访，而走访方式就有大约四种，今天就一一为大家介绍。

何谓走访？走访其实就是要读取到每一个节点，不同的走访方式在於要先处理哪一边的资料，且左子树的优先权必大於右子树，所以重点就在根节点的位置在哪里。

1.前序走访 Preorder：

前序走访的顺序是根节点→左子树→右子树。

牛刀小试：先把左子树和右子树想像成一个大节点，向上面的图片一样，会比较容易成功。

前序走访：x+46-82

实作：这次用上一篇链结串列表示法的二元树程序码作范例，可以先准备好呦=U=

2.中序走访 Inorder：

可以说是我们最熟悉的走访方式，平常我们所写的算式或是按计算机的顺序都是中序走访。中序走访顺序左子树→根节点→右子树。

牛刀小试：

中序走访：4+6x8-2

实作：

3.後序走访 Postorder：

後续走访的顺序左子树→右子树→根节点。

牛刀小试：

後序走访：46+82-x

实作：

4.层序走访 Level-order：

与前三种走访方式较为不同，以层次的等级决定走访的顺序第一层→第二层→第三层…以此类推。

牛刀小试：

层序走访：x+-4682

实作：需用到伫列存取树的节点。

今日小结：今天介绍了四种二元树的走访，只要注意根节点的位置就一定能轻松掌握，明天会把程序码完整地补上还会继续介绍二元树的更多种运用。