<?php
/**
* @copyright Jonathon Blumenthal 2005
* @author Jonathon Blumenthal
* @license http://opensource.org/licenses/gpl-license.php
*
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License
* as published by the Free Software Foundation; either version 2
* of the License, or (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*/
// PHP Binary Tree Node
class Btree {
private $data;
private $left;
private $right;
/* constructor */
function Btree ($data, $left, $right) {
$this->data = $data;
$this->left = $left;
$this->right = $right;
}
/**
* Accessor method to get the data from this node.
* @return - the data from this node
**/
function getData( ) { return $this->data; }
/**
* Accessor method to get a reference to the left child of this node.
* @return - a reference to the left child of this node (or the null reference if there
* is no left child)
**/
function getLeft( ) { return $this->left; }
/**
* Accessor method to get a reference to the right child of this node.
* @return - a reference to the right child of this node (or the null reference if there
* is no left child)
**/
function getRight( ) { return $this->right; }
/**
* Accessor method to get the data from the leftmost node of the tree below this node.
* @return - the data from the deepest node that can be reached from this node by
* following left links.
**/
function getLeftmostData() {
if ($this->left == NULL)
return $this->data;
else
return $this->left->getLeftmostData( );
}
/**
* Accessor method to get the data from the rightmost node of the tree below this node.
* @return - the data from the deepest node that can be reached from this node by
* following left links.
**/
function getRightmostData() {
if ($this->right == NULL)
return $this->data;
else
return $this->right->getRightmostData( );
}
/**
* Accessor method to determine whether a node is a leaf.
* @return - true (if this node is a leaf) or false (if this node is not a leaf.
**/
function isLeaf( ) {
return ($this->left == NULL) && ($this->right == NULL);
}
/**
* Uses an inorder traversal to print the data from each node at or below
* this node of the binary tree.
* Postcondition:
* The data of this node and all its descendants have been writeen by
**/
function inorderPrint( ) {
if ($this->left != NULL)
$this->left->inorderPrint( );
echo $this->data;
if ($this->right != NULL)
$this->right->inorderPrint( );
}
/**
* Uses a preorder traversal to print the data from each node at or below
* this node of the binary tree.
* Postcondition:
* The data of this node and all its descendants have been writen by preorder traversal.
**/
function preorderPrint( ) {
echo $this->data;
if ($this->left != NULL)
$this->left->preorderPrint( );
if ($this->right != NULL)
$this->right->preorderPrint( );
}
/**
* Uses a preorder traversal to print the data from each node at or below
* this node of the binary tree.
* Postcondition:
* The data of this node and all its descendants have been writen by postorder traversal.
**/
function postorderPrint( ) {
if ($this->left != NULL)
$this->left->postorderPrint( );
if ($this->right != NULL)
$this->right->postorderPrint( );
echo $this->data;
}
/**
* Uses an preorder traversal to print the data from each node at or below
* this node of the binary tree, with indentations to indicate the depth
* of each node.
* @param depth - the depth of this node (with 0 for root, 1 for the root's children, and so on)
* Postcondition: The data of this node and all its descendants have been writeen by
* ECHO using an inorder traversal. The indentation of each line of data is four times
* its depth in the tree. A dash "--" is printed at any place where a child has no
* sibling.
**/
function treePrint($depth) {
// Print the indentation and the data from the current node:
for ($i = 1; $i <= $depth; $i++)
echo "....";
echo $this->data."<br>";
// Print the left subtree (or a dash if there is a right child and no left child)
if ($this->left != NULL)
$this->left->treePrint($depth+1);
elseif ($this->right != NULL) {
for ($i = 1; $i <= $depth+1; $i++)
echo "....";
echo "--<br>";
}
// Print the right subtree (or a dash if there is a left child and no left child)
if ($this->right != NULL)
$this->right->treePrint($depth+1);
elseif ($this->left != NULL) {
for ($i = 1; $i <= $depth+1; $i++)
echo "....";
echo "--<br>";
}
}
/**
* Modification method to set the data in this node.
* @param - newData the new data to place in this node
* Postcondition: The data of this node has been set to newData.
**/
function setData($newData) {
$this->data = $newData;
}
/**
* Modification method to set the link to the left child of this node.
* @param - newLeft
* a reference to the node that should appear as the left child of this node
* (or the null reference if there is no left child for this node)
* Postcondition:
* The link to the left child of this node has been set to newLeft.
* Any other node (that used to be the left child) is no longer connected to
* this node.
**/
function setLeft($newLeft) {
$this->left = $newLeft;
}
/**
* Modification method to set the link to the right child of this node.
* @param - newRight
* a reference to the node that should appear as the right child of this node
* (or the null reference if there is no right child for this node)
* Postcondition:
* The link to the right child of this node has been set to newRight.
* Any other node (that used to be the right child) is no longer connected to
* this node.
**/
function setRight($newRight) {
$this->right = $newRight;
}
/**
* Count the number of nodes in a binary tree.
* @param - root:
* a reference to the root of a binary tree (which may be
* an empty tree where source is null)
* @return - the number of nodes in the binary tree
**/
function treeSize() {
if ($this->left != NULL) $left_sum = $this->left->treeSize(); else $left_sum = 0;
if ($this->right != NULL) $right_sum = $this->right->treeSize(); else $right_sum = 0;
return 1 + $left_sum + $right_sum;
}
}
//PHP Binary Tree Demo
$node21 = new Btree(21, NULL, NULL);
$node20 = new Btree(20, NULL, NULL);
$node19 = new Btree(19, NULL, $node20);
$node18 = new Btree(18, NULL, NULL);
$node17 = new Btree(17, NULL, NULL);
$node16 = new Btree(16, NULL, NULL);
$node15 = new Btree(15, NULL, NULL);
$node14 = new Btree(14, $node16, $node17);
$node13 = new Btree(13, NULL, NULL);
$node12 = new Btree(12, $node18, NULL);
$node11 = new Btree(11, NULL, NULL);
$node10 = new Btree(10, NULL, NULL);
$node9 = new Btree(9, $node21, NULL);
$node8 = new Btree(8, NULL, $node19);
$node7 = new Btree(7, $node15, $node14);
$node6 = new Btree(6, $node13, $node12);
$node5 = new Btree(5, $node11, $node10);
$node4 = new Btree(4, $node9, $node8);
$node3 = new Btree(3, $node7, $node6);
$node2 = new Btree(2, $node5, $node4);
$Root = new Btree(1, $node3, $node2);
echo "Inorder Print: "; $Root->inorderPrint();
echo "<br><br>";
echo "Preorder Print: "; $Root->preorderPrint();
echo "<br><br>";
echo "Post Order Print: "; $Root->postorderPrint();
echo "<br><br>";
echo "Tree print: <br>"; $Root->treePrint(0);
echo "<br><br>";
echo "Left Most Leaf: ".$Root->getLeftmostData();
echo "<br><br>";
echo "Right Most Leaf: ".$Root->getRightmostData();
echo "<br><br>";
echo "Size of Tree: ".$Root->treeSize();
?>