计算二叉树的叶子结点数； 求二叉树的深度 。c++代码实现

好的，关于计算二叉树的叶子结点数，可以使用递归的方式进行实现。代码如下：

int countLeafNodes(TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    if (root->left == NULL && root->right == NULL) {
        return 1;
    }
    return countLeafNodes(root->left) + countLeafNodes(root->right);
}

关于求二叉树的深度，同样可以使用递归的方式实现。代码如下：

int getTreeDepth(TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    int leftDepth = getTreeDepth(root->left);
    int rightDepth = getTreeDepth(root->right);
    return (leftDepth > rightDepth) ? leftDepth + 1 : rightDepth + 1;
}

希望能对你有所帮助。

相关问题

用C++ 编写一个程序，实现二叉树的下列运算： 输入一个二叉树的先序序列，生成二叉树的二叉链表； 显示其先序、中序和后序遍历结果； 计算二叉树的叶子结点数； 求二叉树的深度 。

好的，我可以为您提供一个C++程序来实现这些操作。下面是代码：

#include <iostream>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class BinaryTree {
public:
    TreeNode* build_tree(vector<char>& preorder) {
        if (preorder.empty()) {
            return NULL;
        }
        char root_val = preorder[0];
        preorder.erase(preorder.begin());
        if (root_val == '#') {
            return NULL;
        }
        TreeNode* root = new TreeNode(root_val - '0');
        root->left = build_tree(preorder);
        root->right = build_tree(preorder);
        return root;
    }

    vector<int> preorder(TreeNode* root) {
        vector<int> res;
        if (!root) {
            return res;
        }
        res.push_back(root->val);
        vector<int> left = preorder(root->left);
        vector<int> right = preorder(root->right);
        res.insert(res.end(), left.begin(), left.end());
        res.insert(res.end(), right.begin(), right.end());
        return res;
    }

    vector<int> inorder(TreeNode* root) {
        vector<int> res;
        if (!root) {
            return res;
        }
        vector<int> left = inorder(root->left);
        res.insert(res.end(), left.begin(), left.end());
        res.push_back(root->val);
        vector<int> right = inorder(root->right);
        res.insert(res.end(), right.begin(), right.end());
        return res;
    }

    vector<int> postorder(TreeNode* root) {
        vector<int> res;
        if (!root) {
            return res;
        }
        vector<int> left = postorder(root->left);
        vector<int> right = postorder(root->right);
        res.insert(res.end(), left.begin(), left.end());
        res.insert(res.end(), right.begin(), right.end());
        res.push_back(root->val);
        return res;
    }

    int count_leaves(TreeNode* root) {
        if (!root) {
            return 0;
        }
        if (!root->left && !root->right) {
            return 1;
        }
        return count_leaves(root->left) + count_leaves(root->right);
    }

    int depth(TreeNode* root) {
        if (!root) {
            return 0;
        }
        int left_depth = depth(root->left);
        int right_depth = depth(root->right);
        return max(left_depth, right_depth) + 1;
    }
};

int main() {
    string preorder_str;
    cin >> preorder_str;
    vector<char> preorder(preorder_str.begin(), preorder_str.end());
    BinaryTree tree;
    TreeNode* root = tree.build_tree(preorder);
    cout << "先序遍历结果:";
    vector<int> res = tree.preorder(root);
    for (int i = 0; i < res.size(); i++) {
        cout << " " << res[i];
    }
    cout << endl;

    cout << "中序遍历结果:";
    res = tree.inorder(root);
    for (int i = 0; i < res.size(); i++) {
        cout << " " << res[i];
    }
    cout << endl;

    cout << "后序遍历结果:";
    res = tree.postorder(root);
    for (int i = 0; i < res.size(); i++) {
        cout << " " << res[i];
    }
    cout << endl;

    cout << "叶子结点数:" << tree.count_leaves(root) << endl;
    cout << "二叉树深度:" << tree.depth(root) << endl;

    return 0;
}

您可以将上述代码保存为一个.cpp文件，在终端中运行该文件，然后输入二叉树的先序遍历序列，程序将会输出先序、中序、后序遍历结果，叶子结点数和二叉树深度。

用C++使用二叉链表的存储结构，构造一棵二叉树，实现两个算法（利用递归调用）： （1） 求解二叉树的深度； （2） 求解二叉树叶子结点数；

在C++中，我们可以使用二叉链表来构建二叉树，每个节点包含一个值、指向左子节点的指针和指向右子节点的指针。为了实现这两个算法，首先需要定义一个二叉树节点的数据结构：

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

接下来我们分别实现求解二叉树深度和叶子节点数的递归函数：

1. **求解二叉树深度** (Tree Depth)

int maxDepth(TreeNode* root) {
    if (!root) return 0; // 空树深度为0
    else {
        int leftDepth = maxDepth(root->left); // 左子树深度
        int rightDepth = maxDepth(root->right); // 右子树深度
        return std::max(leftDepth, rightDepth) + 1; // 返回较大深度加1（根节点也算一层）
    }
}

2. **求解二叉树叶子结点数** (Number of Leaf Nodes)

int countLeafNodes(TreeNode* root) {
    if (!root) return 0; // 空树叶子节点数为0
    else if (!root->left && !root->right) // 如果左右都没有子节点，则是叶子节点
        return 1;
    else
        return countLeafNodes(root->left) + countLeafNodes(root->right);
}

以上就是在C++中使用二叉链表存储结构实现求解二叉树深度和叶子结点数的示例。