Location: PHPKode > scripts > Binary Tree > binary-tree/btree.class.php
<?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();
?>

Return current item: Binary Tree