Difference between revisions of "All about Binary search tree"

From Hawk Wiki
Jump to: navigation, search
(=Deleting node)
(Some code of binary search tree)
Line 1: Line 1:
 
==Some code of binary search tree==
 
==Some code of binary search tree==
Tree insert<br>
+
===Tree insert===
 
Tree loop all<br>
 
Tree loop all<br>
 
Tree to linked list<br>
 
Tree to linked list<br>

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