PHP實作二元樹遍歷非遞歸方式，堆疊模擬實現

二叉樹定義是這樣的：一棵非空的二元樹由根結點及左、右子樹這三個基本部分組成，根據節點的訪問位置不同有三種遍歷方式：
① NLR：前序遍歷(PreorderTraversal亦稱(先序遍歷))
——訪問結點的操作發生在遍歷其左右子樹之前。
② LNR：中序遍歷(InorderTraversal)
——訪問結點的操作發生在遍歷其左右子樹之中(間)。
③ LRN：後序遍歷(PostorderTraversal)
——訪問結點的操作發生在遍歷其左右子樹之後。
如下圖：

對於二元樹的以前都是用C寫的，遞歸遍歷， 用PHP也可以簡單模擬，下面這個例子算是最簡單的一種遍歷了（參考網路的）。

<code><span>/**
 * 二叉树遍历
 * @blog<http:>
 */</http:></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教程有興趣的朋友有所幫助。