
平台论坛博客文库

› 论坛 › 程序设计 › PHP › php文档中心 › PHP实现平衡二叉树(AVL树)

PHP实现平衡二叉树(AVL树) [复制链接]

so_brave

家境小康

论坛徽章:: 0

电梯直达

1楼 [收藏(0)] [报告]

发表于 2011-11-21 16:24 |只看该作者 |倒序浏览

PHP实现平衡二叉树(AVL树)

Php代码

1.<?php
2. require 'bstOrder.php';
3.
4. $test = range(1, 10);
5. //$test = array(3,9,1,4,8,5,7,6,2,10);
6. $tree = new Bst($test, true);
7. //$tree->deleteNode('30');(非平衡树可删除,平衡树的没写删除操作)
8. print_r($tree->getTree());
9.?>
<?php
require 'bstOrder.php';
$test = range(1, 10);
//$test = array(3,9,1,4,8,5,7,6,2,10);
$tree = new Bst($test, true);
//$tree->deleteNode('30');(非平衡树可删除,平衡树的没写删除操作)
print_r($tree->getTree());
?>

复制代码

bstOrder.php

Php代码

1.<?php
2. /**
3. * PHP实现二叉排序树
4. * @author zhaojiangwei
5. * @since 2011/11/16 16:29
6. *
7. */
8.
9. class Node{
10. private $data;
11. private $left;
12. private $right;
13. private $bf;//平衡度
14.
15. public function Node($data = NULL, $bf = 0, $left = NULL, $right = NULL){
16. $this->data = $data;
17. $this->left = $left;
18. $this->right = $right;
19. $this->bf = $bf;
20. }
21.
22. public function getBf(){
23. return $this->bf;
24. }
25.
26. public function setBf($bf){
27. $this->bf = $bf;
28. }
29.
30. public function getData(){
31. return $this->data;
32. }
33.
34. public function setData($data){
35. $this->data = $data;
36. }
37.
38. public function &getLeft(){
39. return $this->left;
40. }
41.
42. public function &getRight(){
43. return $this->right;
44. }
45.
46. public function setLeft($left){
47. $this->left = $left;
48. }
49.
50. public function setRight($right){
51. $this->right = $right;
52. }
53. }
54.
55. class Bst{
56. private $head;//头结点
57. private $data;//初始输入的数据,为数组形式,如array('a','b');
58. private $tag;//查找时设置的前一结点(已无效,没用)
59.
60. //$bst:是否创建AVL树
61. public function Bst($data, $bst = FALSE){
62. $this->data = $data;
63. $this->head = NULL;
64.
65. if(!$bst){
66. $this->createBst();
67. }else{
68. $this->createBfBst();
69. }
70. }
71.
72. public function createBfBst(){
73. foreach($this->data as $value){
74. $this->insertBfNode($this->head, $value);
75. }
76. }
77.
78. private function insertBfNode(&$node, $value){
79. if($node == NULL){
80. $node = new Node($value, 0);
81. return TRUE;
82. }else{
83. if($node->getData() > $value){
84. if(!$this->insertBfNode($node->getLeft(), $value)){
85. return FALSE;
86. }
87.
88. switch($node->getBf()){
89. case 0:
90. $node->setBf(1);
91. return TRUE;
92. case 1:
93. $this->rightRotate($node);
94. return FALSE;
95. case -1:
96. $node->setBf(0);
97. return FALSE;
98. }
99. }elseif($node->getData() < $value){
100. if(!$this->insertBfNode($node->getRight(), $value)){
101. return FALSE;
102. }
103.
104. switch($node->getBf()){
105. case 0:
106. $node->setBf(-1);
107. return TRUE;
108. case 1:
109. $node->setBf(0);
110. return FALSE;
111. case -1:
112. $this->leftRotate($node);
113. return FALSE;
114. }
115. }else{
116. return FAlse;
117. }
118. }
119. }
120.
121. private function excuteLeft(&$node){
122. $temp = $node;
123. $node = $node->getRight();
124. $temp->setRight($node->getLeft());
125. $node->setLeft($temp);
126. }
127.
128. private function excuteRight(&$node){
129. $temp = $node;
130. $node = $node->getLeft();
131. $temp->setLeft($node->getRight());
132. $node->setRight($temp);
133. }
134.
135. private function leftRotate(&$node){
136. $right = &$node->getRight();
137. switch($right->getBf()){
138. case 1:
139. $left = &$right->getLeft();
140. switch($left->getBf()){
141. case -1:
142. $right->setBf(0);
143. $node->setBf(1);
144. break;
145. case 0:
146. $right->setBf(0);
147. $node->setBf(0);
148. break;
149. case 1:
150. $right->setBf(-1);
151. $node->setBf(0);
152. break;
153. }
154.
155. $left->setBf(0);
156. $this->excuteRight($right);
157. $this->excuteLeft($node);
158. break;
159.
160. case -1:
161. $node->setBf(0);
162. $right->setBf(0);
163. $this->excuteLeft($node);
164. break;
165. }
166. }
167.
168. private function rightRotate(&$node){
169. $left = &$node->getLeft();
170. switch($left->getBf()){
171. case -1:
172. $right = &$left->getRight();
173. switch($right->getBf()){
174. case -1:
175. $left->setBf(1);
176. $node->setBf(0);
177. break;
178. case 0:
179. $left->setBf(0);
180. $node->setBf(0);
181. break;
182. case 1:
183. $left->setBf(0);
184. $node->setBf(-1);
185. break;
186. }
187.
188. $right->setBf(0);
189. $this->excuteLeft($left);
190. $this->excuteRight($node);
191. break;
192. case 1:
193. $node->setBf(0);
194. $left->setBf(0);
195. $this->excuteRight($node);
196. break;
197. }
198. }
199.
200. public function createBst(){
201. foreach($this->data as $value){
202. $this->insertNode($value);
203. }
204. }
205.
206. //$pre:如果找不到该结点,是否返回前值
207. public function &searchBst(& $node, $key, $pre = FALSE){
208. if($node == NULL){
209. if($pre){
210. return $this->tag;
211. }else{
212. return FALSE;
213. }
214. }
215.
216. if($key > $node->getData()){
217. $this->tag = $node;
218. return $this->searchBst($node->getRight(), $key, $pre);
219. }elseif($key < $node->getData()){
220. $this->tag = $node;
221. return $this->searchBst($node->getLeft(), $key, $pre);
222. }else{
223. return $node;
224. }
225. }
226.
227. public function insertNode($key){
228. if(!$this->head){
229. $this->head = new Node($key);
230. }else{
231. $pre = $this->searchBst($this->head, $key, TRUE);
232. $node = new Node($key);
233.
234. if($pre->getData() > $key){
235. $pre->setLeft($node);
236. }else{
237. $pre->setRight($node);
238. }
239. }
240. }
241.
242. public function deleteNode($key){
243. $node = &$this->searchBst($this->head, $key);
244.
245. if(!$node){
246. return FALSE;
247. }
248.
249. if($node->getLeft() == NULL){
250. $node = $node->getRight();
251. }elseif($node->getRight() == NULL){
252. $node = $node->getLeft();
253. }else{
254. $leftBig = &$this->searchLeftBig($node);
255. $node->setData($leftBig->getData());
256.
257. if($leftBig->getLeft()){
258. $leftBig = $leftBig->getLeft();
259. }
260. }
261. }
262.
263. private function &searchLeftBig(& $key){
264. $result = &$key->getLeft();
265.
266. while($result){
267. if($result->getRight() == NULL){
268. return $result;
269. }
270.
271. $result = &$result->getRight();
272. }
273. }
274.
275. public function getTree(){
276. return $this->head;
277. }
278. }
279.?>

复制代码

php

文库|博客

返回列表

Chinaunix › 论坛 › 程序设计 › PHP › php文档中心 › PHP实现平衡二叉树(AVL树)

PHP实现平衡二叉树(AVL树) [复制链接]

浏览过的版块