二叉树算法 - 二叉树的遍历

Thursday. April 25, 2019 - 2 mins

PHP 数据结构与算法二叉树算法

数据结构与算法系列（三十）

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

有多种方式可以遍历二叉树，如果限制从左到右的习惯方式，主要分为三种：前序遍历、中序遍历和后序遍历。下面我们简单介绍这几种遍历方式及对应实现算法，所谓的前序、中序和后序都是以根节点作为参照系。

前序遍历

如果二叉树为空，则返回空，否则从根节点开始，先遍历左子树，再遍历右子树：

中序遍历

同样，如果是空树，返回空，否则从左子树最左侧的节点开始，然后从左到右依次遍历左子树，真正的根节点，最后是右子树（依然是从最左侧节点开始从左到右的顺序遍历）：

后序遍历

如果是空树，返回空，否则还是从左子树最左侧的节点开始，先遍历完叶子节点，再遍历父节点，遍历完左子树后，直接从右子树最左侧节点开始，按照和左子树同样的顺序遍历完右子树，最后访问根节点：

不同的遍历方式从不同维度将二叉树这种非线性的结构变成了某种意义上的线性序列，从而方便计算机操作。

遍历实现算法

二叉树的遍历其实就是个递归的过程，所以对应算法也采用递归来实现。

我们以二叉链表的方式来存储数组，对应的前序、中序、后序实现算法如下：

<?php

// 二叉链表节点
class Node
{
    public $data;
    public $left = null;
    public $right = null;

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

/**
 * 前序遍历
 * @param Node $tree
 */
function preOrderTraverse($tree)
{
    if ($tree == null) {
        return;
    }
    printf("%s\n", $tree->data);
    preOrderTraverse($tree->left);
    preOrderTraverse($tree->right);
}

/**
 * 中序遍历
 * @param Node $tree
 */
function midOrderTraverse($tree)
{
    if ($tree == null) {
        return;
    }
    midOrderTraverse($tree->left);
    printf("%s\n", $tree->data);
    midOrderTraverse($tree->right);
}

/**
 * 后序遍历
 * @param Node $tree
 */
function postOrderTraverse($tree)
{
    if ($tree == null) {
        return;
    }
    postOrderTraverse($tree->left);
    postOrderTraverse($tree->right);
    printf("%s\n", $tree->data);
}

我们为上述代码编写一段测试代码：

$node1 = new Node('A');
$node2 = new Node('B');
$node3 = new Node('C');
$node1->left = $node2;
$node1->right = $node3;

preOrderTraverse($node1);
print "=======\n";
midOrderTraverse($node1);
print "=======\n";
postOrderTraverse($node1);

对应的输出结果如下，表明三种遍历都没有问题：

下一篇我们将分享完整的二叉树节点增删改查实现。