PHP 树的先序,中序,后序遍历

 1 <?php
 2     #树节点
 3     class Node {
 4         public $lc = null;    #左孩子
 5         public $rc = null;    #右孩子
 6         public $val;
 7         
 8         public function __construct($val) {
 9             $this->val = $val;
10         }
11     }
12     
13     #先序遍历
14     function preTraverse(Node $root) {
15         echo $root->val . " ";
16         if($root->lc != null) preTraverse($root->lc);
17         if($root->rc != null) preTraverse($root->rc);
18     }
19     
20     #中序遍历
21     function inTraverse(Node $root) {
22         if($root->lc != null) inTraverse($root->lc);
23         echo $root->val . " ";
24         if($root->rc != null) inTraverse($root->rc);
25     }
26     
27     #后序遍历
28     function postTraverse(Node $root) {
29         if($root->lc != null) postTraverse($root->lc);
30         if($root->rc != null) postTraverse($root->rc);
31         echo $root->val . " ";
32     }
33     
34     $root = new Node(3);
35     $node1 = new Node(2);
36     $node2 = new Node(1);
37     $node3 = new Node(6);
38     $node4 = new Node(5);
39     $node5 = new Node(7);
40     
41     $root->lc = $node1;
42     $root->rc = $node3;
43     $node1->lc = $node2;
44     $node3->lc = $node4;
45     $node3->rc = $node5;
46     
47     preTraverse($root);
48     echo "<br>";
49     inTraverse($root);
50     echo "<br>";
51     postTraverse($root);
52 ?>
输出
3 2 1 6 5 7
1 2 3 5 6 7
1 2 5 7 6 3