定义

二叉树的遍历是指从根结点出发，按照某种次序依次访问二叉树的所有结点，使得每个结点被访问一次且仅被访问一次。

遍历方法-深度优先

1.前序遍历

若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，然后再前序遍历右子树

如图

2.中序遍历

若二叉树为空，则空操作返回，否则从根结点开始（不是先访问根结点），中序遍历左子树，然后访问根结点，然后中序遍历右子树

如图

3.后序遍历

若二叉树为空，则空操作返回，否则从左到右先叶子后结点的顺序遍历访问左右子树，最后访问根结点。

如图

遍历方法-广度优先

1.层序遍历

若二叉树为空，则空操作返回，否则从树的第一层起，也就是从根结点起，从上往下访问，同一层中从左往右访问。

如图

PHP实现示例

二叉树结点类

class BitNode
{
    public $data; //数据域
    public $lchild; //左孩子指针
    public $rchild; //右孩子指针

    public function __construct($data)
    {
        $this->data = $data;
    }
}

二叉树生成及遍历类的实现

class BitreeDemo
{
    public $bitTree;
    public $arr, $len;
    public $root;//用于存储根结点

    public function __construct($arr = [])
    {
        $this->arr = $arr;          //要建立二叉树的数组
        $this->len = count($arr);   //数组长度
        if ($this->len == 0) {
            return "请传入数组内容";
        }
        //构建根节点
        $root = new BitNode($arr[0]);
        $root->lchild = $this->createTree(1);
        $root->rchild = $this->createTree(2);
        $this->root = $root;
    }

    /**
     * 递归构建二叉树
     **/
    public function createTree($key)
    {
        //约定好#为空结点，构建后就可以返回
        if ($this->arr[$key] == '#') {
            $node = new BitNode(null);
            return $node;
        }
        $node = new BitNode($this->arr[$key]);
        $left_key = $key*2+1;//二叉树左结点位置，数组从0开始计算的
        $right_key = $key*2+2;//二叉树右侧结点的位置
        if ($left_key < $this->len) {//防止越界
            $node->lchild = $this->createTree($left_key);
        }
        if ($right_key < $this->len) {//防止越界
            $node->rchild = $this->createTree($right_key);
        }
        return $node;
    }

    /**
     * 前序遍历输出
     */
    public function ahead_bl($root)
    {
        if ($root) {
            echo $root->data;
            $this->ahead_bl($root->lchild);
            $this->ahead_bl($root->rchild);
        }
    }

    /**
     * 中序遍历输出
     */
    public function center_bl($root)
    {
        if ($root) {
            $this->center_bl($root->lchild);
            echo $root->data;
            $this->center_bl($root->rchild);
        }
    }

    /**
     * 后序遍历输出
     */
    public function aback_bl($root)
    {
        if ($root) {
            $this->aback_bl($root->lchild);
            $this->aback_bl($root->rchild);
            echo $root->data;
        }
    }

    /**
     * 层序遍历输出
     */
    public function level_bl($root){
        $queue = [];//逆向队列数组
        array_unshift($queue,$root);//插入数组头部
        while(!empty($queue)){//当队列不为空的时候
            $node = array_pop($queue);//数组中最后一个元素出列
            echo $node->data;
            if($node->lchild){
                array_unshift($queue,$node->lchild);//左子结点插入数组头部
            }
            if($node->rchild){
                array_unshift($queue,$node->rchild);//右子结点插入数组头部
            }
        }
    }
}

测试用例，以前面说的图示为例子

$arr = ['A', 'B', 'C', 'D', '#', 'E', 'F', 'G', 'H', '#', '#', '#', 'I'];
echo "顺序结构存储的二叉树数组：<br />";
print_r($arr);
$node = new BitreeDemo($arr);
echo "<br />前序遍历结果：<br />";
$node->ahead_bl($node->root);
echo "<br />中序遍历结果：<br />";
$node->center_bl($node->root);
echo "<br />后序遍历结果：<br />";
$node->aback_bl($node->root);
echo "<br />层次遍历结果：<br />";
$node->level_bl($node->root);

测试结果

顺序结构存储的二叉树数组：
Array ( [0] => A [1] => B [2] => C [3] => D [4] => # [5] => E [6] => F [7] => G [8] => H [9] => # [10] => # [11] => # [12] => I ) 
前序遍历结果：
ABDGHCEIF
中序遍历结果：
GDHBAEICF
后序遍历结果：
GHDBIEFCA
层次遍历结果：
ABCDEFGHI