PHP Classes

File: btree.php

Recommend this page to a friend!
  Classes of BasicA   Binary Tree Algorithms   btree.php   Download  
File: btree.php
Role: ???
Content type: text/plain
Description: Binary Tree Object for Sorting and Searching of data :: The power of Binary trees does not just lie in the depths of the system!
Class: Binary Tree Algorithms
Author: By
Last change:
Date: 23 years ago
Size: 4,809 bytes
 

Contents

Class file image Download
<?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"); ?>