二叉树的遍历

遍历是指：按某种搜索路径访问二叉树的每个结点，而且每个结点仅被访问一次。

对于线性存储结构，只有一种方式遍历。

对于链式存储结构，有先序遍历、中序遍历、后序遍历等。

• 先序遍历序列：A B D E G C F — 先输出，再左树，最后右树。
• 中序遍历序列：D B G E A C F — 先左树，再输出，最后右树。
• 后序遍历序列：D G E B F C A — 先左树，再右树，最后输出。

知道中序遍历序列和先序或后序中任意一个，即可还原树。

除此之外还有按层遍历，需要引入队列辅助。

通过遍历我们可以得到结点的层次以及树的层等重要参数。

链接到

• 上一个知识点：6.5 二叉树的存储结构
• 下一个知识点：6.7 二叉树的相关算法