设计一个算法：统计一棵二叉树中所有叶结点的数目及非叶结点的数

[问答题]

设计一个算法：统计一棵二叉树中所有叶结点的数目及非叶结点的数目。

code_laoq

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

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

（2）使用C语言实现

//计算总结点个数
int nodeNums(BiTree* root) {
    if (!root)
        return 0;
    else
        return nodeNums(root->left) + nodeNums(root->right) + 1;
}
//计算度数为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);
}
//计算叶子结点个数
int leaves(BiTree* root) {
    if (!root)
        return 0;
    if (!root->left && !root->right)
        return 1;
    return leaves(root->left) + leaves(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(N^d)
log(b,a) > d	O(N^log(b,a))
log(b,a) = d	O((N^d) * logN)

发表于 2023-12-12 15:43:36 回复(0)

提交观点

问题信息

树

上传者：阿奻_

难度：

1条回答 1收藏 535浏览

设计一个算法：统计一棵二叉树中所有叶结点的数目及非叶结点的数

问题信息

热门推荐

相关试题