标签归档:Binary Tree

二叉树及二叉排序树的PHP实现

二叉树及二叉排序树的PHP实现

最近一段时间在看很基础的数据结构,本来想把一些数据结构和算法用PHP实现
但是google搜索后,发现一个使用php实现的基本的数据结构和算法,二叉树、二叉搜索树、AVL树、B树、链表和常见排序、搜索算法等等都有实现,而且全部是使用面向对象来实现的,只能膜拜。

源码地址:http://www.brpreiss.com/books/opus11/public/Opus11-1.0.tar.gz
文档地址:http://www.brpreiss.com/books/opus11/

阅读后,将其中对于二叉树及二叉排序树的实现提取出来,代码如下:

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
 
<?php
/**
 * 二叉树的定义
 */
class BinaryTree {
    protected $key = NULL;      //  当前节点的值
    protected $left = NULL;     //  左子树
    protected $right = NULL;    //  右子树
 
    /**
     * 以指定的值构造二叉树,并指定左右子树
     *
     * @param mixed $key 节点的值.
     * @param mixed $left 左子树节点.
     * @param mixed $right 右子树节点.
     */
    public function __construct( $key = NULL, $left = NULL, $right = NULL) {
        $this->key = $key;
        if ($key === NULL) {
            $this->left = NULL;
            $this->right = NULL;
        }
        elseif ($left === NULL) {
            $this->left = new BinaryTree();
            $this->right = new BinaryTree();
        }
        else {
            $this->left = $left;
            $this->right = $right;
        }
    }
 
    /**
     * 析构方法.
     */
    public function __destruct() {
        $this->key = NULL;
        $this->left = NULL;
        $this->right = NULL;
    }
 
    /**
    * 清空二叉树.
    **/
    public function purge () {
        $this->key = NULL;
        $this->left = NULL;
        $this->right = NULL;
    }
 
    /**
     * 测试当前节点是否是叶节点.
     *
     * @return boolean 如果节点非空并且有两个空的子树时为真,否则为假.
     */
    public function isLeaf() {
        return !$this->isEmpty() &&
            $this->left->isEmpty() &&
            $this->right->isEmpty();
    }
 
    /**
     * 测试节点是否为空
     *
     * @return boolean 如果节点为空返回真,否则为假.
     */
    public function isEmpty() {
        return $this->key === NULL;
    }
 
    /**
     * Key getter.
     *
     * @return mixed 节点的值.
     */
    public function getKey() {
        if ($this->isEmpty()) {
            return false;
        }
        return $this->key;
    }
 
 
    /**
     * 给节点指定Key值,节点必须为空
     *
     * @param mixed $object 添加的Key值.
     */
    public function attachKey($obj) {
        if (!$this->isEmpty())
            return false;
        $this->key = $obj;
        $this->left = new BinaryTree();
        $this->right = new BinaryTree();
    }
 
    /**
     * 删除key值,使得节点为空.
     */
    public function detachKey() {
        if (!$this->isLeaf())
            return false;
        $result = $this->key;
        $this->key = NULL;
        $this->left = NULL;
        $this->right = NULL;
        return $result;
    }
 
    /**
     * 返回左子树
     *
     * @return object BinaryTree 当前节点的左子树.
     */
    public function getLeft() {
        if ($this->isEmpty())
            return false;
        return $this->left;
    }
 
    /**
     * 给当前结点添加左子树
     *
     * @param object BinaryTree $t 给当前节点添加的子树.
     */
    public function attachLeft(BinaryTree $t) {
        if ($this->isEmpty() || !$this->left->isEmpty())
            return false;
        $this->left = $t;
    }
 
    /**
     * 删除左子树
     *
     * @return object BinaryTree  返回删除的左子树.
     */
    public function detachLeft() {
        if ($this->isEmpty())
            return false;
        $result = $this->left;
        $this->left = new BinaryTree();
        return $result;
    }
 
    /**
     * 返回当前节点的右子树
     *
     * @return object BinaryTree 当前节点的右子树.
     */
    public function getRight() {
        if ($this->isEmpty())
            return false;
        return $this->right;
    }
 
    /**
     * 给当前节点添加右子树
     *
     * @param object BinaryTree $t 需要添加的右子树.
     */
    public function attachRight(BinaryTree $t) {
        if ($this->isEmpty() || !$this->right->isEmpty())
            return false;
        $this->right = $t;
    }
 
    /**
     * 删除右子树,并返回此右子树
     * @return object BinaryTree 删除的右子树.
     */
    public function detachRight() {
        if ($this->isEmpty ())
            return false;
        $result = $this->right;
        $this->right = new BinaryTree();
        return $result;
    }
 
    /**
     * 先序遍历
     */
    public function preorderTraversal() {
        if ($this->isEmpty()) {
            return ;
        }
        echo ' ', $this->getKey();
        $this->getLeft()->preorderTraversal();
        $this->getRight()->preorderTraversal();
    }
 
