计算二叉树的叶子结点数； 求二叉树的深度 。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文件，在终端中运行该文件，然后输入二叉树的先序遍历序列，程序将会输出先序、中序、后序遍历结果，叶子结点数和二叉树深度。

设计一个二叉链表存储的二叉树； （2）编写二叉树的创建、显示的程序； （3）编写二叉树先序、中序、后序、层次遍历的应用程序； （4）编写求二叉树叶子结点数、总结点数和深度的应用程序； （5）设计一个选择式菜单，以菜单方式选择上述操作。

1. 二叉链表存储的二叉树定义：

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

2. 二叉树的创建和显示程序：

TreeNode* createTree() {
    int val;
    cin >> val;
    if (val == -1) return nullptr; // -1 表示为空节点
    TreeNode* root = new TreeNode(val);
    root->left = createTree();
    root->right = createTree();
    return root;
}

void printTree(TreeNode* root) {
    if (root == nullptr) return;
    cout << root->val << " ";
    printTree(root->left);
    printTree(root->right);
}

3. 二叉树的遍历程序：

void preorder(TreeNode* root) {
    if (root == nullptr) return;
    cout << root->val << " ";
    preorder(root->left);
    preorder(root->right);
}

void inorder(TreeNode* root) {
    if (root == nullptr) return;
    inorder(root->left);
    cout << root->val << " ";
    inorder(root->right);
}

void postorder(TreeNode* root) {
    if (root == nullptr) return;
    postorder(root->left);
    postorder(root->right);
    cout << root->val << " ";
}

void levelorder(TreeNode* root) {
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        if (node == nullptr) continue;
        cout << node->val << " ";
        q.push(node->left);
        q.push(node->right);
    }
}

4. 求二叉树叶子结点数、总结点数和深度的程序：

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

int countNode(TreeNode* root) {
    if (root == nullptr) return 0;
    return countNode(root->left) + countNode(root->right) + 1;
}

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

5. 选择式菜单程序：

int main() {
    TreeNode* root = nullptr;
    while (true) {
        cout << "1. 创建二叉树\n";
        cout << "2. 显示二叉树\n";
        cout << "3. 先序遍历\n";
        cout << "4. 中序遍历\n";
        cout << "5. 后序遍历\n";
        cout << "6. 层次遍历\n";
        cout << "7. 求叶子结点数\n";
        cout << "8. 求总结点数\n";
        cout << "9. 求深度\n";
        cout << "0. 退出程序\n";
        cout << "请选择操作：";
        int choice;
        cin >> choice;
        switch (choice) {
            case 1:
                root = createTree();
                break;
            case 2:
                printTree(root);
                cout << endl;
                break;
            case 3:
                preorder(root);
                cout << endl;
                break;
            case 4:
                inorder(root);
                cout << endl;
                break;
            case 5:
                postorder(root);
                cout << endl;
                break;
            case 6:
                levelorder(root);
                cout << endl;
                break;
            case 7:
                cout << countLeaf(root) << endl;
                break;
            case 8:
                cout << countNode(root) << endl;
                break;
            case 9:
                cout << depth(root) << endl;
                break;
            case 0:
                return 0;
            default:
                cout << "输入错误，请重新选择。\n";
        }
    }
}