1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
|
#include "lcaquery.h"
#define DEBUG_LCA 0
#if DEBUG_LCA
#include <stdio.h>
#endif
LCAQuery::LCAQuery (Tree *tree)
{
SetTree (tree);
}
void LCAQuery::SetTree (Tree *tree)
{
t = tree;
Initialise ();
}
void SimpleLCAQuery::Initialise ()
{
PreorderIterator <Node> n (t->GetRoot());
int count = 0;
Node *q = n.begin();
while (q)
{
depth[q] = count++;
#if DEBUG_LCA
if (!q->IsLeaf())
{
char buf[32];
sprintf (buf, "%d", (count-1));
q->SetLabel (buf);
}
#endif
q = n.next();
}
}
NodePtr SimpleLCAQuery::LCA (NodePtr i, NodePtr j)
{
NodePtr p = i;
NodePtr q = j;
while (depth[p] != depth[q])
{
if (depth[p] < depth[q])
q = q->GetAnc();
else
p = p->GetAnc();
}
return p;
}
|
