笔记：武汉理工大学2015年计算机考研复试 算法笔试题解1

题目：非递归遍历二叉树求单孩子节点个数

分析：因为要非递归，所以需要用到栈来解决，使用前序遍历栈的方法来遍历，遍历时检测出栈的元素的孩子节点个数。

题解：

struct node//树的结点
{
    int val;
    node* left;
    node* right;
};

struct nodestack//放结点的栈
{
    int topid;
    node data[64];
};

int  function1(node root)
{
    int onechild=0;//记录单孩子结点的个数

    node tempNode = root;
    nodestack tempStack;
    tempStack.topid=-1;

    while(tempStack.topid!=-1||tempNode!=NULL)//按先序遍历
    {
        while(tempNode!=NULL)//沿着左依次压进栈，并输出根
        {
            cout<<tempNode.val;
            tempStack.topid++;
            tempStack.data[tempStack.topid] = tempNode;//压栈

            tempNode=tempNode.left;
        }
        node topNode = tempStack.data[tempStack.topid];//顶部出栈
        tempStack.topid--;

        if(topNode->left!=NULL&&topNode->right==NULL)//有左孩子没右孩子
            onechild++;
         if(topNode->left==NULL&&topNode->right!=NULL)//有右孩子没左孩子
            onechild++;

        tempNode = topNode->right;
    }
}