PHP implements non-recursive binary tree traversal and stack simulation implementation

The definition of a binary tree is as follows: a non-empty binary tree consists of three basic parts: the root node and the left and right subtrees. There are three traversal methods depending on the access position of the node:
① NLR: Preorder Traversal (also known as Preorder Traversal)
——The operation of accessing a node occurs before traversing its left and right subtrees.
② LNR: Inorder Traversal (InorderTraversal)
——The operation of accessing a node occurs by traversing its left and right subtrees (between).
③ LRN: Postorder Traversal
——The operation of accessing a node occurs after traversing its left and right subtrees.
As shown below:

Binary trees were previously written in C, and recursive traversal can also be simply simulated with PHP. The following example is considered the simplest kind of traversal (refer to the Internet).

<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); }); });

The above introduces the non-recursive method of binary tree traversal and stack simulation implementation in PHP, including aspects of it. I hope it will be helpful to friends who are interested in PHP tutorials.