A simple implementation of binary search tree in PHP.
<?php /** * Binary Search Tree * A simple bst implementation in PHP * @author J Wolfe <odwolfe@yahoo.com> */ /** * Class Node */ class Node { public $left = null; public $right = null; public $data = null; public function __construct($data) { $this->data = $data; } // Actually this method isn't working in this context. // If anyone knows how to get this work, please email me. public function __toString() { return $this->data; } } /** * Class BST * Basic binary search tree functionality */ class BST { /** * Root of the tree * @var null */ public $root = null; /** * Insert a node order based * @param $data */ public function insertNode($data) { $node = new Node($data); if (is_null($this->root)) { $this->root = $node; } else { $c_node =& $this->root; while (!is_null($c_node)) { if ($c_node->data > $data) { $c_node =& $c_node->left; } // NOTE:: the following condition creates empty nodes // if ($c_node->data < $data) { else { $c_node =& $c_node->right; } } $c_node = $node; } } /** * Search a node by a data * @param $data * @return Node */ public function searchNode($data) { $c_node = $this->root; while (!is_null($c_node)) { if ($c_node->data == $data) { break; } else { if ($c_node->data > $data) { $c_node = $c_node->left; } else { $c_node = $c_node->right; } } } return $c_node; } /** * Find a node that holds the minimum data * @param $c_node Node * @return Node */ public function &findMinNode($c_node) { $p_node = $c_node; while (!is_null($c_node->left)) { $p_node = $c_node; $c_node = $c_node->left; } return $p_node; } /** * Delete a node * The best resource I've found for node deletion logic: * http://www.algolist.net/Data_structures/Binary_search_tree/Removal * * TODO:: Delete orphans after a deletion occurs * @param $data */ public function deleteNode($data) { $c_node =& $this->root; while (!is_null($c_node)) { if ($c_node->data == $data) { // has both children if (!is_null($c_node->left) && !is_null($c_node->right) ) { // check right->left node to see if it is searchable if (!is_null($c_node->right->left)) { // get a parent node of a min node // in order to remove a child node $p_node =& $this->findMinNode($c_node->right); $c_node->data = $p_node->left->data; $p_node->left = null; } // if not, it just takes a right node else { $c_node->data = $c_node->right->data; $c_node->right = null; } } // has one left child elseif (!is_null($c_node->left)) { $c_node = $c_node->left; } // has one right child elseif (!is_null($c_node->right)) { $c_node = $c_node->right; } // no children else { $c_node = null; } break; } else { // loop for searching if ($c_node->data > $data) { $c_node =& $c_node->left; } else { $c_node =& $c_node->right; } } } } /** * Pre Order traverse * @param null $c_node */ public function dispPreOrder($c_node = null) { if (!is_null($c_node)) { echo $c_node->data . " "; $this->dispPreOrder($c_node->left); $this->dispPreOrder($c_node->right); } } /** * In Order traverse * @param null $c_node */ public function dispInOrder($c_node = null) { if (!is_null($c_node)) { $this->dispInOrder($c_node->left); echo $c_node->data . " "; $this->dispInOrder($c_node->right); } } /** * Post Order traverse * @param null $c_node */ public function dispPostOrder($c_node = null) { if (!is_null($c_node)) { $this->dispPostOrder($c_node->left); $this->dispPostOrder($c_node->right); echo $c_node->data . " "; } } } /* * Sample data and usage of the class */ // test elements $arr_test = array(23, 45, 16, 37, 3, 1, 99, 22); $bst = new BST(); // insert elements to a bst tree foreach ($arr_test as $val) { $bst->insertNode($val); } echo $bst->dispPreOrder($bst->root) . "<br/>"; echo $bst->dispInOrder($bst->root) . "<br/>"; echo $bst->dispPostOrder($bst->root) . "<br/>"; // search testing $t_node = $bst->searchNode(23); echo ($t_node ? $t_node->data . "is found!" : "Not found!") . "<br/>"; $t_node = $bst->searchNode(100); echo ($t_node ? $t_node->data . "is found!" : "Not found!") . "<br/>"; // check if deletion works $bst->deleteNode(23); echo $bst->dispInOrder($bst->root) . "<br/>";