PHPで二分木(binary tree)を実現するプログラム(NLR、LNR、LRN)

2014年9月3日

1.二分木について
二分木の中でも、全てのノードが「葉であるか、二つの子を持っている（次数が2であるという）」ものを、全二分木 (full binary tree) と呼ぶ。完全二分木 (perfect binary tree, complete binary tree) は全ての葉が同じ「深さ」を持つ二分木を指す。

二分木–wikipedia

2.phpコード下記：
class Node {
public $value;
public $left;
public $right;
}
// NLR：PreorderTraversal
function preorder($root){
$stack = array();
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);
}
}
//LNR：InorderTraversal
function inorder($root){
$stack = array();
$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;
}
}
//LRN：PostorderTraversal
function postorder($root){
$pushstack = array();
$visitstack = array();
array_push($pushstack, $root);

while (!empty($pushstack)) {
$center_node = array_pop($pushstack);
array_push($visitstack, $center_node);
if ($center_node->left != null) array_push($pushstack, $center_node->left);
if ($center_node->right != null) array_push($pushstack, $center_node->right);
}

while (!empty($visitstack)) {
$center_node = array_pop($visitstack);
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

postorder($a);
//結果:D B E F C A