醉丶春风的Blog

二叉树的遍历方式

二叉树遍历分为三种：前序、中序、后序，其中中序遍历最为重要, 是因为中序遍历会按顺序输出元素。

之所以这么叫？是根据根节点的顺序命名的。

• 前序遍历：遍历方式为: 根-->左-->右, 先输出根节点，在依次前序遍历左子树和右子树。
• 中序遍历：遍历方式为: 左-->根-->右, 先中序遍历左子树，在输出根节点，最后中序遍历右子树
• 后序遍历：遍历方式为: 左-->右-->根, 先后序遍历左子树，接着后序遍历右子树，最后输出根节点

三种遍历方式的不同取决于根结点

• 根在左右子树前的遍历称为前序遍历
• 根在左右子树后的遍历称为后序遍历
• 根在左右子树中间的遍历称为中序遍历

图解

对于上图中的二叉树来说, 下面是三种遍历的结果

• 前序遍历: 结果为 ABCDEFGIH
• 中序遍历: 结果为 CDBAFEIGH
• 后序遍历: 结果为 DCBFIHGEA

这里要说下中序遍历, 我一开始踩了个坑, 认为结果是DCBAFIHGE, 这个结果是错的

之所以是C开头, 是因为中序遍历的顺序为 左->根->右, 如图, C没有左子树, 则下一个元素就是对应的根结点, 也就是C, 然后才是右子树D, 然后回到C的父结点B, 再往上到根标点A

右子树的顺序为:

因为是先左结点, 所以排第一的是F, 然后到E, 接着到了E的右子树,但是下一个元素并不是该右子树, 下一个元素是该子树的左子树 I, 然后才到该子树G, 最后到H, 最后顺序为: CDBAFEIGH

递归遍历代码实现

前序遍历

/**
 * 前序遍历
 * 针对每一层的根元素, 先输出左右子树, 再输出根元素
 * @param $rootNode
 */
public function preOrder($rootNode)
{
    if ($rootNode === null) {
        return;
    }
    $this->preOrder($rootNode->left);

    $this->preOrder($rootNode->right);

    echo $rootNode->data, ',';
}

中序遍历

/**
 * 中序遍历
 * 针对每一层的根元素, 先输出左子树, 再输出根元素, 最后输出右子树
 * @param $rootNode
 */
public function inOrder($rootNode)
{
    if ($rootNode === null) {
        return;
    }
    $this->inOrder($rootNode->left);

    echo $rootNode->data, ',';

    $this->inOrder($rootNode->right);
}

后序遍历

/**
 * 后序遍历
 * 针对每一层的根元素, 先输出根元素, 再输出左右子树
 * @param $rootNode
 */
public function postOrder($rootNode)
{
    if ($rootNode === null) {
        return;
    }

    echo $rootNode->data, ',';

    $this->postOrder($rootNode->left);

    $this->postOrder($rootNode->right);
}