|
1
|
|
|
<?php |
|
2
|
|
|
|
|
3
|
|
|
namespace DataStructures\Trees; |
|
4
|
|
|
|
|
5
|
|
|
use DataStructures\Trees\Interfaces\TreeInterface; |
|
6
|
|
|
|
|
7
|
|
|
abstract class BinaryTreeAbstract implements TreeInterface { |
|
8
|
|
|
protected $root; |
|
9
|
|
|
protected $size; |
|
10
|
|
|
|
|
11
|
|
|
public function empty() { |
|
12
|
|
|
return $this->root === null; |
|
13
|
|
|
} |
|
14
|
|
|
|
|
15
|
|
|
public function size() { |
|
16
|
|
|
return $this->size; |
|
17
|
|
|
} |
|
18
|
|
|
|
|
19
|
|
|
public function put($key, $data){} |
|
20
|
|
|
public function putOrUpdate($key, $data){} |
|
21
|
|
|
|
|
22
|
|
View Code Duplication |
public function get($key){ |
|
|
|
|
|
|
23
|
|
|
if($this->root === null) { |
|
24
|
|
|
return null; |
|
25
|
|
|
} |
|
26
|
|
|
|
|
27
|
|
|
if($this->root->key === $key) { |
|
28
|
|
|
return $this->root->data; |
|
29
|
|
|
} else { |
|
30
|
|
|
$node = $this->root; |
|
31
|
|
|
while($node !== null) { |
|
32
|
|
|
if($key < $node->left) { |
|
33
|
|
|
$node = $node->left; |
|
34
|
|
|
} else if($key > $node->right) { |
|
35
|
|
|
$node = $node->right; |
|
36
|
|
|
} else { |
|
37
|
|
|
return $node->data; |
|
38
|
|
|
} |
|
39
|
|
|
} |
|
40
|
|
|
} |
|
41
|
|
|
|
|
42
|
|
|
return null; |
|
43
|
|
|
} |
|
44
|
|
|
public function getRoot(){ |
|
45
|
|
|
return $this->root; |
|
46
|
|
|
} |
|
47
|
|
|
|
|
48
|
|
|
public function exists($key){ |
|
49
|
|
|
if($this->root === null) { |
|
50
|
|
|
return false; |
|
51
|
|
|
} |
|
52
|
|
|
|
|
53
|
|
|
if($this->root->key === $key) { |
|
54
|
|
|
return true; |
|
55
|
|
|
} else { |
|
56
|
|
|
$node = $this->root; |
|
57
|
|
|
while($node !== null) { |
|
58
|
|
|
if($key < $node->left) { |
|
59
|
|
|
$node = $node->left; |
|
60
|
|
|
} else if($key > $node->right) { |
|
61
|
|
|
$node = $node->right; |
|
62
|
|
|
} else { |
|
63
|
|
|
return true; |
|
64
|
|
|
} |
|
65
|
|
|
} |
|
66
|
|
|
} |
|
67
|
|
|
|
|
68
|
|
|
return false; |
|
69
|
|
|
} |
|
70
|
|
|
|
|
71
|
|
|
public function floor($key){} |
|
72
|
|
|
public function ceil($key){} |
|
73
|
|
|
public function min(){} |
|
74
|
|
|
public function max(){} |
|
75
|
|
|
public function deleteMin(){} |
|
76
|
|
|
public function deleteMax(){} |
|
77
|
|
|
public function delete($key){} |
|
78
|
|
|
public function count() {} |
|
79
|
|
|
|
|
80
|
|
View Code Duplication |
public function search($key) { |
|
|
|
|
|
|
81
|
|
|
if($this->root === null) { |
|
82
|
|
|
return null; |
|
83
|
|
|
} |
|
84
|
|
|
|
|
85
|
|
|
if($this->root->key === $key) { |
|
86
|
|
|
return $this->root->data; |
|
87
|
|
|
} else { |
|
88
|
|
|
$node = $this->root; |
|
89
|
|
|
while($node !== null) { |
|
90
|
|
|
if($key < $node->left) { |
|
91
|
|
|
$node = $node->left; |
|
92
|
|
|
} else if($key > $node->right) { |
|
93
|
|
|
$node = $node->right; |
|
94
|
|
|
} else { |
|
95
|
|
|
return $node->data; |
|
96
|
|
|
} |
|
97
|
|
|
} |
|
98
|
|
|
} |
|
99
|
|
|
|
|
100
|
|
|
return null; |
|
101
|
|
|
} |
|
102
|
|
|
|
|
103
|
|
|
public function isLeaf($node) { // BinaryTreeNode |
|
104
|
|
|
return ($node !== null && $node->left === null && $node->right === null); |
|
105
|
|
|
} |
|
106
|
|
|
|
|
107
|
|
|
public function isRoot($node) { |
|
108
|
|
|
return $node !== null && $node->parent === null; |
|
109
|
|
|
} |
|
110
|
|
|
} |
SiroDiaz /
DataStructures
Loading history...
Duplicated code is one of the most pungent code smells. If you need to duplicate the same code in three or more different places, we strongly encourage you to look into extracting the code into a single class or operation.
You can also find more detailed suggestions in the “Code” section of your repository.