Question about storing a maze board(like 2d array) into Tree.

I need to build the maze board(like 2d array) using a tree. But I find
that my buildTree function doesn't work. Could anyone give me some
hints on debugging it? Thanks

On Fri, 19 Nov 2004 18:57:02 -0800, Daniel wrote:

I need to build the maze board(like 2d array) using a tree. But I find
that my buildTree function doesn't work. Could anyone give me some
hints on debugging it? Thanks

I would personally black box test each function. When you find the
function with the error, white box test it.

Why don't you start by telling us exactly what the program is "supposed"
to do and exactly what "doesn't work".

Rob Gamble

"Robert Gamble" <rg*******@gmail.com> wrote in message
news:pa****************************@gmail.com...

On Fri, 19 Nov 2004 18:57:02 -0800, Daniel wrote:

> I need to build the maze board(like 2d array) using a tree. But I
> find that my buildTree function doesn't work. Could anyone give me
> some hints on debugging it? Thanks

I would personally black box test each function. When you find the
function with the error, white box test it.

I need to build the maze board(like 2d array) using a tree. But I find
that my buildTree function doesn't work. Could anyone give me some
How about a clue as to what kind of "doesn't work."
hints on debugging it? Thanks
The program is not that big. Did you use your degbugger to step
through it?

Your algorithm is flawed.

Let's set up some notation:
p{i} will be the local automatic variable p created for the i-th
recursion of BuildTree.
x{i}, and y{i} are the actual arguments passed to BuildTree on the
i-th recursion.

bool BuildTree(TreeNodePtr *T, int x, int y)
Hiding a pointer type inside a typedef or macro just leads to
confusion. Consider the standard macro FILE. Even though a user
never needs an object of type FILE but only pointers of type FILE*,
the language authors recognized the potential problems and did not
create the macro as FILEPTR.

On the call from main, x{0} and y{0} are both 0.
On the first recursive entry, x{1} is still 0 but y{1} is 1.
On the second recursive entry, x{2} is still 0 but y{2} is 2.
On the third recursive entry, x{3} is still 0 but y{3} is 3.
{ if (boardSize == 0) //boardSize is a global variable
{ return TRUE;
}
else
{
if (x > boardSize || y > boardSize)
Let's assume boardSize is 2 for discussion.

On the call from main, this is false.
On recursion 1, still false.
On recursion 2, still false.
On recursion 3, this is now true.
{ return FALSE;
Recursion 3 returns to recursion 2 at this point. Note that
p{2}->left was never updated.

}
else
{ TreeNodePtr p = (TreeNodePtr)malloc(sizeof(struct TreeNode));
You should test the return from malloc. You should not cast the
return at all.

p{0} contains the address of the allocated area.
p{1} contains the address of another allocated area.
p{2} contains the address of a third allocated area.
p->left = NULL;
p->right = NULL;
p->data.x = x;
p->data.y = y;
p->data.type = GetStepType(itemList, x, y); //GetStepType just
return a int

if (!BuildTree(&(p->left), x, y+1))//Build left tree
On the call from main, you initiate the first recursion here.
During recursion 1, you initiate the second recursion.
During recursion 2, you initiate the third recursion.

The third recursion returned false, so this is now true.

The second recursion returned false, so this is now true.

The first recursion returned false, so this is now true.
{ return FALSE;
Recursion 2 returns to recursion 1 at this point. Note that
p{1}->left was not updated. p{2} is destroyed (the variable itself,
not the memory it points to).

Recursion 1 returns to recursion 0 at this point. Note that
p{0}->left was not updated. p{1} is destroyed.

Recursion 0 returns to main at this point. Note that fullTree was not
updated. p{0} is destroyed.
}
if (!BuildTree(&(p->right), x+1, y)) //Build right tree
By now you should realize that this code is unreachable.
{ return FALSE;
}
*T = p;
}
}
return TRUE;
}

////////////////////////////////
// In the Main
///////////////////////////////
void main()
{ TreeNodePtr fullTree=(TreeNodePtr) malloc (sizeof (struct
TreeNode));

fullTree->data.x = 0;
fullTree->data.y = 0;
fullTree->data.type = 1;
fullTree->left = NULL;
fullTree->right = NULL;

BuildTree(&fullTree, 0, 0);
Why don't you test the return code? It would have told you there was
a problem.

Under normal (non-error) circumstances, BuildTree would have replaced
the value of fullTree, thereby creating a memory leak.

You now have three allocated areas of memory which you no longer have
pointers for, otherwise known as three memory leaks.

PrintTree(fullTree,0);
}