Difference between revisions of "All about Binary search tree"
(→Binary tree depth) |
(→Binary tree depth) |
||
| Line 158: | Line 158: | ||
===Binary tree depth=== | ===Binary tree depth=== | ||
<code class="php"> | <code class="php"> | ||
| + | <pre> | ||
/////////////////////////////////////////////////////////////////////// | /////////////////////////////////////////////////////////////////////// | ||
// Get depth of a binary tree | // Get depth of a binary tree | ||
| Line 174: | Line 175: | ||
return (nLeft > nRight) ? (nLeft + 1) : (nRight + 1); | return (nLeft > nRight) ? (nLeft + 1) : (nRight + 1); | ||
} | } | ||
| + | </pre> | ||
</code> | </code> | ||
Revision as of 22:52, 3 April 2012
Contents
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:
";
outputTree($tree);
echo "
";
echo "Tree to Linked list output:
";
$list=null;
tree2List($tree,$list);
echo "
";
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
";
//case 1 (hard) right child has left child
if($tree->right!==null&&$tree->right->left!==null){
echo "case 1: right child has left child
";
$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
";
$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
";
if($tree->left!==null){
echo "case 3.a: Node has left child
";
$tree->val=$tree->left->val;
$tree->left=$tree->left->left;
}
else{
echo "case 3.b: Node has no child
";
$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);
}
