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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
<?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