PHP 创建二叉树镜像(交换左右子树)

 1 <?php
 2     #生成二叉树镜像(交换树的所有左右节点)
 3 
 4     class Node {
 5         public $data = null;
 6         public $parent = null;
 7         public $left = null;
 8         public $right = null;
 9     }
10 
11     #递归方法
12     function mirror_recursive($root) {
13         if ($root === null) {
14             return;
15         }
16 
17         mirror_recursive($root->left);
18         mirror_recursive($root->right);
19         $temp = $root->left;
20         $root->left = $root->right;
21         $root->right = $temp;
22     }
23 
24     #非递归方法,用一个栈或队列都可以,类似于深度优先和广度优先遍历
25     function mirror_norec($root) {
26         $queue = array();
27         array_unshift($queue, $root);
28 
29         while (!empty($queue)) {
30             $cnode = array_pop($queue);
31             if ($cnode->left !== null) array_unshift($queue, $cnode->left);
32             if ($cnode->right !== null) array_unshift($queue, $cnode->right);
33             $temp = $cnode->left;
34             $cnode->left = $cnode->right;
35             $cnode->right = $temp;
36         }
37     }
38 
39     #中序遍历
40     function inorder_traverse($root) {
41         if ($root->left !== null) inorder_traverse($root->left);
42         echo $root->data . " ";
43         if ($root->right !== null) inorder_traverse($root->right);
44     }
45 
46     $root = new Node();
47     $n1 = new Node();
48     $n2 = new Node();
49     $n11 = new Node();
50     $n12 = new Node();
51     $n13 = new Node();
52     $n14 = new Node();
53     $n15 = new Node();
54     $n21 = new Node();
55 
56     $root->data = 0;
57     $n1->data = 1;
58     $n2->data = 2;
59     $n11->data = 11;
60     $n12->data = 12;
61     $n13->data = 13;
62     $n14->data = 14;
63     $n15->data = 15;
64     $n21->data = 21;
65 
66     $root->left = $n1;
67     $root->right = $n2;
68     $n1->left = $n11;
69     $n1->right = $n12;
70     $n11->left = $n13;
71     $n12->right = $n14;
72     $n13->left = $n15;
73     $n2->right = $n21;
74 
75     inorder_traverse($root);
76     echo "<br>";
77     mirror_recursive($root);
78     inorder_traverse($root);
79     echo "<br>";
80     mirror_norec($root);
81     inorder_traverse($root);
82 ?>
15 13 11 1 12 14 0 2 21
21 2 0 14 12 1 11 13 15
15 13 11 1 12 14 0 2 21