Difference between revisions of "All about Binary search tree"

Revision as of 22:51, 3 April 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:
"; 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);

}