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

[Daniel]

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

bool BuildTree(TreeNodePtr *T, int x, int y)
{ if (boardSize == 0) //boardSize is a global variable
{ return TRUE;
}
else
{
if (x > boardSize || y > boardSize)
{ return FALSE;
}
else
{ TreeNodePtr p = (TreeNodePtr)malloc(sizeof(struct TreeNode));
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
{ return FALSE;
}
if (!BuildTree(&(p->right), x+1, y)) //Build right tree
{ 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);

PrintTree(fullTree,0);
}

 

[Robert Gamble]

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

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

Rob Gamble

 

[scott]

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

 

[Robert Gamble]

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

It looks like the OP has already found the function that doesn't work.
He is now looking for help with the "white box testing" in which case he
needs to explain what the function is supposed to do and what part isn't
working as expected.

Rob Gamble

 

[Barry Schwarz]

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);
}

This should have printed out the data from fullTree. Did it?


<<Remove the del for email>>