徐善通的随笔

千里之行, 始于足下



了解二叉树的三种遍历方式前序、中序、后序


二叉树的遍历方式

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

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

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

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

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

图解

alt

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

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

这里要说下中序遍历, 我一开始踩了个坑, 认为结果是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);
}

作者: 徐善通
地址: https://www.xstnet.com/article-139.html
声明: 除非本文有注明出处,否则转载请注明本文地址


我有话说



最新回复


正在加载中....

Copyrights © 2016-2019 醉丶春风 , All rights reserved. 皖ICP备15015582号-1