设计一个算法求链接存储的二叉树中非叶结点的个数。结点类型为BinTreeNode，结点结构为（left，data，right），root为指向根结点的指针。要求：（1）描述算法的基本设计思想；（2）用算法描述语言描述算法；（3）给出算法的时间复杂性分析。

区块链毕设网qklbishe.com为您提供问题的解答

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

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

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

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

（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)