How can I get number of leaf nodes in binary tree

问题:

I have a practice question that I'm stumped on - to get the number of leaf nodes in a binary tree without using recursion. I've had a bit of a look around for ideas, I've seen some such as passing the nodes to a stack, but I don't see how to do it when there's multiple branches. Can anyone provide a pointer?

回答1:

NumberOfLeafNodes(root);
int NumberOfLeafNodes(NODE *p)
{
    NODE *nodestack[50];
    int top=-1;
    int count=0;
    if(p==NULL)
        return 0;
    nodestack[++top]=p;
    while(top!=-1)
    {
        p=nodestack[top--];
        while(p!=NULL)
        {
            if(p->leftchild==NULL && p->rightchild==NULL)
                count++;
            if(p->rightchild!=NULL)
                nodestack[++top]=p->rightchild;
            p=p->leftchild;      
        }
    }
return count;
}