二叉查找树：简单点说就是颗做孩子小，右孩子大的树
说几个关键点
最小值：总是树的最左节点的key
最大值：总是树的最右节点的key
前趋：按照中序遍历的顺序，遍历输出时当前节点的前一个节点
如果当前节点有左子节点，前驱就是当前节点的左边的最右节点，也可以认为是以当前节点的左孩子为根的树的最大值
如果当前节点没有左子节点，前驱就是找到一个父节点，使得当前节点位于该父节点的右边，不明白的看代码
后继：按照中序遍历的顺序，遍历输出时当前节点的后一个节点
如果当前节点有右子节点，后继就是当前节点的右边的最左节点，也可以认为是以当前节点的右孩子为根的树的最小值
如果当前节点没有柚子节点，后继就是找到一个父节点，使得当前节点位于该父节点的左边
插入节点：插入节点的思想是从root开始用当前节点的key值比较待插入节点的key值，待插入key比当前节点key小，则当前节点变为当前节点左孩子，否则变为当前节点右孩子，继续比较key，直到当前节点为null(到达树底部)，记下比较完的最后一个叶子节点为P，如果P不为空，比较这个叶子节点和待插入节点的key，待插入节点小则作为这个叶子节点的左孩子，否则作为他的右孩子，如果P为空，说明这是一个空树，直接将待插入节点作为根返回即可
删除节点：删除节点分三种情况
1）如果待删除节点没有孩子，直接将节点删除即可。
2）如果待删除节点只有一个孩子，将待删除节点删除，并连接待删除节点的孩子和父亲，原来的左孩子还是作为其父节点的左孩子，原来的右孩子还是作为其父亲的右孩子
3）如果待删除节点有两个孩子，则找到待删除节点的直接后继，将后继删除（直接后继肯定只有一个子节点，要不然不可能是一个直接后继），然后按照2）连接后继的子节点和父节点，最后交换待删除节点和后继节点的key值
下面是代码和输出结果
1 <?php
2 #二叉查找树实现
3 #节点
4 class Node {
5 public $key = null;
6 public $parent = null;
7 public $left = null;
8 public $right = null;
9 }
10
11 #查找操作
12 function search($root, $k) {
13 $cnode = $root;
14 while ($cnode != null) {
15 if ($cnode->key == $K) {
16 return $cnode;
17 } else if ($cnode->key > $k) {
18 $cnode = $cnode->left;
19 } else {
20 $cnode = $cnode->right;
21 }
22 }
23
24 return $cnode;
25 }
26
27 #查找最小关键字
28 function search_minimum($root) {
29 $cnode = $root;
30 while ($cnode->left != null) {
31 $cnode = $cnode->left;
32 }
33 return $cnode;
34 }
35
36 #查找最大关键字
37 function search_maximum($root) {
38 $cnode = $root;
39 while ($cnode->right != null) {
40 $cnode = $cnode->right;
41 }
42 return $cnode;
43 }
44
45 #查找中序遍历前驱节点
46 function predecessor($x) {
47 if ($x->left !== null) { #左子结点存在，直接返回左子结点的最右子节点
48 return search_maximum($x->left);
49 }
50 #否则查找其父节点，直到当前节点位于父节点的右边
51 $p = $x->parent;
52 while ($p !== null && $x == $p->left) { #如果x是p的左孩子，说明p是x的后继，我们需要找的是p是x的前驱
53 $x = $p;
54 $p = $p->parent;
55 }
56 return $p;
57 }
58
59 #查找中序遍历的后继结点
60 function successor($x) {
61 if ($x->right !== null) {
62 return search_minimum($x->right);
63 }
64 $p = $x->parent;
65 while ($p !== null && $x = $p->right) {
66 $x = $p;
67 $p = $p->parent;
68 }
69
70 return $p;
71 }
72
73 #插入结点
74 function insert($root, $inode) {
75 $cnode = $root;
76 $pnode = null;
77 while ($cnode !== null) { #为inode找到合适的插入位置
78 $pnode = $cnode;
79 if ($cnode->key > $inode->key) {
80 $cnode = $cnode->left;
81 } else {
82 $cnode = $cnode->right;
83 }
84 }
85
86 $inode->parent = $pnode;
87 if ($pnode === null) { #pnode == null,说明是空树
88 $root = $inode;
89 } else {
90 if ($pnode->key > $inode->key) {
91 $pnode->left = $inode;
92 } else {
93 $pnode->right = $inode;
94 }
95 }
96 // print_r($root);
97 // echo "<br>";
98 }
99
100 #删除结点
101 function delete($root, $dnode) {
102 if ($dnode-> left === null || $dnode->right === null) { #如果待删除结点无子节点或只有一个子节点，则c = dnode
103 $c = $dnode;
104 } else { #如果待删除结点有两个子节点，c置为dnode的直接后继，以待最后将待删除结点的值换为其后继的值
105 $c = successor($dnode);
106 }
107
108 if ($c->left !== null) {
109 $s = $c->left;
110 } else {
111 $s = $c->right;
112 }
113
114 if ($s !== null) { #将c的子节点的父母结点置为c的父母结点，此处c只可能有1个子节点，因为如果c有两个子节点，则c不可能是dnode的直接后继
115 $s->parent = $c->parent;
116 }
117
118 if ($c->parent === null) { #如果c的父母为空，说明c=dnode是根节点，删除根节点后直接将根节点置为根节点的子节点，此处dnode是根节点，且拥有两个子节点，则c是dnode的后继结点，c的父母就不会为空，就不会进入这个if
119 $root = $s;
120 } else if ($c == $c->parent->left) { #如果c是其父节点的左右子节点，则将c父母的左右子节点置为c的左右子节点
121 $c->parent->left = $s;
122 } else {
123 $c->parent->right = $s;
124 }
125
126 #如果c!=dnode，说明c是dnode的后继结点，交换c和dnode的key值
127 if ($c != $dnode) {
128 $dnode->key = $c->key;
129 }
130
131 #返回根节点
132 return $root;
133 }
134
135 #使用数组构造二叉查找树
136 function build_iterative_tree($arr) {
137 $root = new Node();
138 $root->key = $arr[0];
139 for ($i = 1; $i < count($arr); $i++) {
140 $new_node = new Node();
141 $new_node->key = $arr[$i];
142 insert($root, $new_node);
143 }
144 return $root;
145 }
146
147 #二叉查找树中序遍历
148 function inorder_traverse($root) {
149 if ($root->left !== null) {
150 inorder_traverse($root->left);
151 }
152
153 echo $root->key . " ";
154
155 if ($root->right !== null) {
156 inorder_traverse($root->right);
157 }
158 }
159
160 $arr = array(55, 1, 5, 9, 3, 4, 2, 2, 7, 8, 8, 0, 1);
161 $root = build_iterative_tree($arr);
162 inorder_traverse($root);
163 echo "<br>";
164 echo search_maximum($root)->key;
165 echo "<br>";
166 echo search_minimum($root)->key;
167 echo "<br>";
168 $inode = new Node();
169 $inode->key = 99;
170 insert($root, $inode);
171 inorder_traverse($root);
172 echo "<br>";
173 delete($root, $root);
174 inorder_traverse($root);
175 echo "<br>";
176 ?>
0 1 1 2 2 3 4 5 7 8 8 9 55
55
0
0 1 1 2 2 3 4 5 7 8 8 9 55 99
0 1 1 2 2 3 4 5 7 8 8 9 99