设计一个算法求链接存储的二叉树中非叶结点的个数

[问答题]

设计一个算法求链接存储的二叉树中非叶结点的个数。结点类型为BinTreeNode，结点结构为（left，data，right），root为指向根结点的指针。要求：

（1）描述算法的基本设计思想；

（2）用算法描述语言描述算法；

（3）给出算法的时间复杂性分析。

code_laoq

（1）采用递归遍历的思想，这是很容易想到的，因为二叉树是递归定义的。当然也可以用栈实现非递归的算法，时间复杂度相同。在数据结构考试中如果未要求使用非递归算法，一般来说通过递归算法解决树的相关问题，因为递归算法更加直观和易于理解（对于人类而言）。

但是在实际开发中用递归可能会发生栈溢出的情况。

（2）使用C语言实现该算法

//计算度数为2的结点总数
int twoChildNodes(BiTree* root) {
    if (!root)
        return 0;
    if (root->left && root->right)
        return twoChildNodes(root->left) + twoChildNodes(root->right) + 1;
    else
        return twoChildNodes(root->left) + twoChildNodes(root->right);
}
//计算度数为1的结点总数
int oneChildNodes(BiTree* root) {
    if (!root)
        return 0;
    bool only_left = root->left && !root->right;
    bool only_right = root->right && !root->left;
    if (only_left)
        return 1 + oneChildNodes(root->left);
    else if (only_right)
        return 1 + oneChildNodes(root->right);
    else
        return oneChildNodes(root->left) + oneChildNodes(root->right);
}

（3）算法类似二叉树的遍历，递归实现的本质也是系统帮我们建立了栈结构，而系统栈需要记住每个节点的值，所以空间复杂度仍为O(N)。

T(N)=2T(N/2)+O(1):，其中 a = 2, b = 2, d = 0;

得到 log(2,2) = 1 > 0，代入Master公式得时间复杂度为O(N)