PHP는 비재귀적 이진 트리 탐색 및 스택 시뮬레이션 구현을 구현합니다.

이진 트리의 정의는 다음과 같습니다. 비어 있지 않은 이진 트리는 루트 노드와 왼쪽 및 오른쪽 하위 트리의 세 가지 기본 부분으로 구성됩니다. 액세스 위치에 따라 세 가지 순회 방법이 있습니다. 노드:
① NLR: Preorder Traversal(PreorderTraversal이라고도 함)
——노드에 액세스하는 작업은 왼쪽 및 오른쪽 하위 트리를 순회하기 전에 발생합니다.
② LNR: 중위순회(InorderTraversal)
——노드에 액세스하는 작업은 왼쪽 및 오른쪽 하위 트리(사이)를 탐색하여 발생합니다.
③ LRN: Postorder Traversal
——노드에 액세스하는 작업은 왼쪽 및 오른쪽 하위 트리를 순회한 후에 발생합니다.
아래와 같이:

바이너리 트리는 이전에 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' ).숨다(); $(this).addClass('has-numbering').parent().append($numbering); for (i = 1; i ').text(i)); }; $numbering.fadeIn(1700); }); });

위 내용은 PHP에서 이진 트리 탐색 및 스택 시뮬레이션 구현의 비재귀적 방법을 소개하며, 그 내용도 PHP 튜토리얼에 관심이 있는 친구들에게 도움이 되기를 바랍니다.