Difference between revisions of "Algorithm Problems"
From Hawk Wiki
(Created page with "==Binary search== <pre> def search_binary_tree(node, key): if node is None: return None # key not found if key < node.key: return search_binary_tree(...") |
(→Binary tree insert) |
||
| Line 23: | Line 23: | ||
InsertNode(treeNode->right, newNode); | InsertNode(treeNode->right, newNode); | ||
} | } | ||
| + | </pre> | ||
| + | ==Print linklist inversed== | ||
| + | <pre> | ||
| + | /////////////////////////////////////////////////////////////////////// | ||
| + | // 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); | ||
| + | } | ||
| + | } | ||
| + | </pre> | ||
| + | ==Inverse Array== | ||
| + | <pre> | ||
| + | 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] ; | ||
| + | </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> | ||
Revision as of 00:46, 22 February 2012
Contents
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);
