Difference between revisions of "Algorithm Problems"
From Hawk Wiki
(→Inverse Array) |
|||
| Line 1: | Line 1: | ||
| − | ==Binary search== | + | ==Binary Tree== |
| + | ===Binary search=== | ||
<pre> | <pre> | ||
def search_binary_tree(node, key): | def search_binary_tree(node, key): | ||
| Line 11: | Line 12: | ||
return node.value # found key | return node.value # found key | ||
</pre> | </pre> | ||
| − | ==Binary tree insert== | + | ===Binary tree insert=== |
<pre> | <pre> | ||
/* Inserts the node pointed to by "newNode" into the subtree rooted at "treeNode" */ | /* Inserts the node pointed to by "newNode" into the subtree rooted at "treeNode" */ | ||
| Line 23: | Line 24: | ||
InsertNode(treeNode->right, newNode); | InsertNode(treeNode->right, newNode); | ||
} | } | ||
| + | </pre> | ||
| + | ===Binary tree depth=== | ||
| + | <pre> | ||
| + | /////////////////////////////////////////////////////////////////////// | ||
| + | // 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); | ||
</pre> | </pre> | ||
==Print linklist inversed== | ==Print linklist inversed== | ||
| Line 53: | Line 75: | ||
cout << a[i] ; | cout << a[i] ; | ||
} | } | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
</pre> | </pre> | ||
Revision as of 00:47, 22 February 2012
Contents
Binary 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);
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] ;
}
