数据结构

PHP二叉树的初体验

$a=new Node();

$b=new Node();

$c=new Node();

$d=new Node();

$e=new Node();

$f=new Node();

$g=new Node();

$h=new Node();

$i=new Node();

$j=new Node();

$k=new Node();

 

$a->value='A';

$b->value='B';

$c->value='C';

$d->value='D';

$e->value='E';

$f->value='F';

$g->value='G';

$h->value='H';

$i->value='I';

$j->value='J';

$k->value='K';

$a->left=$b;

$a->right=$g;

$b->left=$c;

$b->right=$f;

$c->left=$d;

$c->right=$e;

$g->left=$h;

$g->right=$i;

$i->left=$j;

$i->right=$k;

echo '非递归算法<br><hr/>';

echo 'preorder_<br><hr/>';

preorder_($a);//A B C D E F G H I J K 

echo '<br>inorder_<br><hr/>';

inorder_($a);//D C E B F A H G J I K

echo '<br>tailorder_<br><hr/>';

tailorder_($a);//D E C F B H J K I G A

 

echo '<br><br>递归算法<br><hr/>';

echo 'preorder<br><hr/>';

preorder($a);//A B C D E F G H I J K

echo '<br>inorder<br><hr/>';

inorder($a);//D C E B F A H G J I K

echo '<br>tailorder<br><hr/>';

tailorder($a);//D E C F B H J K I G A

class Node {

    public $value;

    public $left;

    public $right;

}

 

function preorder(Node $node){

    if($node->value){

        echo $node->value.' ';

    }

    if($node->left){

        preorder($node->left);

    }

    if($node->right){

        preorder($node->right);

    }

}

function inorder(Node $node){

    if($node->left){

        inorder($node->left);

    }

    if($node->value){

        echo $node->value.' ';

    }

    if($node->right){

        inorder($node->right);

    }

}

function tailorder(Node $node){

    if($node->left){

        tailorder($node->left);

    }

    if($node->right){

        tailorder($node->right);

    }

    if($node->value){

        echo $node->value.' ';

    }

}

function preorder_(Node $node){

    $stack = array();

    array_push($stack, $node);

    while(!empty($stack)){

        $tmp = array_pop($stack);

        echo $tmp->value.' ';

        if($tmp->right){

            array_push($stack, $tmp->right);

        }

        if($tmp->left){

            array_push($stack, $tmp->left);

        }

    }

}

function inorder_(Node $node){

    $stack = array();

    $tmp = $node;

    while($tmp || !empty($stack)){

        if($tmp){

            array_push($stack, $tmp);

            $tmp = $tmp->left;

        }else{

            $tmp = array_pop($stack);

            echo $tmp->value.' ';

            $tmp= $tmp->right;

        }

    }

}

 

function tailorder_(Node $node){

    $stack = array();

    $outstack = array();

    $tmp = $node;

    array_push($stack, $tmp);

    // while 外 先压$outstack后出$outstack

    while(!empty($stack)){

        $tmp = array_pop($stack);

        array_push($outstack, $tmp);

        

        // while 内 先压$stack先出$outstack

        if($tmp->left){

            array_push($stack, $tmp->left);

        }

        if($tmp->right){

            array_push($stack, $tmp->right);

        }

        

    }

    while(!empty($outstack)){

        $tmp = array_pop($outstack);

        echo $tmp->value.' ';

    }

}

 

 

——————————

运行效果: