PHP实现二叉树遍历非递归方式，栈模拟实现-php教程-PHP中文网

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

php中文网

发布： 2016-07-29 09:03:14

原创

1216人浏览过

ViiTor实时翻译

AI实时多语言翻译专家！强大的语音识别、AR翻译功能。

116

查看详情

二叉树定义是这样的：一棵非空的二叉树由根结点及左、右子树这三个基本部分组成，根据节点的访问位置不同有三种遍历方式：
① NLR：前序遍历(PreorderTraversal亦称(先序遍历))
——访问结点的操作发生在遍历其左右子树之前。
② LNR：中序遍历(InorderTraversal)
——访问结点的操作发生在遍历其左右子树之中(间)。
③ LRN：后序遍历(PostorderTraversal)
——访问结点的操作发生在遍历其左右子树之后。
如下图：
PHP实现二叉树遍历非递归方式，栈模拟实现
对于二叉树的以前都是用C写的，递归遍历，用PHP也可以简单模拟，下面这个例子算是最简单的一种遍历了（参考网络的）。

<code><span>/**
 * 二叉树遍历
 * @blog<http://www.phpddt.com>
 */</span>
class Node {
    <span>public</span><span>$value</span>;
    <span>public</span><span>$left</span>;
    <span>public</span><span>$right</span>;
}
<span>//前序遍历，访问根节点->遍历子左树->遍历右左树</span>
function preorder(<span>$root</span>){
    <span>$stack</span><span>=</span><span>array</span>();
    array_push(<span>$stack</span>, <span>$root</span>);
    <span>while</span>(<span>!</span>empty(<span>$stack</span>)){
        <span>$center_node</span><span>=</span> array_pop(<span>$stack</span>);
        echo <span>$center_node</span><span>-></span>value<span>.</span><span>' '</span>;

        <span>if</span>(<span>$center_node</span><span>-></span>right <span>!=</span><span>null</span>) array_push(<span>$stack</span>, <span>$center_node</span><span>-></span>right);
        <span>if</span>(<span>$center_node</span><span>-></span>left <span>!=</span><span>null</span>) array_push(<span>$stack</span>, <span>$center_node</span><span>-></span>left);
    }
}
<span>//中序遍历，遍历子左树->访问根节点->遍历右右树</span>
function inorder(<span>$root</span>){
    <span>$stack</span><span>=</span><span>array</span>();
    <span>$center_node</span><span>=</span><span>$root</span>;
    <span>while</span> (<span>!</span>empty(<span>$stack</span>) <span>||</span><span>$center_node</span><span>!=</span><span>null</span>) {
             <span>while</span> (<span>$center_node</span><span>!=</span><span>null</span>) {
                 array_push(<span>$stack</span>, <span>$center_node</span>);
                 <span>$center_node</span><span>=</span><span>$center_node</span><span>-></span>left;
             }

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

             <span>$center_node</span><span>=</span><span>$center_node</span><span>-></span>right;
         }
}
<span>//后序遍历，遍历子左树->访问子右树->遍历根节点</span>
function postorder(<span>$root</span>){
        <span>$pushstack</span><span>=</span><span>array</span>();
        <span>$visitstack</span><span>=</span><span>array</span>();
        array_push(<span>$pushstack</span>, <span>$root</span>);

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

        <span>while</span> (<span>!</span>empty(<span>$visitstack</span>)) {
            <span>$center_node</span><span>=</span> array_pop(<span>$visitstack</span>);
            echo <span>$center_node</span><span>-></span>value<span>.</span><span>" "</span>;
        }
}

<span>//创建如上图所示的二叉树</span><span>$a</span><span>=</span><span>new</span> Node();
<span>$b</span><span>=</span><span>new</span> Node();
<span>$c</span><span>=</span><span>new</span> Node();
<span>$d</span><span>=</span><span>new</span> Node();
<span>$e</span><span>=</span><span>new</span> Node();
<span>$f</span><span>=</span><span>new</span> Node();
<span>$a</span><span>-></span>value <span>=</span><span>'A'</span>;
<span>$b</span><span>-></span>value <span>=</span><span>'B'</span>;
<span>$c</span><span>-></span>value <span>=</span><span>'C'</span>;
<span>$d</span><span>-></span>value <span>=</span><span>'D'</span>;
<span>$e</span><span>-></span>value <span>=</span><span>'E'</span>;
<span>$f</span><span>-></span>value <span>=</span><span>'F'</span>;
<span>$a</span><span>-></span>left <span>=</span><span>$b</span>;
<span>$a</span><span>-></span>right <span>=</span><span>$c</span>;
<span>$b</span><span>-></span>left <span>=</span><span>$d</span>;
<span>$c</span><span>-></span>left <span>=</span><span>$e</span>;
<span>$c</span><span>-></span>right <span>=</span><span>$f</span>;

<span>//前序遍历</span>
preorder(<span>$a</span>);  <span>//结果是：A B D C E F</span>
inorder(<span>$a</span>);  <span>//结果是： D B A E C F</span>
postorder(<span>$a</span>); <span>//结果是:  D B E F C A</span></code>

登录后复制

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

').addClass('pre-numbering').hide(); $(this).addClass('has-numbering').parent().append($numbering); for (i = 1; i ').text(i)); }; $numbering.fadeIn(1700); }); });

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