本文实例讲述了PHP实现绘制二叉树图形显示功能。分享给大家供大家参考，具体如下：
前言：
最近老师布置了一个作业：理解并实现平衡二叉树和红黑树，本来老师是说用C#写的，但是我学的C#基本都还给老师了，怎么办？那就用现在最熟悉的语言PHP来写吧！
有一个问题来了，书上在讲解树的时候基本上会给出形象的树形图。但是当我们自己试着实现某种树，在调试、输出的时候确只能以字符的形式顺序地输出。这给调试等方面带来了很大的不便。然后在各种百度之后，我发现利用PHP实现二叉树的图形显示的资源几乎是零！好吧，那我就自己个儿实现一个！
效果显示：
如果我是直接在这一步摆代码的话，估计大家会比较烦闷，那我就直接上结果吧，后面在补代码，先激发激发大家的阅读兴趣：
1、搜索二叉树：
2、平衡二叉树：
3、红黑树：
上代码：
我们给图片创建一个类吧，显得稍微的小高级：
image.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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
|
<?php
/**
* author:LSGOZJ
* description: 绘制二叉树图像
*/
class image
{
//树相关设置
//每层之间的间隔高度
private $level_high = 100;
//最底层叶子结点之间的宽度
private $leaf_width = 50;
//结点圆的半径
private $rad = 20;
//根节点离边框顶端距离
private $leave = 20;
//树（保存树对象的引用）
private $tree;
//树的层数
private $level;
//完全二叉树中最底层叶子结点数量（计算图像宽度时用到，论如何实现图片大小自适应）
private $maxCount;
//图像相关设置
//画布宽度
private $width;
//画布高度
private $height;
//画布背景颜色（RGB）
private $bg = array(
220, 220, 220
);
//节点颜色（搜索二叉树和平衡二叉树时用）
private $nodeColor = array(
255, 192, 203
);
//图像句柄
private $image;
/**
* 构造函数，类属性初始化
* @param $tree 传递一个树的对象
* @return null
*/
public function __construct($tree)
{
$this->tree = $tree;
$this->level = $this->getLevel();
$this->maxCount = $this->GetMaxCount($this->level);
$this->width = ($this->rad * 2 * $this->maxCount) + $this->maxCount * $this->leaf_width;
$this->height = $this->level * ($this->rad * 2) + $this->level_high * ($this->level - 1) + $this->leave;
//1.创建画布
$this->image = imagecreatetruecolor($this->width, $this->height); //新建一个真彩色图像，默认背景是黑色
//填充背景色
$bgcolor = imagecolorallocate($this->image, $this->bg[0], $this->bg[1], $this->bg[2]);
imagefill($this->image, 0, 0, $bgcolor);
}
/**
* 返回传进来的树对象对应的完全二叉树中最底层叶子结点数量
* @param $level 树的层数
* @return 结点数量
*/
function GetMaxCount($level)
{
return pow(2, $level - 1);
}
/**
* 获取树对象的层数
* @param null
* @return 树的层数
*/
function getLevel()
{
return $this->tree->Depth();
}
/**
* 显示二叉树图像
* @param null
* @return null
*/
public function show()
{
$this->draw($this->tree->root, 1, 0, 0);
header("Content-type:image/png");
imagepng($this->image);
imagedestroy($this->image);
}
/**
* （递归）画出二叉树的树状结构
* @param $root，根节点（树或子树） $i，该根节点所处的层 $p_x，父节点的x坐标 $p_y,父节点的y坐标
* @return null
*/
private function draw($root, $i, $p_x, $p_y)
{
if ($i <= $this->level) {
//当前节点的y坐标
$root_y = $i * $this->rad + ($i - 1) * $this->level_high;
//当前节点的x坐标
if (!is_null($parent = $root->parent)) {
if ($root == $parent->left) {
$root_x = $p_x - $this->width / (pow(2, $i));
} else {
$root_x = $p_x + $this->width / (pow(2, $i));
}
} else {
//根节点
$root_x = (1 / 2) * $this->width;
$root_y += $this->leave;
}
//画结点（确定所画节点的类型（平衡、红黑、排序）和方法）
$method = 'draw' . get_class($this->tree) . 'Node';
$this->$method($root_x, $root_y, $root);
//将当前节点和父节点连线（黑色线）
$black = imagecolorallocate($this->image, 0, 0, 0);
if (!is_null($parent = $root->parent)) {
imageline($this->image, $p_x, $p_y, $root_x, $root_y, $black);
}
//画左子节点
if (!is_null($root->left)) {
$this->draw($root->left, $i + 1, $root_x, $root_y);
}
//画右子节点
if (!is_null($root->right)) {
$this->draw($root->right, $i + 1, $root_x, $root_y);
}
}
}
/**
* 画搜索二叉树结点
* @param $x，当前节点的x坐标 $y，当前节点的y坐标 $node，当前节点的引用
* @return null
*/
private function drawBstNode($x, $y, $node)
{
//节点圆的线颜色
$black = imagecolorallocate($this->image, 0, 0, 0);
$nodeColor = imagecolorallocate($this->image, $this->nodeColor[0], $this->nodeColor[1], $this->nodeColor[2]);
//画节点圆
imageellipse($this->image, $x, $y, $this->rad * 2, $this->rad * 2, $black);
//节点圆颜色填充
imagefill($this->image, $x, $y, $nodeColor);
//节点对应的数字
imagestring($this->image, 4, $x, $y, $node->key, $black);
}
/**
* 画平衡二叉树结点
* @param $x，当前节点的x坐标 $y，当前节点的y坐标 $node，当前节点的引用
* @return null
*/
private function drawAvlNode($x, $y, $node)
{
$black = imagecolorallocate($this->image, 0, 0, 0);
$nodeColor = imagecolorallocate($this->image, $this->nodeColor[0], $this->nodeColor[1], $this->nodeColor[2]);
imageellipse($this->image, $x, $y, $this->rad * 2, $this->rad * 2, $black);
imagefill($this->image, $x, $y, $nodeColor);
imagestring($this->image, 4, $x, $y, $node->key . '(' . $node->bf . ')', $black);
}
/**
* 画红黑树结点
* @param $x，当前节点的x坐标 $y，当前节点的y坐标 $node，当前节点的引用
* @return null
*/
private function drawRbtNode($x, $y, $node)
{
$black = imagecolorallocate($this->image, 0, 0, 0);
$gray = imagecolorallocate($this->image, 180, 180, 180);
$pink = imagecolorallocate($this->image, 255, 192, 203);
imageellipse($this->image, $x, $y, $this->rad * 2, $this->rad * 2, $black);
if ($node->IsRed == TRUE) {
imagefill($this->image, $x, $y, $pink);
} else {
imagefill($this->image, $x, $y, $gray);
}
imagestring($this->image, 4, $x, $y, $node->key, $black);
}
}
|
好，现在我们来看看在客户端如何调用：
client.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
|
class Client
{
public static function Main()
{
try {
//实现文件的自动加载
function autoload($class)
{
include strtolower($class) . '.php';
}
spl_autoload_register('autoload');
$arr = array(62, 88, 58, 47, 35, 73, 51, 99, 37, 93);
// $tree = new Bst(); //搜索二叉树
$tree = new Avl(); //平衡二叉树
// $tree = new Rbt(); //红黑树
$tree->init($arr); //树的初始化
// $tree->Delete(62);
// $tree->Insert(100);
// $tree->MidOrder(); //树的中序遍历（这也是调试的一个手段，看看数字是否从小到大排序）
$image = new image($tree);
$image->show(); //显示图像
} catch (Exception $e) {
echo $e->getMessage();
}
}
}
Client::Main();
|
这里用到的那三个树的类如下：
二叉搜索树bst.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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
|
<?php
/**
* author:zhongjin
* description: 二叉查找树
*/
//结点
class Node
{
public $key;
public $parent;
public $left;
public $right;
public function __construct($key)
{
$this->key = $key;
$this->parent = NULL;
$this->left = NULL;
$this->right = NULL;
}
}
//二叉搜索树
class Bst
{
public $root;
/**
* 初始化树结构
* @param $arr 初始化树结构的数组
* @return null
*/
public function init($arr)
{
$this->root = new Node($arr[0]);
for ($i = 1; $i < count($arr); $i++) {
$this->Insert($arr[$i]);
}
}
/**
* （对内）中序遍历
* @param $root （树或子树的）根节点
* @return null
*/
private function mid_order($root)
{
if ($root != NULL) {
$this->mid_order($root->left);
echo $root->key . " ";
$this->mid_order($root->right);
}
}
/**
* （对外）中序遍历
* @param null
* @return null
*/
public function MidOrder()
{
$this->mid_order($this->root);
}
/**
* 查找树中是否存在$key对应的节点
* @param $key 待搜索数字
* @return $key对应的节点
*/
function search($key)
{
$current = $this->root;
while ($current != NULL) {
if ($current->key == $key) {
return $current;
} elseif ($current->key > $key) {
$current = $current->left;
} else {
$current = $current->right;
}
}
return $current;
}
/**
* 查找树中的最小关键字
* @param $root 根节点
* @return 最小关键字对应的节点
*/
function search_min($root)
{
$current = $root;
while ($current->left != NULL) {
$current = $current->left;
}
return $current;
}
/**
* 查找树中的最大关键字
* @param $root 根节点
* @return 最大关键字对应的节点
*/
function search_max($root)
{
$current = $root;
while ($current->right != NULL) {
$current = $current->right;
}
return $current;
}
/**
* 查找某个$key在中序遍历时的直接前驱节点
* @param $x 待查找前驱节点的节点引用
* @return 前驱节点引用
*/
function predecessor($x)
{
//左子节点存在，直接返回左子节点的最右子节点
if ($x->left != NULL) {
return $this->search_max($x->left);
}
//否则查找其父节点，直到当前结点位于父节点的右边
$p = $x->parent;
//如果x是p的左孩子，说明p是x的后继，我们需要找的是p是x的前驱
while ($p != NULL && $x == $p->left) {
$x = $p;
$p = $p->parent;
}
return $p;
}
/**
* 查找某个$key在中序遍历时的直接后继节点
* @param $x 待查找后继节点的节点引用
* @return 后继节点引用
*/
function successor($x)
{
if ($x->right != NULL) {
return $this->search_min($x->right);
}
$p = $x->parent;
while ($p != NULL && $x == $p->right) {
$x = $p;
$p = $p->parent;
}
return $p;
}
/**
* 将$key插入树中
* @param $key 待插入树的数字
* @return null
*/
function Insert($key)
{
if (!is_null($this->search($key))) {
throw new Exception('结点' . $key . '已存在，不可插入！');
}
$root = $this->root;
$inode = new Node($key);
$current = $root;
$prenode = NULL;
//为$inode找到合适的插入位置
while ($current != NULL) {
$prenode = $current;
if ($current->key > $inode->key) {
$current = $current->left;
} else {
$current = $current->right;
}
}
$inode->parent = $prenode;
//如果$prenode == NULL， 则证明树是空树
if ($prenode == NULL) {
$this->root = $inode;
} else {
if ($inode->key < $prenode->key) {
$prenode->left = $inode;
} else {
$prenode->right = $inode;
}
}
//return $root;
}
/**
* 在树中删除$key对应的节点
* @param $key 待删除节点的数字
* @return null
*/
function Delete($key)
{
if (is_null($this->search($key))) {
throw new Exception('结点' . $key . "不存在，删除失败！");
}
$root = $this->root;
$dnode = $this->search($key);
if ($dnode->left == NULL || $dnode->right == NULL) { #如果待删除结点无子节点或只有一个子节点，则c = dnode
$c = $dnode;
} else { #如果待删除结点有两个子节点，c置为dnode的直接后继，以待最后将待删除结点的值换为其后继的值
$c = $this->successor($dnode);
}
//无论前面情况如何，到最后c只剩下一边子结点
if ($c->left != NULL) {
$s = $c->left;
} else {
$s = $c->right;
}
if ($s != NULL) { #将c的子节点的父母结点置为c的父母结点，此处c只可能有1个子节点，因为如果c有两个子节点，则c不可能是dnode的直接后继
$s->parent = $c->parent;
}
if ($c->parent == NULL) { #如果c的父母为空，说明c=dnode是根节点，删除根节点后直接将根节点置为根节点的子节点，此处dnode是根节点，且拥有两个子节点，则c是dnode的后继结点，c的父母就不会为空，就不会进入这个if
$this->root = $s;
} else if ($c == $c->parent->left) { #如果c是其父节点的左右子节点，则将c父母的左右子节点置为c的左右子节点
$c->parent->left = $s;
} else {
$c->parent->right = $s;
}
#如果c!=dnode，说明c是dnode的后继结点，交换c和dnode的key值
if ($c != $dnode) {
$dnode->key = $c->key;
}
#返回根节点
// return $root;
}
/**
* （对内）获取树的深度
* @param $root 根节点
* @return 树的深度
*/
private function getdepth($root)
{
if ($root == NULL) {
return 0;
}
$dl = $this->getdepth($root->left);
$dr = $this->getdepth($root->right);
return ($dl > $dr ? $dl : $dr) + 1;
}
/**
* （对外）获取树的深度
* @param null
* @return null
*/
public function Depth()
{
return $this->getdepth($this->root);
}
}
?>
|
平衡二叉树avl.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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
|
<?php
/**
* author:zhongjin
* description: 平衡二叉树
*/
//结点
class Node
{
public $key;
public $parent;
public $left;
public $right;
public $bf; //平衡因子
public function __construct($key)
{
$this->key = $key;
$this->parent = NULL;
$this->left = NULL;
$this->right = NULL;
$this->bf = 0;
}
}
//平衡二叉树
class Avl
{
public $root;
const LH = +1; //左高
const EH = 0; //等高
const RH = -1; //右高
/**
* 初始化树结构
* @param $arr 初始化树结构的数组
* @return null
*/
public function init($arr)
{
$this->root = new Node($arr[0]);
for ($i = 1; $i < count($arr); $i++) {
$this->Insert($arr[$i]);
}
}
/**
* （对内）中序遍历
* @param $root （树或子树的）根节点
* @return null
*/
private function mid_order($root)
{
if ($root != NULL) {
$this->mid_order($root->left);
echo $root->key . "-" . $root->bf . " ";
$this->mid_order($root->right);
}
}
/**
* （对外）中序遍历
* @param null
* @return null
*/
public function MidOrder()
{
$this->mid_order($this->root);
}
/**
* 将以$root为根节点的最小不平衡二叉树做右旋处理
* @param $root（树或子树）根节点
* @return null
*/
private function R_Rotate($root)
{
$L = $root->left;
if (!is_NULL($root->parent)) {
$P = $root->parent;
if ($root == $P->left) {
$P->left = $L;
} else {
$P->right = $L;
}
$L->parent = $P;
} else {
$L->parent = NULL;
}
$root->parent = $L;
$root->left = $L->right;
$L->right = $root;
//这句必须啊！
if ($L->parent == NULL) {
$this->root = $L;
}
}
/**
* 将以$root为根节点的最小不平衡二叉树做左旋处理
* @param $root（树或子树）根节点
* @return null
*/
private function L_Rotate($root)
{
$R = $root->right;
if (!is_NULL($root->parent)) {
$P = $root->parent;
if ($root == $P->left) {
$P->left = $R;
} else {
$P->right = $R;
}
$R->parent = $P;
} else {
$R->parent = NULL;
}
$root->parent = $R;
$root->right = $R->left;
$R->left = $root;
//这句必须啊！
if ($R->parent == NULL) {
$this->root = $R;
}
}
/**
* 对以$root所指结点为根节点的二叉树作左平衡处理
* @param $root（树或子树）根节点
* @return null
*/
public function LeftBalance($root)
{
$L = $root->left;
$L_bf = $L->bf;
switch ($L_bf) {
//检查root的左子树的平衡度，并作相应的平衡处理
case self::LH: //新结点插入在root的左孩子的左子树上，要做单右旋处理
$root->bf = $L->bf = self::EH;
$this->R_Rotate($root);
break;
case self::RH: //新节点插入在root的左孩子的右子树上，要做双旋处理
$L_r = $L->right; //root左孩子的右子树根
$L_r_bf = $L_r->bf;
//修改root及其左孩子的平衡因子
switch ($L_r_bf) {
case self::LH:
$root->bf = self::RH;
$L->bf = self::EH;
break;
case self::EH:
$root->bf = $L->bf = self::EH;
break;
case self::RH:
$root->bf = self::EH;
$L->bf = self::LH;
break;
}
$L_r->bf = self::EH;
//对root的左子树作左平衡处理
$this->L_Rotate($L);
//对root作右平衡处理
$this->R_Rotate($root);
}
}
/**
* 对以$root所指结点为根节点的二叉树作右平衡处理
* @param $root（树或子树）根节点
* @return null
*/
public function RightBalance($root)
{
$R = $root->right;
$R_bf = $R->bf;
switch ($R_bf) {
//检查root的右子树的平衡度，并作相应的平衡处理
case self::RH: //新结点插入在root的右孩子的右子树上，要做单左旋处理
$root->bf = $R->bf = self::EH;
$this->L_Rotate($root);
break;
case self::LH: //新节点插入在root的右孩子的左子树上，要做双旋处理
$R_l = $R->left; //root右孩子的左子树根
$R_l_bf = $R_l->bf;
//修改root及其右孩子的平衡因子
switch ($R_l_bf) {
case self::RH:
$root->bf = self::LH;
$R->bf = self::EH;
break;
case self::EH:
$root->bf = $R->bf = self::EH;
break;
case self::LH:
$root->bf = self::EH;
$R->bf = self::RH;
break;
}
$R_l->bf = self::EH;
//对root的右子树作右平衡处理
$this->R_Rotate($R);
//对root作左平衡处理
$this->L_Rotate($root);
}
}
/**
* 查找树中是否存在$key对应的节点
* @param $key 待搜索数字
* @return $key对应的节点
*/
public function search($key)
{
$current = $this->root;
while ($current != NULL) {
if ($current->key == $key) {
return $current;
} elseif ($current->key > $key) {
$current = $current->left;
} else {
$current = $current->right;
}
}
return $current;
}
/**
* 查找树中的最小关键字
* @param $root 根节点
* @return 最小关键字对应的节点
*/
function search_min($root)
{
$current = $root;
while ($current->left != NULL) {
$current = $current->left;
}
return $current;
}
/**
* 查找树中的最大关键字
* @param $root 根节点
* @return 最大关键字对应的节点
*/
function search_max($root)
{
$current = $root;
while ($current->right != NULL) {
$current = $current->right;
}
return $current;
}
/**
* 查找某个$key在中序遍历时的直接前驱节点
* @param $x 待查找前驱节点的节点引用
* @return 前驱节点引用
*/
private function predecessor($x)
{
//左子节点存在，直接返回左子节点的最右子节点
if ($x->left != NULL) {
return $this->search_max($x->left);
}
//否则查找其父节点，直到当前结点位于父节点的右边
$p = $x->parent;
//如果x是p的左孩子，说明p是x的后继，我们需要找的是p是x的前驱
while ($p != NULL && $x == $p->left) {
$x = $p;
$p = $p->parent;
}
return $p;
}
/**
* 查找某个$key在中序遍历时的直接后继节点
* @param $x 待查找后继节点的节点引用
* @return 后继节点引用
*/
private function successor($x)
{
if ($x->left != NULL) {
return $this->search_min($x->right);
}
$p = $x->parent;
while ($p != NULL && $x == $p->right) {
$x = $p;
$p = $p->parent;
}
return $p;
}
/**
* （对内）插入结点，如果结点不存在则插入，失去平衡要做平衡处理
* @param $root 根节点 $key 待插入树的数字
* @return null
*/
private function insert_node(&$root, $key)
{
//找到了插入的位置，插入新节点
if (is_null($root)) {
$root = new Node($key);
//插入结点成功
return TRUE;
} else {
//在树中已经存在和$key相等的结点
if ($key == $root->key) {
//插入节点失败
return FALSE;
} //在root的左子树中继续搜索
elseif ($key < $root->key) {
//插入左子树失败
if (!($this->insert_node($root->left, $key))) {
//树未长高
return FALSE;
}
//成功插入,修改平衡因子
if (is_null($root->left->parent)) {
$root->left->parent = $root;
}
switch ($root->bf) {
//原来左右子树等高，现在左子树增高而树增高
case self::EH:
$root->bf = self::LH;
//树长高
return TRUE;
break;
//原来左子树比右子树高，需要做左平衡处理
case self::LH:
$this->LeftBalance($root);
//平衡后，树并未长高
return FALSE;
break;
//原来右子树比左子树高，现在左右子树等高
case self::RH:
$root->bf = self::EH;
//树并未长高
return FALSE;
break;
}
} //在root的右子树中继续搜索
else {
//插入右子树失败
if (!$this->insert_node($root->right, $key)) {
//树未长高
return FALSE;
}
//成功插入,修改平衡因子
if (is_null($root->right->parent)) {
$root->right->parent = $root;
}
switch ($root->bf) {
//原来左右子树等高，现在右子树增高而树增高
case self::EH:
$root->bf = self::RH;
//树长高
return TRUE;
break;
//原来左子树比右子树高，现在左右子树等高
case self::LH:
$root->bf = self::EH;
return FALSE;
break;
//原来右子树比左子树高，要做右平衡处理
case self::RH:
$this->RightBalance($root);
//树并未长高
return FALSE;
break;
}
}
}
}
/**
* （对外）将$key插入树中
* @param $key 待插入树的数字
* @return null
*/
public function Insert($key)
{
$this->insert_node($this->root, $key);
}
/**
* 获取待删除的节点（删除的最终节点）
* @param $key 待删除的数字
* @return 最终被删除的节点
*/
private function get_del_node($key)
{
$dnode = $this->search($key);
if ($dnode == NULL) {
throw new Exception("结点不存在！");
return;
}
if ($dnode->left == NULL || $dnode->right == NULL) { #如果待删除结点无子节点或只有一个子节点，则c = dnode
$c = $dnode;
} else { #如果待删除结点有两个子节点，c置为dnode的直接后继，以待最后将待删除结点的值换为其后继的值
$c = $this->successor($dnode);
}
$dnode->key = $c->key;
return $c;
}
/**
* （对内）删除指定节点，处理该结点往上结点的平衡因子
* @param $node 最终该被删除的节点
* @return null
*/
private function del_node($node)
{
if ($node == $this->root) {
$this->root = NULL;
return;
}
$current = $node;
//现在的node只有两种情况，要么只有一个子节点，要么没有子节点
$P = $current->parent;
//删除一个结点，第一个父节点的平衡都肯定会发生变化
$lower = TRUE;
while ($lower == TRUE && !is_null($P)) {
//待删除结点是左节点
if ($current == $P->left) {
if($current == $node){
if (!is_null($current->left)) {
$P->left = $current->left;
} else {
$P->left = $current->left;
}
}
$P_bf = $P->bf;
switch ($P_bf) {
case self::LH:
$P->bf = self::EH;
$lower = TRUE;
$current = $P;
$P = $current->parent;
break;
case self::EH:
$P->bf = self::RH;
$lower = FALSE;
break;
case self::RH:
$this->RightBalance($P);
$lower = TRUE;
$current = $P->parent;
$P = $current->parent;
break;
}
} //右结点
else {
if($current == $node){
if (!is_null($current->left)) {
$P->right = $current->left;
} else {
$P->right = $current->left;
}
}
$P_bf = $P->bf;
switch ($P_bf) {
case self::LH:
$this->LeftBalance($P);
$lower = TRUE;
$current = $P->parent;
$P = $current->parent;
break;
case self::EH:
$P->bf = self::LH;
$lower = FALSE;
break;
case self::RH:
$P->bf = self::LH;
$lower = TRUE;
$current = $P;
$P = $current->parent;
break;
}
}
}
}
/**
* （对外）删除指定节点
* @param $key 删除节点的key值
* @return null
*/
public function Delete($key)
{
$del_node = $this->get_del_node($key);
$this->del_node($del_node);
}
/**
* （对内）获取树的深度
* @param $root 根节点
* @return 树的深度
*/
private function getdepth($root)
{
if ($root == NULL) {
return 0;
}
$dl = $this->getdepth($root->left);
$dr = $this->getdepth($root->right);
return ($dl > $dr ? $dl : $dr) + 1;
}
/**
* （对外）获取树的深度
* @param null
* @return null
*/
public function Depth()
{
return $this->getdepth($this->root);
}
}
?>
|
红黑树rbt.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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
|
<?php
/**
* author:zhongjin
* description: 红黑树
*/
//结点
class Node
{
public $key;
public $parent;
public $left;
public $right;
public $IsRed; //分辨红节点或黑节点
public function __construct($key, $IsRed = TRUE)
{
$this->key = $key;
$this->parent = NULL;
$this->left = NULL;
$this->right = NULL;
//插入结点默认是红色
$this->IsRed = $IsRed;
}
}
//红黑树
class Rbt
{
public $root;
/**
* 初始化树结构
* @param $arr 初始化树结构的数组
* @return null
*/
public function init($arr)
{
//根节点必须是黑色
$this->root = new Node($arr[0], FALSE);
for ($i = 1; $i < count($arr); $i++) {
$this->Insert($arr[$i]);
}
}
/**
* （对内）中序遍历
* @param $root （树或子树的）根节点
* @return null
*/
private function mid_order($root)
{
if ($root != NULL) {
$this->mid_order($root->left);
echo $root->key . "-" . ($root->IsRed ? 'r' : 'b') . ' ';
$this->mid_order($root->right);
}
}
/**
* （对外）中序遍历
* @param null
* @return null
*/
public function MidOrder()
{
$this->mid_order($this->root);
}
/**
* 查找树中是否存在$key对应的节点
* @param $key 待搜索数字
* @return $key对应的节点
*/
function search($key)
{
$current = $this->root;
while ($current != NULL) {
if ($current->key == $key) {
return $current;
} elseif ($current->key > $key) {
$current = $current->left;
} else {
$current = $current->right;
}
}
//结点不存在
return $current;
}
/**
* 将以$root为根节点的最小不平衡二叉树做右旋处理
* @param $root（树或子树）根节点
* @return null
*/
private function R_Rotate($root)
{
$L = $root->left;
if (!is_null($root->parent)) {
$P = $root->parent;
if($root == $P->left){
$P->left = $L;
}else{
$P->right = $L;
}
$L->parent = $P;
} else {
$L->parent = NULL;
}
$root->parent = $L;
$root->left = $L->right;
$L->right = $root;
//这句必须啊！
if ($L->parent == NULL) {
$this->root = $L;
}
}
/**
* 将以$root为根节点的最小不平衡二叉树做左旋处理
* @param $root（树或子树）根节点
* @return null
*/
private function L_Rotate($root)
{
$R = $root->right;
if (!is_null($root->parent)) {
$P = $root->parent;
if($root == $P->right){
$P->right = $R;
}else{
$P->left = $R;
}
$R->parent = $P;
} else {
$R->parent = NULL;
}
$root->parent = $R;
$root->right = $R->left;
$R->left = $root;
//这句必须啊！
if ($R->parent == NULL) {
$this->root = $R;
}
}
/**
* 查找树中的最小关键字
* @param $root 根节点
* @return 最小关键字对应的节点
*/
function search_min($root)
{
$current = $root;
while ($current->left != NULL) {
$current = $current->left;
}
return $current;
}
/**
* 查找树中的最大关键字
* @param $root 根节点
* @return 最大关键字对应的节点
*/
function search_max($root)
{
$current = $root;
while ($current->right != NULL) {
$current = $current->right;
}
return $current;
}
/**
* 查找某个$key在中序遍历时的直接前驱节点
* @param $x 待查找前驱节点的节点引用
* @return 前驱节点引用
*/
function predecessor($x)
{
//左子节点存在，直接返回左子节点的最右子节点
if ($x->left != NULL) {
return $this->search_max($x->left);
}
//否则查找其父节点，直到当前结点位于父节点的右边
$p = $x->parent;
//如果x是p的左孩子，说明p是x的后继，我们需要找的是p是x的前驱
while ($p != NULL && $x == $p->left) {
$x = $p;
$p = $p->parent;
}
return $p;
}
/**
* 查找某个$key在中序遍历时的直接后继节点
* @param $x 待查找后继节点的节点引用
* @return 后继节点引用
*/
function successor($x)
{
if ($x->left != NULL) {
return $this->search_min($x->right);
}
$p = $x->parent;
while ($p != NULL && $x == $p->right) {
$x = $p;
$p = $p->parent;
}
return $p;
}
/**
* 将$key插入树中
* @param $key 待插入树的数字
* @return null
*/
public function Insert($key)
{
if (!is_null($this->search($key))) {
throw new Exception('结点' . $key . '已存在，不可插入！');
}
$root = $this->root;
$inode = new Node($key);
$current = $root;
$prenode = NULL;
//为$inode找到合适的插入位置
while ($current != NULL) {
$prenode = $current;
if ($current->key > $inode->key) {
$current = $current->left;
} else {
$current = $current->right;
}
}
$inode->parent = $prenode;
//如果$prenode == NULL， 则证明树是空树
if ($prenode == NULL) {
$this->root = $inode;
} else {
if ($inode->key < $prenode->key) {
$prenode->left = $inode;
} else {
$prenode->right = $inode;
}
}
//将它重新修正为一颗红黑树
$this->InsertFixUp($inode);
}
/**
* 对插入节点的位置及往上的位置进行颜色调整
* @param $inode 插入的节点
* @return null
*/
private function InsertFixUp($inode)
{
//情况一：需要调整条件，父节点存在且父节点的颜色是红色
while (($parent = $inode->parent) != NULL && $parent->IsRed == TRUE) {
//祖父结点：
$gparent = $parent->parent;
//如果父节点是祖父结点的左子结点，下面的else与此相反
if ($parent == $gparent->left) {
//叔叔结点
$uncle = $gparent->right;
//case1:叔叔结点也是红色
if ($uncle != NULL && $uncle->IsRed == TRUE) {
//将父节点和叔叔结点都涂黑，将祖父结点涂红
$parent->IsRed = FALSE;
$uncle->IsRed = FALSE;
$gparent->IsRed = TRUE;
//将新节点指向祖父节点（现在祖父结点变红，可以看作新节点存在）
$inode = $gparent;
//继续while循环，重新判断
continue; //经过这一步之后，组父节点作为新节点存在（跳到case2）
}
//case2:叔叔结点是黑色，且当前结点是右子节点
if ($inode == $parent->right) {
//以父节点作为旋转结点做左旋转处理
$this->L_Rotate($parent);
//在树中实际上已经转换，但是这里的变量的指向还没交换，
//将父节点和字节调换一下，为下面右旋做准备
$temp = $parent;
$parent = $inode;
$inode = $temp;
}
//case3:叔叔结点是黑色，而且当前结点是父节点的左子节点
$parent->IsRed = FALSE;
$gparent->IsRed = TRUE;
$this->R_Rotate($gparent);
} //如果父节点是祖父结点的右子结点，与上面完全相反
else {
//叔叔结点
$uncle = $gparent->left;
//case1:叔叔结点也是红色
if ($uncle != NULL && $uncle->IsRed == TRUE) {
//将父节点和叔叔结点都涂黑，将祖父结点涂红
$parent->IsRed = FALSE;
$uncle->IsRed = FALSE;
$gparent->IsRed = TRUE;
//将新节点指向祖父节点（现在祖父结点变红，可以看作新节点存在）
$inode = $gparent;
//继续while循环，重新判断
continue; //经过这一步之后，组父节点作为新节点存在（跳到case2）
}
//case2:叔叔结点是黑色，且当前结点是左子节点
if ($inode == $parent->left) {
//以父节点作为旋转结点做右旋转处理
$this->R_Rotate($parent);
//在树中实际上已经转换，但是这里的变量的指向还没交换，
//将父节点和字节调换一下，为下面右旋做准备
$temp = $parent;
$parent = $inode;
$inode = $temp;
}
//case3:叔叔结点是黑色，而且当前结点是父节点的右子节点
$parent->IsRed = FALSE;
$gparent->IsRed = TRUE;
$this->L_Rotate($gparent);
}
}
//情况二：原树是根节点（父节点为空），则只需将根节点涂黑
if ($inode == $this->root) {
$this->root->IsRed = FALSE;
return;
}
//情况三：插入节点的父节点是黑色，则什么也不用做
if ($inode->parent != NULL && $inode->parent->IsRed == FALSE) {
return;
}
}
/**
* （对外）删除指定节点
* @param $key 删除节点的key值
* @return null
*/
function Delete($key)
{
if (is_null($this->search($key))) {
throw new Exception('结点' . $key . "不存在，删除失败！");
}
$dnode = $this->search($key);
if ($dnode->left == NULL || $dnode->right == NULL) { #如果待删除结点无子节点或只有一个子节点，则c = dnode
$c = $dnode;
} else { #如果待删除结点有两个子节点，c置为dnode的直接后继，以待最后将待删除结点的值换为其后继的值
$c = $this->successor($dnode);
}
//为了后面颜色处理做准备
$parent = $c->parent;
//无论前面情况如何，到最后c只剩下一边子结点
if ($c->left != NULL) { //这里不会出现，除非选择的是删除结点的前驱
$s = $c->left;
} else {
$s = $c->right;
}
if ($s != NULL) { #将c的子节点的父母结点置为c的父母结点，此处c只可能有1个子节点，因为如果c有两个子节点，则c不可能是dnode的直接后继
$s->parent = $c->parent;
}
if ($c->parent == NULL) { #如果c的父母为空，说明c=dnode是根节点，删除根节点后直接将根节点置为根节点的子节点，此处dnode是根节点，且拥有两个子节点，则c是dnode的后继结点，c的父母就不会为空，就不会进入这个if
$this->root = $s;
} else if ($c == $c->parent->left) { #如果c是其父节点的左右子节点，则将c父母的左右子节点置为c的左右子节点
$c->parent->left = $s;
} else {
$c->parent->right = $s;
}
$dnode->key = $c->key;
$node = $s;
//c的结点颜色是黑色，那么会影响路径上的黑色结点的数量，必须进行调整
if ($c->IsRed == FALSE) {
$this->DeleteFixUp($node,$parent);
}
}
/**
* 删除节点后对接点周围的其他节点进行调整
* @param $key 删除节点的子节点和父节点
* @return null
*/
private function DeleteFixUp($node,$parent)
{
//如果待删结点的子节点为红色，直接将子节点涂黑
if ($node != NULL && $node->IsRed == TRUE) {
$node->IsRed = FALSE;
return;
}
//如果是根节点，那就直接将根节点置为黑色即可
while (($node == NULL || $node->IsRed == FALSE) && ($node != $this->root)) {
//node是父节点的左子节点，下面else与这里相反
if ($node == $parent->left) {
$brother = $parent->right;
//case1:兄弟结点颜色是红色（父节点和兄弟孩子结点都是黑色）
//将父节点涂红，将兄弟结点涂黑，然后对父节点进行左旋处理（经过这一步，情况转换为兄弟结点颜色为黑色的情况）
if ($brother->IsRed == TRUE) {
$brother->IsRed = FALSE;
$parent->IsRed = TRUE;
$this->L_Rotate($parent);
//将情况转化为其他的情况
$brother = $parent->right; //在左旋处理后，$parent->right指向的是原来兄弟结点的左子节点
}
//以下是兄弟结点为黑色的情况
//case2:兄弟结点是黑色，且兄弟结点的两个子节点都是黑色
//将兄弟结点涂红，将当前结点指向其父节点，将其父节点指向当前结点的祖父结点。
if (($brother->left == NULL || $brother->left->IsRed == FALSE) && ($brother->right == NULL || $brother->right->IsRed == FALSE)) {
$brother->IsRed = TRUE;
$node = $parent;
$parent = $node->parent;
} else {
//case3:兄弟结点是黑色，兄弟结点的左子节点是红色，右子节点为黑色
//将兄弟结点涂红，将兄弟节点的左子节点涂黑，然后对兄弟结点做右旋处理（经过这一步，情况转换为兄弟结点颜色为黑色，右子节点为红色的情况）
if ($brother->right == NULL || $brother->right->IsRed == FALSE) {
$brother->IsRed = TRUE;
$brother->left->IsRed = FALSE;
$this->R_Rotate($brother);
//将情况转换为其他情况
$brother = $parent->right;
}
//case4:兄弟结点是黑色，且兄弟结点的右子节点为红色，左子节点为任意颜色
//将兄弟节点涂成父节点的颜色，再把父节点涂黑，将兄弟结点的右子节点涂黑，然后对父节点做左旋处理
$brother->IsRed = $parent->IsRed;
$parent->IsRed = FALSE;
$brother->right->IsRed = FALSE;
$this->L_Rotate($parent);
//到了第四种情况，已经是最基本的情况了，可以直接退出了
$node = $this->root;
break;
}
} //node是父节点的右子节点
else {
$brother = $parent->left;
//case1:兄弟结点颜色是红色（父节点和兄弟孩子结点都是黑色）
//将父节点涂红，将兄弟结点涂黑，然后对父节点进行右旋处理（经过这一步，情况转换为兄弟结点颜色为黑色的情况）
if ($brother->IsRed == TRUE) {
$brother->IsRed = FALSE;
$parent->IsRed = TRUE;
$this->R_Rotate($parent);
//将情况转化为其他的情况
$brother = $parent->left; //在右旋处理后，$parent->left指向的是原来兄弟结点的右子节点
}
//以下是兄弟结点为黑色的情况
//case2:兄弟结点是黑色，且兄弟结点的两个子节点都是黑色
//将兄弟结点涂红，将当前结点指向其父节点，将其父节点指向当前结点的祖父结点。
if (($brother->left == NULL || $brother->left->IsRed == FALSE) && ($brother->right == NULL || $brother->right->IsRed == FALSE)) {
$brother->IsRed = TRUE;
$node = $parent;
$parent = $node->parent;
} else {
//case3:兄弟结点是黑色，兄弟结点的右子节点是红色，左子节点为黑色
//将兄弟结点涂红，将兄弟节点的左子节点涂黑，然后对兄弟结点做左旋处理（经过这一步，情况转换为兄弟结点颜色为黑色，右子节点为红色的情况）
if ($brother->left == NULL || $brother->left->IsRed == FALSE) {
$brother->IsRed = TRUE;
$brother->right = FALSE;
$this->L_Rotate($brother);
//将情况转换为其他情况
$brother = $parent->left;
}
//case4:兄弟结点是黑色，且兄弟结点的左子节点为红色，右子节点为任意颜色
//将兄弟节点涂成父节点的颜色，再把父节点涂黑，将兄弟结点的右子节点涂黑，然后对父节点左左旋处理
$brother->IsRed = $parent->IsRed;
$parent->IsRed = FALSE;
$brother->left->IsRed = FALSE;
$this->R_Rotate($parent);
$node = $this->root;
break;
}
}
}
if ($node != NULL) {
$this->root->IsRed = FALSE;
}
}
/**
* （对内）获取树的深度
* @param $root 根节点
* @return 树的深度
*/
private function getdepth($root)
{
if ($root == NULL) {
return 0;
}
$dl = $this->getdepth($root->left);
$dr = $this->getdepth($root->right);
return ($dl > $dr ? $dl : $dr) + 1;
}
/**
* （对外）获取树的深度
* @param null
* @return null
*/
public function Depth()
{
return $this->getdepth($this->root);
}
}
?>
|
希望本文所述对大家PHP程序设计有所帮助。
原文链接：http://blog.csdn.net/baidu_30000217/article/details/52880578