php实现先序、中序、后序遍历二叉树

二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆

 1 <?php
 2 class Node{
 3     public $value;
 4     public $left;
 5     public $right;
 6 }
 7 //先序遍历 根节点 ---> 左子树 ---> 右子树
 8 function preorder($root){
 9     $stack=array();
10     array_push($stack,$root);
11     while(!empty($stack)){
12         $center_node=array_pop($stack);
13         echo $center_node->value.' ';//先输出根节点
14         if($center_node->right!=null){
15             array_push($stack,$center_node->right);//压入左子树
16         }
17         if($center_node->left!=null){
18             array_push($stack,$center_node->left);
19         }
20     }
21 }
22 //中序遍历，左子树---> 根节点 ---> 右子树
23 function inorder($root){
24     $stack = array();
25     $center_node = $root;
26     while (!empty($stack) || $center_node != null) {
27              while ($center_node != null) {
28                  array_push($stack, $center_node);
29                  $center_node = $center_node->left;
30              }
31  
32              $center_node = array_pop($stack);
33              echo $center_node->value . " ";
34  
35              $center_node = $center_node->right;
36          }
37 }
38 //后序遍历，左子树 ---> 右子树 ---> 根节点
39 function tailorder($root){
40     $stack=array();
41     $outstack=array();
42     array_push($stack,$root);
43     while(!empty($stack)){
44         $center_node=array_pop($stack);
45         array_push($outstack,$center_node);//最先压入根节点，最后输出
46         if($center_node->left!=null){
47             array_push($stack,$center_node->left);
48         }
49         if($center_node->right!=null){
50             array_push($stack,$center_node->right);
51         }
52     }
53     
54     while(!empty($outstack)){
55         $center_node=array_pop($outstack);
56         echo $center_node->value.' ';
57     }
58     
59 }
60 $a=new Node();
61 $b=new Node();
62 $c=new Node();
63 $d=new Node();
64 $e=new Node();
65 $f=new Node();
66 $a->value='A';
67 $b->value='B';
68 $c->value='C';
69 $d->value='D';
70 $e->value='E';
71 $f->value='F';
72 $a->left=$b;
73 $a->right=$c;
74 $b->left=$d;
75 $c->left=$e;
76 $c->right=$f;
77 preorder($a);//A B D C E F 
78 echo '<hr/>';
79 inorder($a);//D B A E C F
80 echo '<hr/>';
81 tailorder($a);//D B E F C A

结果：

A B D C E F

D B A E C F

D B E F C A