Difference between revisions of "Algorithm Problems"

Revision as of 00:46, 22 February 2012

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);
 }

Print linklist inversed

///////////////////////////////////////////////////////////////////////
// Print a list from end to beginning
// Input: pListHead - the head of list
///////////////////////////////////////////////////////////////////////
void PrintListReversely(ListNode* pListHead)
{
      if(pListHead != NULL)
      {
            // Print the next node first
            if (pListHead->m_pNext != NULL)
            {
                  PrintListReversely(pListHead->m_pNext);
            }
 
            // Print this node
            printf("%d", pListHead->m_nKey);
      }
}

Inverse Array

for (int i = 0; i < b; i=i++){
char temp1 = a[i];
a[i] = a[(b-1)-i];
a[(b-1)-i] = temp1;
cout << a[i] ;
}

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);