Difference between revisions of "All about Binary search tree"

Revision as of 18:01, 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 right
		$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

 
function deleteNodeFromTree(&$tree,$val){
	if($tree===null)
	return;
	if($tree->val==$val){
		echo "Got this val in tree<br/>";
		//case 1 (hard) right child has left child
		
		if($tree->right!==null&&$tree->right->left!==null){
			echo "case 1: right child has left child<br />";
			$treetmp=&$tree->right->left;
			while($treetmp->left!=null){//find the right branch left most child. This value greater than this->val but smaller than all right branches
				$treetmp=&$treetmp->left;
			}
			$tree->val=$treetmp->val; //Replace(delete) this val
			$treetmp=null;//Delete that node left most node
		}
		//case 2 right child has no left node
		else if($tree->right!==null&&$tree->right->left===null){
			//replace the current val with the right one
			echo "case 2: right child has no left child<br />";
			$tree->val=$tree->right->val;
			$tree->right=$tree->right->right;
		}
		//case 3: no right child
		else if($tree->right===null){
			echo "case 3: no right child<br />";
			if($tree->left!==null){
				echo "case 3.a: Node has left child<br />";
				$tree->val=$tree->left->val;
				$tree->left=$tree->left->left;
			}
			else{
				echo "case 3.b: Node has no child<br />";
				$tree=null;
			}
		}
	}
	else if($val>$tree->val){
		deleteNodeFromTree($tree->right,$val);
	}
	else{
		deleteNodeFromTree($tree->left,$val);
	}
}
//create tree
$tree=null;
insert($tree,10);
insert($tree,5);
insert($tree,2);
insert($tree,15);
insert($tree,20);
insert($tree,12);
//delete from tree
var_dump($tree);
deleteNodeFromTree($tree,10);
var_dump($tree);

Binary search

def search_binary_tree(node, key):
     if node is None:
         return None  # key not found
     if key < node.key:
         return search_binary_tree(node.leftChild, key)
     elif key > node.key:
         return search_binary_tree(node.rightChild, key)
     else:  # key is equal to node key
         return node.value  # found key

Binary tree insert

 /* Inserts the node pointed to by "newNode" into the subtree rooted at "treeNode" */
 void InsertNode(Node* &treeNode, Node *newNode)
 {
     if (treeNode == NULL)
       treeNode = newNode;
     else if (newNode->key < treeNode->key)
       InsertNode(treeNode->left, newNode);
     else
       InsertNode(treeNode->right, newNode);
 }

Binary tree depth

///////////////////////////////////////////////////////////////////////
// Get depth of a binary tree
// Input: pTreeNode - the head of a binary tree
// Output: the depth of a binary tree
///////////////////////////////////////////////////////////////////////
int TreeDepth(SBinaryTreeNode *pTreeNode)
{
      // the depth of a empty tree is 0
      if(!pTreeNode)
            return 0;

      // the depth of left sub-tree
      int nLeft = TreeDepth(pTreeNode->m_pLeft);
      // the depth of right sub-tree
      int nRight = TreeDepth(pTreeNode->m_pRight);

      // depth is the binary tree
      return (nLeft > nRight) ? (nLeft + 1) : (nRight + 1);