    /**
     * 中序遍历
     */
    public function inorderTraversal() {
        if ($this->isEmpty()) {
            return ;
        }
        $this->getLeft()->preorderTraversal();
        echo ' ', $this->getKey();
        $this->getRight()->preorderTraversal();
    }
 
    /**
     * 后序遍历
     */
    public function postorderTraversal() {
        if ($this->isEmpty()) {
            return ;
        }
        $this->getLeft()->preorderTraversal();
        $this->getRight()->preorderTraversal();
        echo ' ', $this->getKey();
    }
}
 
/**
 * 二叉排序树的PHP实现
 */
 
class BST extends BinaryTree {
  /**
     * 构造空的二叉排序树
     */
    public function __construct() {
        parent::__construct(NULL, NULL, NULL);
    }
 
    /**
     * 析构
     */
    public function __destruct() {
        parent::__destruct();
    }
 
    /**
     * 测试二叉排序树中是否包含参数所指定的值
     *
     * @param mixed $obj 查找的值.
     * @return boolean True 如果存在于二叉排序树中则返回真,否则为假期
     */
    public function contains($obj) {
        if ($this->isEmpty())
            return false;
        $diff = $this->compare($obj);
        if ($diff == 0) {
            return true;
        }elseif ($diff < 0)
            return $this->getLeft()->contains($obj);
        else
            return $this->getRight()->contains($obj);
    }
 
    /**
     * 查找二叉排序树中参数所指定的值的位置
     *
     * @param mixed $obj 查找的值.
     * @return boolean True 如果存在则返回包含此值的对象,否则为NULL
     */
    public function find($obj) {
        if ($this->isEmpty())
            return NULL;
        $diff = $this->compare($obj);
        if ($diff == 0)
            return $this->getKey();
        elseif ($diff < 0)
            return $this->getLeft()->find($obj);
        else
            return $this->getRight()->find($obj);
    }
 
    /**
     * 返回二叉排序树中的最小值
     * @return mixed 如果存在则返回最小值,否则返回NULL
     */
    public function findMin() {
        if ($this->isEmpty ())
            return NULL;
        elseif ($this->getLeft()->isEmpty())
            return $this->getKey();
        else
            return $this->getLeft()->findMin();
    }
 
    /**
     * 返回二叉排序树中的最大值
     * @return mixed 如果存在则返回最大值,否则返回NULL
     */
    public function findMax() {
        if ($this->isEmpty ())
            return NULL;
        elseif ($this->getRight()->isEmpty())
            return $this->getKey();
        else
            return $this->getRight()->findMax();
    }
 
    /**
     * 给二叉排序树插入指定值
     *
     * @param mixed $obj 需要插入的值.
     * 如果指定的值在树中存在,则返回错误
     */
    public function insert($obj) {
        if ($this->isEmpty()) {
            $this->attachKey($obj);
        } else {
            $diff = $this->compare($obj);
            if ($diff == 0)
                die('argu error');
            if ($diff < 0)
                $this->getLeft()->insert($obj);
            else
                $this->getRight()->insert($obj);
        }
        $this->balance();
    }
 
 
 /**
     * 从二叉排序树中删除指定的值
     *
     * @param mixed $obj 需要删除的值.
     */
    public function delete($obj) {
        if ($this->isEmpty ())
            die();
 
        $diff = $this->compare($obj);
        if ($diff == 0) {
            if (!$this->getLeft()->isEmpty()) {
                $max = $this->getLeft()->findMax();
                $this->key = $max;
                $this->getLeft()->delete($max);
            }
            elseif (!$this->getRight()->isEmpty()) {
                $min = $this->getRight()->findMin();
                $this->key = $min;
                $this->getRight()->delete($min);
            } else
                $this->detachKey();
        } else if ($diff < 0)
                $this->getLeft()->delete($obj);
            else
                $this->getRight()->delete($obj);
        $this->balance();
    }
 
    public function compare($obj) {
        return $obj - $this->getKey();
    }
 
    /**
     * Attaches the specified object as the key of this node.
     * The node must be initially empty.
     *
     * @param object IObject $obj The key to attach.
     * @exception IllegalOperationException If this node is not empty.
     */
    public function attachKey($obj) {
        if (!$this->isEmpty())
            return false;
        $this->key = $obj;
        $this->left = new BST();
        $this->right = new BST();
    }
 
    /**
     * Balances this node.
     * Does nothing in this class.
     */
    protected function balance () {}
 
 
    /**
     * Main program.
     *
     * @param array $args Command-line arguments.
     * @return integer Zero on success; non-zero on failure.
     */
    public static function main($args) {
        printf("BinarySearchTree main program.\n");
        $root = new BST();
        foreach ($args as $row) {
            $root->insert($row);
        }
        return $root;
    }
}
 
$root = BST::main(array(50, 3, 10, 5, 100, 56, 78));
echo $root->findMax();
$root->delete(100);
echo $root->findMax();

以上代码看了几遍,有些望尘莫及的感觉
差距很大,而且还是2005年写的
再次膜拜!
EOF