<?php
/***********************************************
* PHP Binary Tree Class / Object (Code)
* BTree Sort(Inorder Traversal) and Search
* © CK Leong "BasicA" <basica@k-designs.com.sg>
***********************************************
* Take Note that returned data would be such
* that Array elements start from index 1 and
* thats because the 0th element or the index
* is used in the Algorithm and thus the class
* constructor would automatically convert your
* Array to start from 1 moving all elements
* 1-step down. Therefore when you get the array
* from the class... remember to -1 to the
* returned index.
***********************************************
* BasicA
*/
class clsBinaryTree {
var $TArray;
var $numElem;
var $Elem;
var $RightPointer;
var $LeftPointer;
var $Counter;
var $SortedArray;
var $SearchTerm;
var $SearchIndex;
function clsBinaryTree(
$ArrayIn,
$cntElem = 0) {
$this->TArray = $ArrayIn;
//First Element must start from 1.
if ($ArrayIn[0] != "") {
for ($i = 1; $i < sizeof($ArrayIn) + 1; $i++) {
$NewArray[$i] = $ArrayIn[$i - 1];
}
$this->TArray = $NewArray;
} else {
$this->TArray = $ArrayIn;
}
$this->numElem = $cntElem;
$this->ConstructBinaryTree();
$this->GenerateSorted();
}
function ConstructBinaryTree() {
$MAX = $this->numElem;
for ($i = 1; $i <= $MAX; $i++) {
//global $Elem;
$this->Elem = $i;
$Root = 1;
$this->FollowPointer($Root);
}
}
function FollowPointer($Root) {
if ($this->TArray[$this->Elem] > $this->TArray[$Root]) {
if ($this->RightPointer[$Root] == 0) {
$this->RightPointer[$Root] = $this->Elem;
} else {
$this->FollowPointer($this->RightPointer[$Root]);
}
}
if ($this->TArray[$this->Elem] < $this->TArray[$Root]) {
if ($this->LeftPointer[$Root] == 0) {
$this->LeftPointer[$Root] = $this->Elem;
} else {
$this->FollowPointer($this->LeftPointer[$Root]);
}
}
}
function GenerateSorted() {
$this->Counter = 0;
$this->InOrder(1);
}
function InOrder($Root) {
if (intval($this->LeftPointer[$Root]) != 0) $this->InOrder(intval($this->LeftPointer[$Root]));
$this->Counter += 1;
$this->SortedArray[$this->Counter] = $this->TArray[$Root];
if (intval($this->RightPointer[$Root]) != 0) $this->InOrder(intval($this->RightPointer[$Root]));
}
function Search($InTerm) {
$this->SearchTerm = $InTerm;
$this->BTreeSearch(1);
return $this->SearchIndex;
}
function BTreeSearch($Root) {
if ($this->SearchTerm > $this->TArray[$Root]) {
if ($this->RightPointer[$Root] == 0) {
$this->SearchIndex = 0;
} else {
$this->BTreeSearch($this->RightPointer[$Root]);
}
}
if ($this->SearchTerm < $this->TArray[$Root]) {
if ($this->LeftPointer[$Root] == 0) {
$this->SearchIndex = 0;
} else {
$this->BTreeSearch($this->LeftPointer[$Root]);
}
}
if ($this->SearchTerm == $this->TArray[$Root]) {
$this->SearchIndex = $Root;
}
}
}
$temp[0] = "X";
$temp[1] = "A";
$temp[2] = "Zoo";
$temp[3] = "Programming";
$temp[4] = "BasicA";
print "<b>Original Array</b><br>";
/*Code to print the Array
* TO be remove in actual
*/
print $temp[0] . "<br>";
print $temp[1] . "<br>";
print $temp[2] . "<br>";
print $temp[3] . "<br>";
print $temp[4] . "<br><br>";
$Test = new clsBinaryTree($temp, 5);
print "<b>Pointers</b><br><b>Left:</b>";
/*Code to print the Left and Right Pointers
*TO be remove in actual
*/
for ($i = 1; $i <= 5; $i++) {
print intval($Test->LeftPointer[$i]);
}
print "<br><b>Right:</b>";
for ($i = 1; $i <= 5; $i++) {
print intval($Test->RightPointer[$i]);
}
print "<br><br><b>Sorted List.</b><br>";
/* Code to print the Sorted List
* TO be remove in actual
*/
for ($i = 1; $i <= 5; $i++) {
print $Test->SortedArray[$i] . "<br>";
}
print "<br><b>Search 'Zoo':</b> " . $Test->Search("Zoo");
?>
|
Download
