Ptypes\BinaryTree

Complexity

Total Complexity

60

Size/Duplication

Total Lines	319
Duplicated Lines	0 %

Importance

Changes

0

19 Methods

Rating	Name	Duplication	Size	Complexity
A	get_height()	0	3	1
A	validate_parameter()	0	10	3
A	search()	0	8	4
C	insert()	0	36	8
A	get_min()	0	7	2
A	get_level_recursive()	0	15	4
A	compare()	0	18	3
B	recursive_search()	0	20	5
A	in_order_traversal()	0	12	2
A	is_complete()	0	2	1
A	delete()	0	10	2
A	pre_order_traversal()	0	11	2
A	post_order_traversal()	0	11	2
A	get_level()	0	16	4
A	get_height_recursive()	0	17	3
B	delete_recursive()	0	36	6
A	level_order_traversal()	0	5	2
A	__construct()	0	3	1
B	traverse()	0	26	5

<?php

namespace Ptypes;

use Ptypes\TreeNode;
use Ptypes\Exceptions\UnexpectedType;
use Ptypes\Exceptions\InvalidArgument;

class BinaryTree
{
	public const IN_ORDER = 0;
	public const PRE_ORDER = 1;
	public const POST_ORDER = 2;
	public const LEVEL_ORDER = 3;
	
	public $root;
	
	public function __construct(&$root=null)
	{
		$this->root = $root;
	}
	
	public function insert($node) //$node is a treenode
	{
		$this->validate_parameter($node);
		
		if($this->root == null)
		{
			$this->root = $node;
			return $this;
		}
		
		$n = $this->root;
		while(1)
		{	
			if($node->value < $n->value)
			{
				if($n->left == null)
				{
					$n->left = $node;
					return $this;
				}
				
				$n = $n->left;
			}
			else if($node->value > $n->value)
			{
				if($n->right == null)
				{
					$n->right = $node;
					return $this;
				}
				
				$n = $n->right;
			}
			else if($node->value == $n->value) //node is already in the tree, we do not create duplicates!
			{
				return $this;
			}
		}
	}
	
	public function search($value)
	{
		if(gettype($value) != "integer" && gettype($value) != "int" && gettype($value) != "double")
		{
			throw new InvalidArgument("Expected a number, got: " . gettype($value) . " !\n");
		}
		
		return $this->recursive_search($value, $this->root);
	}
	
	private function recursive_search($value, $node)
	{
		if($node == null)
		{
			return null;
		}
		
		$eval = $value - $node->value;
		if($eval == 0)
		{
			return $node;
		}
		
		if($eval < 0)
		{
			return $this->recursive_search($value, $node->left);
		}
		else if($eval > 0)
		{
			return $this->recursive_search($value, $node->right);
		}
	}
	
	public function get_min($node)
	{
		while($node->left != null) //find left most leaf
		{
			$node = $node->left;
		}
		return $node;
	}
	
	public function compare($nodeA, $nodeB)
	{
		$this->validate_parameter($nodeA);
		$this->validate_parameter($nodeB);
		
		$eval = $nodeA->value - $nodeB->value;
		
		if($eval < 0)
		{
			return -1; //go left
		}
		
		if($eval > 0)
		{
			return 1; //go right
		}
		
		return 0; //equal
	}
	
	public function delete($value)
	{
		//check if value is in the tree
		$node = $this->search($value); //this function also handles type checking
		if($node != null)
		{
			$this->delete_recursive($this->root, $node->value);
		}
		
		return $this; //allows chaining
	}
	
	private function delete_recursive(&$parent, $value)
	{
		if($parent == null) 
		{
			return $parent;
		}
		
		if($value < $parent->value)
		{
			$parent->left = $this->delete_recursive($parent->left, $value);
		}
		else if($value > $parent->value)
		{
			$parent->right = $this->delete_recursive($parent->right, $value);
		}
		else
		{
			if($parent->left == null)
			{
				$temp = $parent->right;
				$parent = null;
				return $temp;
			}
			else if($parent->right == null)
			{
				$temp = $parent->left;
				$parent = null;
				return $temp;
			}
			
			$temp = $this->get_min($parent->right);
			$parent->value = $temp->value;
			$parent->right = $this->delete_recursive($parent->right, $temp->value);
		}
		
		return $parent;
	}
	
