<?php

namespace app\data_structure\tree;

/**

 * php循环方法实现前序、中序、后序遍历二叉树

 * 二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）

 * https://www.cnblogs.com/rxbook/p/10419365.html

 */

class BinaryTree2

{

    public $value;

    public $left;

    public $right;

}

/**

 * 前序遍历

 * 根节点 ---> 左子树 ---> 右子树

 */

function preorder($root)

{

    //PE($root);

    $stack = array();

    array_push($stack, $root); //将$root(树对象)放入数组$stack中

    while (!empty($stack)) {

        //删除数组中的最后一个元素，并返回数组的最后一个值,此处$tree返回的就是完整的$root树对象,此时$stack为空

        $tree = array_pop($stack);

        //PE($tree);

        //PE($stack);

        echo $tree->value . ' ';//先输出根节点

        //由于在循环的过程中，每次array_pop都是删除最后一个元素并返回，因此要先将右子树压进去

        if ($tree->right != null) {

            array_push($stack, $tree->right);//压入右子树

        }

        //再将左树压进去，这样能保证左树处于最后一个元素，下次循环就会先处理左子树

        if ($tree->left != null) {

            array_push($stack, $tree->left); //压入左子树

        }

        //PE($stack);

    }

}

/**

 * 中序遍历

 * 左子树---> 根节点 ---> 右子树

 */

function inorder($root)

{

    $stack = array();

    //最开始，让$tree=最原始的树

    $tree = $root;

    while (!empty($stack) || $tree != null) {

        while ($tree != null) {

            //将整个树存入$stack数组中，然后让树变成左子树,依次循环，把全部的左子树存入$stack数组

            array_push($stack, $tree);

            //直到最后一个左子树，已经没有了left节点，此时$tree为空。相当于把所有层次的树全都压入了$stack数组中

            $tree = $tree->left;

        }

        //P($stack);

        //从$stack的尾部依次弹出元素并输出，结果就是左子树从最底部到最顶部的值

        $tree = array_pop($stack);

        echo $tree->value . " ";

        //此时，将 右子树赋值给 $tree。在没有到达主树之前，所有的右子树都是空，但是$stack不为空。

        //也就导致下次内循环的 while($tree != null)不会执行，一直到左子树输出完毕，到达主树(此时$stack为空)。

        //由于主树的右子树不为空，从而会执行 while($tree != null)，然后会再次将右子树的左子树依次输出，直到输出完最后一个右子树（已经没有了左子树）

        $tree = $tree->right;

        //PE($tree);

    }

}

/**

 * 后序遍历

 * 左子树 ---> 右子树 ---> 根节点

 */

function tailorder($root)

{

    $stack = array();

    $outstack = array();

    array_push($stack, $root);

    while (!empty($stack)) {

        $tree = array_pop($stack);

        array_push($outstack, $tree);//最先压入根节点，最后输出

        if ($tree->left != null) {

            array_push($stack, $tree->left);

        }

        if ($tree->right != null) {

            array_push($stack, $tree->right);

        }

    }

    while (!empty($outstack)) {

        $tree = array_pop($outstack);

        echo $tree->value . ' ';

    }

}

//测试

$a = new BinaryTree2();

$b = new BinaryTree2();

$c = new BinaryTree2();

$d = new BinaryTree2();

$e = new BinaryTree2();

$f = new BinaryTree2();

$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;

echo "php循环方法实现前序、中序、后序遍历二叉树: \n";

echo "前序遍历:";

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

echo "\n";

echo "中序遍历:";

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

echo "\n";

echo "后序遍历:";

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

echo "\n";