A Binary Tree is a data structure composed of nodes, where each node contains a value and references to its left and right child nodes (if they exist). The left child node is smaller or equal in value to its parent, while the right child node is greater in value.
To implement a binary tree in PHP, you can define a class representing a node and another class representing the binary tree itself.
Let's start with the node class
class BinaryTreeNode {
public $value; // value stored in the node
public $left; // reference to the left child node
public $right; // reference to the right child node
public function __construct($value) {
$this->value = $value;
$this->left = null;
$this->right = null;
}
}
The BinaryTreeNode class has three properties: $value, $left, and $right. The constructor initializes the node with a given value and sets the left and right child nodes to null.
Now, let's define the BinaryTree class, which will manage the binary tree
class BinaryTree {
public $root; // reference to the root node
public function __construct() {
$this->root = null;
}
public function insert($value) {
if ($this->root === null) {
$this->root = new BinaryTreeNode($value);
} else {
$this->insertNode($value, $this->root);
}
}
private function insertNode($value, &$node) {
if ($node === null) {
$node = new BinaryTreeNode($value);
} else {
if ($value <= $node->value) {
$this->insertNode($value, $node->left);
} else {
$this->insertNode($value, $node->right);
}
}
}
}
The BinaryTree class has a single property, $root, which holds the reference to the root node. The constructor initializes it as null.
The insert($value) method allows you to insert a new value into the binary tree. If the tree is empty (root is null), it creates a new node and sets it as the root. Otherwise, it calls the insertNode($value, &$node) private method to recursively find the appropriate position to insert the new value.
The insertNode($value, &$node) method checks if the current node is null. If so, it creates a new node with the given value. Otherwise, it compares the value with the current node's value and decides whether to go left or right in the tree based on the comparison result. It recursively calls insertNode() on the appropriate child node until it finds a null spot to insert the new value.
Once the Binary Tree is implemented, you can define methods to search, delete or traverse nodes
class BinaryTree {
// ... previous code ...
public function search($value) {
return $this->searchNode($value, $this->root);
}
private function searchNode($value, $node) {
if ($node === null || $node->value === $value) {
return $node;
}
if ($value < $node->value) {
return $this->searchNode($value, $node->left);
} else {
return $this->searchNode($value, $node->right);
}
}
public function delete($value) {
$this->root = $this->deleteNode($value, $this->root);
}
private function deleteNode($value, $node) {
if ($node === null) {
return null;
}
if ($value < $node->value) {
$node->left = $this->deleteNode($value, $node->left);
} elseif ($value > $node->value) {
$node->right = $this->deleteNode($value, $node->right);
} else {
// Node to be deleted is found
if ($node->left === null && $node->right === null) {
// Case 1: Node has no children
$node = null;
} elseif ($node->left === null) {
// Case 2: Node has only right child
$node = $node->right;
} elseif ($node->right === null) {
// Case 3: Node has only left child
$node = $node->left;
} else {
// Case 4: Node has both left and right children
$minRightNode = $this->findMinNode($node->right);
$node->value = $minRightNode->value;
$node->right = $this->deleteNode($minRightNode->value, $node->right);
}
}
return $node;
}
private function findMinNode($node) {
while ($node->left !== null) {
$node = $node->left;
}
return $node;
}
public function traverseInOrder() {
$this->inOrderTraversal($this->root);
}
private function inOrderTraversal($node) {
if ($node !== null) {
$this->inOrderTraversal($node->left);
echo $node->value . " ";
$this->inOrderTraversal($node->right);
}
}
public function traversePreOrder() {
$this->preOrderTraversal($this->root);
}
private function preOrderTraversal($node) {
if ($node !== null) {
echo $node->value . " ";
$this->preOrderTraversal($node->left);
$this->preOrderTraversal($node->right);
}
}
public function traversePostOrder() {
$this->postOrderTraversal($this->root);
}
private function postOrderTraversal($node) {
if ($node !== null) {
$this->postOrderTraversal($node->left);
$this->postOrderTraversal($node->right);
echo $node->value . " ";
}
}
}
search($value): Performs a search for a given value in the binary tree and returns the corresponding node if found, or null otherwise.delete($value): Deletes the node containing the given value from the binary tree. It handles four cases: when the node has no children, when it has only a left child, when it has only a right child, and when it has both left and right children.findMinNode($node): Helper function to find the minimum value node in a subtree. It is used when deleting a node with two children.traverseInOrder(): Performs an in-order traversal of the binary tree and prints the values in ascending order.traversePreOrder(): Performs a pre-order traversal of the binary tree and prints the values.traversePostOrder(): Performs a post-order traversal of the binary tree and prints the values.
You can use these methods to perform various operations on the binary tree, such as searching for values, deleting nodes, or traversing the tree in different orders.