	public function is_complete()
	{
		//TODO
	}
	
	public function get_height()
	{
		return $this->get_height_recursive($this->root);
	}
	
	private function get_height_recursive($node)
	{
		if($node == null)
		{
			return 0;
		}
		
		$lHeight = $this->get_height_recursive($node->left);
		$rHeight = $this->get_height_recursive($node->right);
		
		if($lHeight > $rHeight)
		{
			return ($lHeight + 1);
		}
		else
		{
			return ($rHeight + 1);
		}
	}
	
	public function get_level($level)
	{
		if(gettype($level) != "integer" && gettype($level) != "int")
		{
			throw new InvalidArgument("Expected an int, got: " . gettype($level) . " !");
		}
		
		$h = $this->get_height();
		if($level > $h)
		{
			throw new InvalidArgument("Cannot get the level: " . $level . " as it is greater than the tree level of: " . $h . " !");
		}
		
		$results = array();
		$this->get_level_recursive($level, $this->root, $results);
		return $results;
	}
	
	private function get_level_recursive($level, $node=null, &$results) //it is important that reference to results stays a reference (php pointer) !
	{
		if($node == null)
		{
			return null;
		}
		
		if($level == 1)
		{
			array_push($results, $node);
		}
		else if($level > 1)
		{
			$this->get_level_recursive($level-1, $node->left, $results);
			$this->get_level_recursive($level-1, $node->right, $results);
		}
	}
	
	public function traverse($order)
	{
		switch($order)
		{
			case self::IN_ORDER:
				$results = array();
				$this->in_order_traversal($this->root, $results);
				return $results;
				
			case self::PRE_ORDER:
				$results = array();
				$this->pre_order_traversal($this->root, $results);
				return $results;
				
			case self::POST_ORDER:
				$results = array();
				$this->post_order_traversal($this->root, $results);
				return $results;
				
			case self::LEVEL_ORDER:
				$results =array();
				$this->level_order_traversal($results);
				return $results;
				
			default:
				throw new InvalidArgument("Invalid order: " . $order . "! Valid orders: IN_ORDER (BinaryTree::IN_ORDER), PRE_ORDER (BinaryTree::PRE_ORDER), POST_ORDER (BinaryTree::POST_ORDER) and LEVEL_ORDER (BinaryTree::LEVEL_ORDER).\n");
		}
	}
	
	private function in_order_traversal($node, &$results) //it is important that reference to results stays a reference (php pointer) !
	{
		if ($node == null)
		{
			return null;
		}
		
		$this->in_order_traversal($node->left, $results);
		
		array_push($results, $node->value);
		
		$this->in_order_traversal($node->right, $results);
	}
	
	private function pre_order_traversal($node, &$results) //it is important that reference to results stays a reference (php pointer) !
	{
		if ($node == null)
		{
			return null;
		}
		
		array_push($results, $node->value);
		
		$this->pre_order_traversal($node->left, $results);
		$this->pre_order_traversal($node->right, $results);
	}
	
	private function post_order_traversal($node, &$results) //it is important that reference to results stays a reference (php pointer) !
	{
		if ($node == null)
		{
			return null;
		}
		
		$this->post_order_traversal($node->left, $results);
		$this->post_order_traversal($node->right, $results);
		
		array_push($results, $node->value);
	}
	
	private function level_order_traversal(&$results)
	{
		for($i = 1; $i <= $this->get_height(); $i++)
		{
			$results[$i] = $this->get_level($i);
		}
	}
	
	private function validate_parameter($node)
	{
		if(gettype($node) != "object")
		{
			throw new UnexpectedType("Expected a Ptypes\TreeNode, got: " . gettype($node));
		}
		
		if(get_class($node) != "Ptypes\TreeNode")
		{
			throw new UnexpectedType("Expected a Ptypes\TreeNode, got: " . get_class($node));
		}
	}
}