遍历二叉树是指按照某种顺序或规则访问二叉树中的每个结点，使每个结点被访问一次且仅被访问一次。遍历二叉树实质上是对一个非线性结构进行线性化操作。

由二叉树的定义可知，一棵非空二叉树由根结点、根结点的左子树和根结点的右子树三部分组成。

因此，只要依次遍历这三部分，就可以遍历整个二叉树。若以D、L、R分别表示访问根结点、遍历根结点的左子树、遍历根结点的右子树，则二叉树的遍历方式有六种：DLR、LDR、LRD、DRL、RDL和RLD。如果限定先左后右，则只有前三种方式，即

DLR——先（根）序遍历，

LDR——中（根）序遍历，

LRD——后（根）序遍历。

 

先序遍历二叉树的递归算法为：若二叉树为空，遍历结束。否则，访问根结点；先序遍历根结点的左子树；先序遍历根结点的右子树。

线索二叉树

首先了解几个相关的概念：

（1）前驱与后继：在二叉树的先序、中序或后序遍历序列中两个相邻的结点互称为前驱与后继。

（2）线索：指向前驱或后继结点的指针。

（3）线索二叉树：加上线索的二叉链表表示的二叉树。

（4）线索化：对二叉树按某种遍历次序使其变为线索二叉树的过程。

当以二叉链表作为存储结构时，只能找到结点的左右孩子的信息，而不能在结点的任一序列中直接找到前驱与后继信息，这种信息只有在遍历的动态过程中才能得到。如果想保存这种信息，最简单的方法是在每个结点上增加两个指针域，分别用来表示在遍历时的前驱和后继信息。这样增加指针域之后，会使结构的存储密度大大降低。另一方面，有n个结点的二叉链表中必定存在n+1个空指针域。由此想到利用这些空指针域存放结点的前驱和后继信息。这样还需要两个标志域用来指示存储的是孩子信息还是线索信息（前驱或后继信息）。