Difference between revisions of "All about Binary search tree"

Revision as of 17:24, 28 February 2012

Some code of binary search tree

Tree insert

Tree loop all
Tree to linked list

<?php
class bTree{
public $val=null;
public $left=null;
public $right=null;
	function bTree($val0){
		$this->val=$val0;
	}
};
function insert(&$tree,$val){
	if($tree==null){
		$tree=new bTree($val);
	}
	else{
		if($val>$tree->val){
			insert($tree->right,$val);
		}
		else{
			insert($tree->left,$val);
		}
	}
}
function outputTree($tree){
	if($tree==null)
		return;
	outputTree($tree->left);
	echo $tree->val." ";
	outputTree($tree->right);
}
$currentNode=null;
function tree2List(&$tree,&$list=null){
	global $currentNode;
	if($tree===null)
		return;
	tree2List($tree->left,$list);
	if($list===null){
		$list=new bTree($tree->val); //create new | first left most element
	}
	else{
		$list->right=new bTree($tree->val);//only create new element on the left
		$list->right->left=$list;
		$list=$list->right;
	}
	echo $list->val." ";
	tree2List($tree->right,$list);
}

$tree=null;
insert($tree,10);
insert($tree,5);
insert($tree,2);
insert($tree,15);
insert($tree,20);
insert($tree,12);
echo "Tree output:<br />";
outputTree($tree);
echo "<br />";
echo "Tree to Linked list output:<br />";
$list=null;
tree2List($tree,$list);
echo "<br />";
echo "Link list (backwards after conversion): ";
while($list!==null){
	echo $list->val." ";
	$list=$list->left;
}

Deleting node

http://adtinfo.org/libavl.html/Deleting-from-a-BST.html