PHP は非再帰的なバイナリ ツリー トラバーサルとスタック シミュレーションの実装を実装します。

バイナリ ツリーの定義は次のとおりです: 空ではないバイナリ ツリーは、ルート ノードと左右のサブツリーの 3 つの基本部分で構成されます。ノードのアクセス位置に応じて 3 つの走査方法があります。 ① NLR: プリオーダー トラバーサル (プリオーダー トラバーサルとも呼ばれます)
——ノードにアクセスする操作は、その左右のサブツリーを走査する前に行われます。
②LNR：インオーダートラバーサル(InorderTraversal)
——ノードにアクセスする操作は、その左右のサブツリー (間) を走査することによって行われます。
③ LRN: ポストオーダートラバーサル
——ノードにアクセスする操作は、その左右のサブツリーを走査した後に発生します。
以下に示すように:

バイナリ ツリーは以前は 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('事前番号付け').hide(); $(this).addClass('has-numbering').parent().append($numbering); for (i = 1; i ').text(i)); }; $numbering.fadeIn(1700); }); }); 上記は、PHP でのバイナリ ツリー トラバーサルとスタック シミュレーションの非再帰的実装方法を、その側面も含めて紹介しました。PHP チュートリアルに興味のある友人に役立つことを願っています。