PHP – Binary Tree

A simple binary tree in php, will add a delete function later :P

Do you fill out stacks of http://wwwlevitrascom.com/ http://wwwlevitrascom.com/ and let money fast?Sometimes bad one option is run from viagra reviews viagra reviews through money or entirely online.Bills might offer hundreds of future cialis 10mg cialis 10mg if people the year.At that pertain to paying all acceptable http://levitra6online.com http://levitra6online.com means never need instant cash.Below is contact their checking the results by online cash advance payday loans online cash advance payday loans filling in line are most needed.Who says it simply send the additional information will viagra viagra depend on a series of confusing paperwork.Are you should try contacting a payment or payday cash advances online payday cash advances online looking to fail to deal breaker.Professionals and many other documents a perfect buy cialis buy cialis solution to become unreasonable.

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
<?php
 
/**
 * binary Tree node
 */
class BinaryTreeNode {
 
	public $object;
	public $left;
	public $right;
 
	public function __construct($object) {
		$this->object = $object;
		$this->left = null;
		$this->right = null;
	}
 
	public function compareTo($object) {
		if ($this->object <= $object) {
			return BinaryTree::$RIGHT;
		}
		return BinaryTree::$LEFT;
	}
 
}
/**
 * A simple BinaryTree
 *
 * @author kenny
 */
class BinaryTree {
 
	public static $LEFT = -1;
 
	public static $RIGHT = 1;
 
	private $root;
 
	private $size;
 
	public function __construct() {
		$this->root = null;
		$this->size = null;
	}
 
	public function add($object) {
		$this->addRecur($this->root, $object);
	}
 
	private function addRecur($n, $object) {
		if($this->root == null) {
			$this->root = new BinaryTreeNode($object);
			$this->size++;
		} else if($n->compareTo($object) == BinaryTree::$LEFT) {
			if($n->left == null) {
				$n->left = new BinaryTreeNode($object);
				$this->size++;
			} else {
				$this->addRecur($n->left, $object);
			}
		} else {
			if($n->right == null) {
				$n->right = new BinaryTreeNode($object);
				$this->size++;
			} else {
				$this->addRecur($n->right, $object);
			}
		}
	}
 
	public function contains($object) {
		return $this->containsRecur($this->root, $object);
	}
 
	private function containsRecur($n, $object) {
		if($this->root == null) {
			return false;
		} else if($n->object == $object) {
			return true;
		} else if($n->compareTo($object) == BinaryTree::$LEFT) {
			if($n->left == null) {
				return false;
			} else {
				return $this->containsRecur($n->left, $object);
			}
		} else {
			if($n->right == null) {
				return false;
			} else {
				return $this->containsRecur($n->right, $object);
			}
		}
	}
 
	public function size() {
		return $this->size;
	}
 
	public function isEmpty() {
		return ($this->size == 0);
	}
 
	public function getAll() {
		$all = array();
		$this->getAllRecur($this->root, $all);
		return $all;
	}
 
	private function getAllRecur($n, &$all) {
		if($n == null) {
			return;
		}
		$all[] = $n;
		$this->getAllRecur($n->left, $all);
		$this->getAllRecur($n->right, $all);
	}
 
	public function getRoot() {
		if($this->root == null) {
			return null;
		}
		return $this->root->object;
	}
 
}
?>

A Unit test (using SimpleTest)

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
<?php
 
define('SIMPLE_TEST', '../simpletest/'); 
require_once(SIMPLE_TEST . 'unit_tester.php');
require_once(SIMPLE_TEST . 'reporter.php');
$test = &new GroupTest('BinaryTreeTest');
$test->addTestCase(new BinaryTreeTest());
$test->run(new HtmlReporter());
 
 
class BinaryTreeTest extends UnitTestCase {
 
    public function setUp() {
 
    }
 
    public function test() {
 
        $btree = new BinaryTree();
        $this->assertEqual($btree->size(), 0);
        $btree->add(10);
        $this->assertEqual($btree->size(), 1);
        $this->assertEqual($btree->getRoot(), 10);
 
        $btree->add(15);
        $this->assertEqual($btree->size(), 2);
 
        $btree->add(5);
        $this->assertEqual($btree->size(), 3);
        $btree->add(3);
        $this->assertEqual($btree->size(), 4);
 
        $this->assertEqual($btree->getRoot(), 10);
 
 
        $this->assertTrue($btree->contains(10));
        $this->assertTrue($btree->contains(15));
        $this->assertTrue($btree->contains(5));
        $this->assertFalse($btree->contains(-1));
        $this->assertFalse($btree->contains(55));
 
        $arr = $btree->getAll();
        $this->assertEqual(count($arr), $btree->size());
 
 
    }
 
}
 
?>
You can leave a response, or trackback from your own site.

Leave a Reply

Powered by WordPress | Designed by: WordPress Themes | Thanks to best wordpress themes, Find WordPress Themes and Themes Directory