PHP – Binary Tree

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

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