Binary tree question

sadas232341s

I make the program to show the leaves in BST, but how to show only nodes that have leaves as children?

int OnlyLeafNodes(Elem *t)
{
if(NULL == t) return 0;
if(NULL == t->left && NULL == t->right) cout << t->key << endl;
else return OnlyLeafNodes(t->left) + OnlyLeafNodes(t->right);
}

Here is the INPUT and OUTPUT that I use for test. It has to show 4, instead of 2 and 5. Because 4 is the node that has only leaves. http://img40.imageshack.us/img40/1421/treex.jpg

barneyman

something like this should do it

int OnlyLeafNodes(Elem *t, int currentDepth=0)
{
// if 'this' is null, return
if(!t)
return currentDepth;

// inc the depth because we represent another one
currentDepth++;

// ask each of the children, how deep they go, relative to me
int leftDepth=OnlyLeafNodes(t->left,currentDepth)-currentDepth);
int rightDepth=OnlyLeafNodes(t->right,currentDepth)-currentDepth);

// spots 1,1 | 1,0 | 0,1
if(max(leftDepth,rightDepth)==1)
	cout << t->key << endl;  

// and return the depth this node represents
return currentDepth;

}

I haven't compiled it, sorry, but the general idea is to find all children who only descend one past the currentDepth

sadas232341s

what is max

barneyman

sorry

#define max(a,b) a>b?a:b

sadas232341s

And how to call the function? I mean what has to be the second argument innerDepth. I call it with the tree and the Height as second argument and it gives me 4, 3, 1 as output. I need only 4.

sadas232341s

Yes I define my own Max function, but why the output is 4,3,1 and not only 4?

barneyman

i think the return should be

// and return the depth this node represents
return currentDepth+(maxDepth,rightdepth);

barneyman

call it with

OnlyLeafNodes(rootNode,0);

sadas232341s

maxDepth is? and why is it in brackets? Is it a function or something? i don' t know

sadas232341s

OK I think I did it it has to be

return currentDepth - leftDepth + rightDepth;

sadas232341s

Now If you can explain me how the whole function works...

barneyman

// and return the depth this node represents
return currentDepth+max(leftDepth,rightdepth)

barneyman

it works by only printing those nodes who have only one depth below them, no more