二叉树的四种遍历方法：先序，中序，后序，层序

左始终在右前面，不同的是 中 这个位置

前序遍历

中序遍历

后序遍历

层序遍历

代码实现

基础类

class TreeNode
{
    public $left = null;
    public $right = null;
    public $parent = null;

    public $value = null;

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

    public function setLeft(TreeNode $node)
    {
        $this->left = $node;
        $this->left->parent = $this;
    }

    public function setRight(TreeNode $node)
    {
        $this->right = $node;
        $this->right->parent = $this;
    }

    public function __toString()
    {
        return (string)$this->value;
    }
}

$a = new  TreeNode('a');
$b = new  TreeNode('b');
$c = new  TreeNode('c');
$d = new  TreeNode('d');
$e = new  TreeNode('e');
$f = new  TreeNode('f');
$g = new  TreeNode('g');
$h = new  TreeNode('h');
$i = new  TreeNode('i');
$j = new  TreeNode('j');
$k = new  TreeNode('k');

$a->setLeft($b);
$a->setRight($c);
$b->setLeft($d);
$b->setRight($e);
$d->setLeft($h);
$d->setRight($i);
$e->setRight($j);
$c->setLeft($f);
$c->setRight($g);
$f->setRight($k);

遍历实现

class Tree
{

    public $root;

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

    public static function preorder($node)
    {
        if (! ($node instanceof TreeNode)) {
            return [];
        }

        return array_merge([$node], self::preorder($node->left), self::preorder($node->right));
    }

    public static function inorder($node)
    {
        if (! ($node instanceof TreeNode)) {
            return [];
        }

        return array_merge(self::inorder($node->left), [$node], self::inorder($node->right));
    }

    public static function postorder($node)
    {
        if (! ($node instanceof TreeNode)) {
            return [];
        }

        return array_merge(self::postorder($node->left), self::postorder($node->right), [$node]);
    }

    // 队列实现 层序遍历，先把根放进去，然后把左节点，右节点放进去
    public static function levelorder($node)
    {
        $data = [];
        if (! ($node instanceof TreeNode)) {
            return $data;
        }

        $queue = [$node]; // 临时处理队列, 把开始节点放进队列

        while (! empty($queue)) {
            $node = array_shift($queue); // 出队

            $data[] = $node;

            $node->left && array_push($queue, $node->left);
            $node->right && array_push($queue, $node->right);
        }

        return $data;
    }

    // 数组 下标方式
    public static function arrayLevelOrder($node)
    {
        $data = [];
        if (! ($node instanceof TreeNode)) {
            return $data;
        }

        $data = [$node];
        $index = 0; // 数组开头开始，遍历数组每一个元素的左右节点，添加在数组后面

        while (count($data) > $index)
        {
            $node = $data[$index];

            $node->left && ($data[] = $node->left);
            $node->right && ($data[] = $node->right);

            ++$index;
        }

        return $data;

    }

}

// 前序:a,b,d,h,i,e,j,c,f,k,g
echo  "前序:", implode(',', Tree::preorder($tree->root)), "\n";

// 中序:h,d,i,b,e,j,a,f,k,c,g
echo  "中序:", implode(',', Tree::inorder($tree->root)), "\n";

// 后序:h,i,d,j,e,b,k,f,g,c,a
echo  "后序:", implode(',', Tree::postorder($tree->root)), "\n";

// 层序:a,b,c,d,e,f,g,h,i,j,k
echo  "层序:", implode(',', Tree::levelorder($tree->root)), "\n";

// 层序:a,b,c,d,e,f,g,h,i,j,k
echo  "层序:", implode(',', Tree::arrayLevelOrder($tree->root)), "\n";

参考：二叉树的四种遍历方法笔记

本作品采用《CC 协议》，转载必须注明作者和本文链接