PHP 前序、中序、后序遍历二叉树

• 前序：ABDEGIHCF
• 中序：DBGIEHACF
• 后序：DIGHEBFCA

答案

<?php
class Node
{
    public $data = null;
    public $left = null;
    public $right = null;
}
$A = new Node();
$B = clone $A;
$C = clone $A;
$D = clone $A;
$E = clone $A;
$F = clone $A;
$G = clone $A;
$H = clone $A;
$I = clone $A;
$A->data = 'A';
$B->data = 'B';
$C->data = 'C';
$D->data = 'D';
$E->data = 'E';
$F->data = 'F';
$G->data = 'G';
$H->data = 'H';
$I->data = 'I';
$A->left = $B;
$A->right = $C;
$B->left = $D;
$B->right = $E;
$E->left = $G;
$E->right = $H;
$G->right = $I;
$C->right = $F;
/**
 * 前序遍历: 中左右
 * 中序遍历: 左中右
 * 后序遍历: 左右中
 */
function eatBtree($node)
{
    if ($node && $node->data) {
        eatBtree($node->left);
        eatBtree($node->right);
        echo $node->data;           //把这一行的位置换一换就能实现遍历方式的转变,放到最后是后序,放到最前是前序,放到中间是中序
    }
}
eatBtree($A);
/**
 * 层序遍历会用到队列
 */
function eatBtree2($node)
{
    $list[] = $node;
    while (count($list) > 0) {
        $cur = array_shift($list);
        if ($cur) {
            echo $cur->data;
            if ($cur->left) {
                $list[] = $cur->left;
            }
            if ($cur->right) {
                $list[] = $cur->right;
            }
        }
    }
}
eatBtree2($A);

参考资料

• https://zhidao.baidu.com/question/235504989.html