二叉树先根遍历、中根遍历、后根遍历

PHP实现二叉树的先根、中根、后根遍历算法。

<?php

class Node
{
    public $value;
    public $left;
    public $right;
}

//先根遍历
function preorder($root)
{
    $stack = [];
    array_push($stack, $root);
    while (!empty($stack)) {
        $center_node = array_pop($stack);
        echo $center_node->value . ' ';
        if ($center_node->right != null) {
            array_push($stack, $center_node->right);
        }
        if ($center_node->left != null) {
            array_push($stack, $center_node->left);
        }
    }
}

//中序遍历
function inorder($root)
{
    $stack = [];
    $center_node = $root;
    while (!empty($stack) || $center_node != null) {
        while ($center_node != null) {
            array_push($stack, $center_node);
            $center_node = $center_node->left;
        }

        $center_node = array_pop($stack);
        echo $center_node->value . " ";

        $center_node = $center_node->right;
    }
}

// 后序遍历
function tailorder($root)
{
    $stack = array();
    $outstack = array();
    array_push($stack, $root);
    while (!empty($stack)) {
        $center_node = array_pop($stack);
        array_push($outstack, $center_node);//最先压入根节点,最后输出
        if ($center_node->left != null) {
            array_push($stack, $center_node->left);
        }
        if ($center_node->right != null) {
            array_push($stack, $center_node->right);
        }
    }

    while (!empty($outstack)) {
        $center_node = array_pop($outstack);
        echo $center_node->value . ' ';
    }

}

$a = new Node();
$b = new Node();
$c = new Node();
$d = new Node();
$e = new Node();
$f = new Node();

$a->value = "A";
$b->value = "B";
$c->value = "C";
$d->value = "D";
$e->value = "E";
$f->value = "F";

$a->left = $b;
$a->right = $c;
$b->left = $d;
$c->left = $e;
$c->right = $f;

preorder($a); // A B D C E F
inorder($a); // D B A E C F
tailorder($a); // D B E F C A

 上一篇
Linux管道命令 Linux管道命令
管线符号 | 仅能处理经由前面一个指令传来的正确信息,也就是 standard output ( STDOUT ) 的信息. 1,cut 取出一段文本,以行为单位 $ cut -d `分隔字符` -f 第几个字段 $ cut -c 字符
2017-08-08 Mantis
下一篇 
MySQL数据库优化的几种方式 MySQL数据库优化的几种方式
数据库在一个完整的数据系统中扮演着很重要的角色,数据库的性能问题一直是影响一套系统性能的关键所在;在不断的工作和学习中,我们会遇到各种各样关于数据库操作方面的问题,我们也是时刻强调一定要设计好一个规范、性能良好的数据库,以下我们总结一下几种
2017-07-26 Mantis