PHP实现二叉树遍历非递归方式，栈模拟实现

二叉树定义是这样的：一棵非空的二叉树由根结点及左、右子树这三个基本部分组成，根据节点的访问位置不同有三种遍历方式：
① NLR：前序遍历(PreorderTraversal亦称(先序遍历))
——访问结点的操作发生在遍历其左右子树之前。
② LNR：中序遍历(InorderTraversal)
——访问结点的操作发生在遍历其左右子树之中(间)。
③ LRN：后序遍历(PostorderTraversal)
——访问结点的操作发生在遍历其左右子树之后。
如下图：

对于二叉树的以前都是用C写的，递归遍历， 用PHP也可以简单模拟，下面这个例子算是最简单的一种遍历了（参考网络的）。

/**
 * 二叉树遍历
 * @blog
 */
class Node {
    public$value;
    public$left;
    public$right;
}
//前序遍历，访问根节点->遍历子左树->遍历右左树
function preorder($root){
    $stack=array();
    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=array();
    $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 postorder($root){
        $pushstack=array();
        $visitstack=array();
        array_push($pushstack, $root);

        while (!empty($pushstack)) {
            $center_node= array_pop($pushstack);
            array_push($visitstack, $center_node);
            if ($center_node->left !=null) array_push($pushstack, $center_node->left);
            if ($center_node->right !=null) array_push($pushstack, $center_node->right);
        }

        while (!empty($visitstack)) {
            $center_node= array_pop($visitstack);
            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
postorder($a); //结果是:  D B E F C A

http://www.phpddt.com/php/binary-tree-traverse.html

').addClass('pre-numbering').hide(); $(this).addClass('has-numbering').parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($('

').text(i)); }; $numbering.fadeIn(1700); }); });

以上就介绍了PHP实现二叉树遍历非递归方式，栈模拟实现，包括了方面的内容，希望对PHP教程有兴趣的朋友有所帮助。