@anush:
we should look at all descendants and ancestors. .. but u 'r looking at pars
In our structure we should have a parent pointer ..
and we should look at all our descendants --- takes O(n) time ..
correct me if I'm wrong ...
On Tue, Sep 20, 2011 at 10:54 AM, anshu mishra
explanation:
Node :
lock - that node is locked or not;
lockedDesc - number of descendents locked of that node
left, right,par as name sugest;
unLock():
when we unlock a node than all its ancestor has to decrease its lockedDesc
value by 1.
Lock():
when we lock a node than all its ancestor has to
Given an n-ary tree of resources arranged hierarchically. A process needs to
lock a resource node in order to use it. But a node cannot be locked if any
of its descendant or ancestor is locked. You are supposed to:
- write the structure of node
- write codes for
Islock()- returns true if a given
for simplicity i doing it for binary tree
struct node
{
bool lock;
int lockedDesc;
node *left, *right, *par;
};
bool Islock(node *cur)
{
return cur-bool;
}
void unLock(node *cur)
{
node *temp;
cur-lock = false;
temp = cur-par;
while (temp != NULL)
{
for simplicity i am doing it for binary tree (liittle modification)
struct node
{
bool lock;
int lockedDesc;
node *left, *right, *par;
};
bool Islock(node *cur)
{
return cur-bool;
}
void unLock(node *cur)
{
node *temp;
cur-lock = false;
temp = cur-par;