设计一个算法求链接存储的二叉树中非叶结点的个数。结点类型为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)

Master公式是常用来解决递归问题时间复杂度的通用公式。
公式可以直接记为:
T(N) = a*T(N / b) + O (Nd)
然后按照下表对应计算复杂度即可:

条件 时间复杂度
log(b,a) < d O(Nd)
log(b,a) > d O(Nlog(b,a))
log(b,a) = d O((Nd) * logN)

43:15

以上就是关于问题设计一个算法求链接存储的二叉树中非叶结点的个数。结点类型为BinTreeNode,结点结构为(left,data,right),root为指向根结点的指针。要求: (1)描述算法的基本设计思想; (2)用算法描述语言描述算法; (3)给出算法的时间复杂性分析。的答案

欢迎关注区块链毕设网-
专业区块链毕业设计成品源码,定制。

区块链NFT链游项目方科学家脚本开发培训

承接区块链项目定制开发

微信:btc9767

QQ :1330797917

TELEGRAM: BTCOK9

承接区块链项目定制开发


qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台-javagopython毕设 » 设计一个算法求链接存储的二叉树中非叶结点的个数。结点类型为BinTreeNode,结点结构为(left,data,right),root为指向根结点的指针。要求: (1)描述算法的基本设计思想; (2)用算法描述语言描述算法; (3)给出算法的时间复杂性分析。