二叉树先根遍历、中根遍历、后根遍历

PHP实现二叉树的先根、中根、后根遍历算法。

<?php

class Node
{
    public $value;
    public $left;
    public $right;
}


function preorder($root)
{
    $stack = [];
    array_push($stack, $root);
    while (!empty($stack)) {
        $center_node = array_pop($stack);
        echo $center_node->value . ' ';
        if ($center_node->right != null) {
            array_push($stack, $center_node->right);
        }
        if ($center_node->left != null) {
            array_push($stack, $center_node->left);
        }
    }
}

//中序遍历
function inorder($root)
{
    $stack = [];
    $center_node = $root;
    while (!empty($stack) || $center_node != null) {
        while ($center_node != null) {
            array_push($stack, $center_node);
            $center_node = $center_node->left;
        }

        $center_node = array_pop($stack);
        echo $center_node->value . " ";

        $center_node = $center_node->right;
    }
}

// 后序遍历
function tailorder($root)
{
    $stack = array();
    $outstack = array();
    array_push($stack, $root);
    while (!empty($stack)) {
        $center_node = array_pop($stack);
        array_push($outstack, $center_node);//最先压入根节点，最后输出
        if ($center_node->left != null) {
            array_push($stack, $center_node->left);
        }
        if ($center_node->right != null) {
            array_push($stack, $center_node->right);
        }
    }

    while (!empty($outstack)) {
        $center_node = array_pop($outstack);
        echo $center_node->value . ' ';
    }

}

$a = new Node();
$b = new Node();
$c = new Node();
$d = new Node();
$e = new Node();
$f = new Node();

$a->value = "A";
$b->value = "B";
$c->value = "C";
$d->value = "D";
$e->value = "E";
$f->value = "F";

$a->left = $b;
$a->right = $c;
$b->left = $d;
$c->left = $e;
$c->right = $f;

preorder($a); // A B D C E F
inorder($a); // D B A E C F
tailorder($a); // D B E F C A