#define N 32
class Node
{
Node *left,*right;
I64 n;
};
I64 n1,n2,common_ancestor;
Node *root;
#define X_SPACING 16
#define Y_SPACING 45
#define ARROW_SPACING 3
U0 ShowTree(CDC *dc,Node *tmpn,I64 *_node_x,I64 *_tree_x,I64 y)
{
I64 node_x;
if (tmpn) {
if (tmpn->left) {
ShowTree(dc,tmpn->left,&node_x,_tree_x,y+Y_SPACING);
dc->color=BLUE;
GrArrow3(dc,*_tree_x,y,0,
node_x+ARROW_SPACING,y+Y_SPACING-ARROW_SPACING,0);
}
if (tmpn->n==n1 || tmpn->n==n2) {
if (tmpn->n==common_ancestor)
dc->color=YELLOW;
else
dc->color=RED;
} else if (tmpn->n==common_ancestor)
dc->color=GREEN;
else
dc->color=BLUE;
*_node_x=*_tree_x;
GrPrint(dc,*_node_x,y,"%d",tmpn->n);
*_tree_x+=X_SPACING;
if (tmpn->right) {
ShowTree(dc,tmpn->right,&node_x,_tree_x,y+Y_SPACING);
dc->color=BLUE;
GrArrow3(dc,*_node_x,y,0,
node_x-ARROW_SPACING,y+Y_SPACING-ARROW_SPACING,0);
}
}
}
U0 DrawIt(CTask *,CDC *dc)
{
I64 node_x=0,tree_x=0;
ShowTree(dc,root,&node_x,&tree_x,20);
}
U0 TreeAdd(Node **_root,Node *tmpn)
{
Node *root=*_root;
if (!root)
*_root=tmpn;
else if (tmpn->n==root->n)
Free(tmpn);
else if (tmpn->n<root->n)
TreeAdd(&root->left,tmpn);
else
TreeAdd(&root->right,tmpn);
}
U0 TreeNew()
{
I64 i;
Node *tmpn;
for (i=0;i<N;i++) {
tmpn=CAlloc(sizeof(Node));
tmpn->n=RandU16%N;
if (i==N-1)
n1=tmpn->n;
else if (i==N-2)
n2=tmpn->n;
TreeAdd(&root,tmpn);
Sleep(50);
}
}
U0 TreeCommonAncestorFind(Node *root)
{
if (root && root->n!=n1 && root->n!=n2) {
common_ancestor=root->n;
if (n1<root->n && n2<root->n)
TreeCommonAncestorFind(root->left);
else if (n1>root->n && n2>root->n)
TreeCommonAncestorFind(root->right);
}
}
U0 TreeCommonAncestor()
{//Make tree and find common ancestor to n1 & n2.
root=NULL;
n1=n2=common_ancestor=0;
SettingsPush; //See SettingsPush
Fs->draw_it=&DrawIt;
DocClear;
"Scroll with {CTRL-Left Grab}.\n";
try {
TreeNew;
TreeCommonAncestorFind(root);
PressAKey;
} catch
PutExcept;
SettingsPop;
}
TreeCommonAncestor;
/*Be careful with recursive routines in TempleOS
because the stack does not grow and will overflow.
See /Demo/StkGrow.HC.
*/