Ran
BAN USERpublic void InorderSuccessor(TreeNode root, TreeNode parent)
{
if (root.Left != null)
{
InorderSuccessor(root.Left, parent);
TreeNode r = root.left;
while (r.Successor != null)
{
r = r.Successor;
}
r.successor = root;
}
else
{
if (parent != null)
parent.successor = root;
}
if (root.right != null)
{
InorderSuccessor(root.Right, root);
}
}
- Thread is finished, when no more words are there to print. So each worker thread has to wait for the synchronization object, once it acquires it can check if there is a word to print. If not then, it can signal next object and come out of the loop.
- Main thread will wait for worker threads to complete its tasks.(Join).
One possible solution:
- create 'm' synchronization primitives (say, AutoResetEvent), one for each thread
- call it, say, h1, h2, h3..hm
- Initially all the synchonization objects are set to non-signaled stae, except h1. So, Thread1 can print the first word.
- Each thread has to wait on one synchonization object. Ex: thread1 will always wait on h1.
- Just before exiting each thread has to perform this:
* Each thread will signal its immediate thread's synchronization object. Ex: Once thread1 completes its task, it signals h2. So the next thread can get the access
* It resets it own synchronization object. Ex: thread1 will reset h1 (if not AutoResetEvent)
- Hence, each thread should get 2 synchronization objects
* one object to wait on
* the next synchonization object to signal. Ex: Thread1 will get (h1 and h2), it waits on h1 and signals h2.
- Thread m will wait on hm, and once it completes printing it signals h1. So the first thread can gain the access.
- Each thread will pick the next word and print. Make this code thread safe(Ex: use monitor/ criticalsection)
//End user class
Class FileSearcher
{
//hashtable (targetfolder and indexer mapping)
private Dictionary<string, Indexer> indexers;
public string SearchText;
public string targetFolder;
//returns list of files which contains given SearchText
public List<string> Search(string searchText, string targetFolder)
{
if(!indexers.ContainsKey(targetFolder))
{
indexer = new Indexer();
foreach(file f in targetFolder)
{
ScanFile(f, indexer);
}
indexers.Add(targetFolder, indexer);
}
else
indexer = indexers[targetFolder];
return indexer.Search(searchText);
}
//this function scans the given file and builds the indexer for all the words
//contained in the file
private void ScanFile(string fileName, Indexer indexer)
{
foreach(string w in file)
{
indexer.AddWord(w);
}
}
}
class Indexer
{
//adds the given word to a trie,
//trie at the end can point to an index(fileID, wordPos) set
//if the word already exists, it just updates the index(fileID, wordPos) set
public void AddWord(string w);
//searches in the trie and returns list of files.
public List<string> Search(string text);
}
- We can keep a flag store/compare, so the space required is N
* for the first tree (flag is 'store') we can store the elements in an array
* for the second tree (flag is 'compare') we can just compare with the stored elements
- Yes, for Binary tree we can hash the values.
2 passes:
- Once to replace root when the root > left + right
- else to replace child node
void ReplaceRoot(TreeNode r)
{
if (r == null)
return;
ReplaceRoot(r.Left);
ReplaceRoot(r.Right);
int left = 0;
int right = 0;
if (r.Left != null)
left = r.Left.Data;
if (r.Right != null)
right = r.Right.Data;
if ((r.Data > (left + right)) && ((left > 0) || (right > 0)))
r.Data = left + right;
}
void ReplaceChild(TreeNode r)
{
if (r == null)
return;
int left = 0;
int right = 0;
if (r.Left != null)
left = r.Left.Data;
if (r.Right != null)
right = r.Right.Data;
if ((r.Data != (left + right)) && ((left > 0) || (right > 0)))
{
if (r.Right != null)
r.Right.Data = r.Data - left;
else if (r.Left != null)
r.Left.Data = - r.Data;
}
ReplaceChild(r.Left);
ReplaceChild(r.Right);
}
public static void Main()
{
ReplaceRoot(r);
ReplaceChild(r);
}
If both Inorder and Postorder sequence are provided, then one possible implementation:
int j= inorder.Count -1;
TreeNode ConstructNodes(List<Node> inorder, List<Node> postOrder)
{
int index = -1;
TreeNode n = new TreeNode();
n.Data = postOrder[j].Data;
//gets the index of the "postOrder[j].data" element in the inorder list.
index = getIndex(inorder, postOrder[j].Data);
inorder[index].Processed = true;
if ((index < inorder.Count -1) && (!inorder[index + 1].Processed))
{
j--;
n.Right = ConstructNodes(inorder, postOrder);
}
else
n.Right = null;
if ((index > 0) && (!inorder[index -1].Processed))
{
j--;
n.Left = ConstructNodes(inorder, postOrder);
}
else
n.Left = null;
return n;
}
I am not very clear on the question itself. Could anyone please elaborate more?
- Ran July 17, 2014