统计二叉树中度为1结点个数c++

可以使用递归的方式来统计二叉树中度为1的节点数量。首先，我们需要定义二叉树的数据结构：

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

然后，我们可以使用一个递归函数来统计二叉树中度为1的节点数量：

int countDegreeOneNodes(TreeNode* root) {
    if (root == NULL) {
        return 0;
    }

    int count = 0;

    // 如果当前节点的度为1，则count加1
    if ((root->left == NULL && root->right != NULL) || (root->left != NULL && root->right == NULL)) {
        count++;
    }

    // 递归统计左子树和右子树中度为1的节点数量
    count += countDegreeOneNodes(root->left);
    count += countDegreeOneNodes(root->right);

    return count;
}

通过调用 `countDegreeOneNodes` 函数并传入二叉树的根节点，即可得到度为1的节点数量。

相关问题

c++统计二叉树度为2的结点个数

在 C++ 中，要统计二叉树中度为 2 的节点（即有两个子节点的节点），你可以遍历整个二叉树并计数。这通常需要递归，因为每个节点都有左右两个子节点，我们可以在访问每个节点时检查其左子节点和右子节点是否都存在。

以下是一个简单的步骤说明：

1. 定义一个二叉树节点结构体，包含整数值和指向左右子节点的指针。

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

2. 写一个递归函数，该函数接受一个节点作为输入，并返回度为 2 的节点的数量。如果当前节点不是 null，则递归地计算左右子节点的度，并加上当前节点自身度为 2 的情况。

int countDegreeTwo(TreeNode* root) {
    if (root == nullptr) return 0; // 空节点不计数

    int leftDegree = (root->left != nullptr) ? 1 : 0;
    int rightDegree = (root->right != nullptr) ? 1 : 0;

    if (leftDegree && rightDegree) ++count; // 当前节点度为 2
    return leftDegree + rightDegree + countDegreeTwo(root->left) + countDegreeTwo(root->right);
}

3. 最后，在主程序中创建一个二叉树实例并调用上述函数来获取结果。

int main() {
    // 初始化并构建你的二叉树
    TreeNode* tree = ...;
    
    int result = countDegreeTwo(tree);
    std::cout << "二叉树中有 " << result << " 个度为 2 的节点.\n";
    return 0;
}

设一棵二叉树以二叉链表表示，试以成员函数形式编写有关二叉树的递归算法： (1) 统计二叉树中度为1的结点个数。 (2) 统计二叉树中度为2的结点个数。 (3) 统计二叉树中度为0（叶结点）的结点个数。 (4) 统计二叉树的高度。 (5) 统计二叉树的宽度，即在二叉树的各层上，具有结点数最多的那一层上结点总数。(6) 从二叉树中删去所有叶结点。 (7) 计算二叉树中指定结点 *p 所在层次。 (8) 计算二叉树中各结点中的最大元素的值。 (9) 以前序次序输出一棵二叉树所有结点的数据值及结点所在层次。

以下是二叉树的递归算法实现：

#include<iostream>
using namespace std;

struct node{
    int data;
    node *left;
    node *right;
};

class BinaryTree{
    private:
        node *root;
    public:
        BinaryTree(){
            root = NULL;
        }
        node* get_root(){
            return root;
        }
        void create_tree(node *&root){
            int data;
            cin >> data;
            if(data == -1){
                root = NULL;
            }else{
                root = new node;
                root->data = data;
                create_tree(root->left);
                create_tree(root->right);
            }
        }
        int count_degree_one(node *root){
            if(root == NULL){
                return 0;
            }
            int count = 0;
            if((root->left != NULL && root->right == NULL) || (root->left == NULL && root->right != NULL)){
                count = 1;
            }
            return count + count_degree_one(root->left) + count_degree_one(root->right);
        }
        int count_degree_two(node *root){
            if(root == NULL){
                return 0;
            }
            int count = 0;
            if(root->left != NULL && root->right != NULL){
                count = 1;
            }
            return count + count_degree_two(root->left) + count_degree_two(root->right);
        }
        int count_degree_zero(node *root){
            if(root == NULL){
                return 0;
            }
            int count = 0;
            if(root->left == NULL && root->right == NULL){
                count = 1;
            }
            return count + count_degree_zero(root->left) + count_degree_zero(root->right);
        }
        int height(node *root){
            if(root == NULL){
                return 0;
            }
            return max(height(root->left), height(root->right)) + 1;
        }
        void count_width(node *root, int level, int width[]){
            if(root == NULL){
                return;
            }
            width[level]++;
            count_width(root->left, level+1, width);
            count_width(root->right, level+1, width);
        }
        int find_max_width(int width[], int level){
            int max_width = 0;
            for(int i=0; i<=level; i++){
                if(width[i] > max_width){
                    max_width = width[i];
                }
            }
            return max_width;
        }
        int width(node *root){
            if(root == NULL){
                return 0;
            }
            int h = height(root);
            int width[h];
            for(int i=0; i<h; i++){
                width[i] = 0;
            }
            count_width(root, 0, width);
            return find_max_width(width, h-1);
        }
        node* delete_leaves(node *root){
            if(root == NULL){
                return NULL;
            }
            if(root->left == NULL && root->right == NULL){
                delete root;
                return NULL;
            }
            root->left = delete_leaves(root->left);
            root->right = delete_leaves(root->right);
            return root;
        }
        int find_level(node *root, node *p, int level){
            if(root == NULL){
                return -1;
            }
            if(root == p){
                return level;
            }
            int l = find_level(root->left, p, level+1);
            if(l == -1){
                return find_level(root->right, p, level+1);
            }
            return l;
        }
        int find_max_data(node *root){
            if(root == NULL){
                return -1;
            }
            int max_data = root->data;
            max_data = max(max_data, find_max_data(root->left));
            max_data = max(max_data, find_max_data(root->right));
            return max_data;
        }
        void pre_order(node *root, int level){
            if(root == NULL){
                return;
            }
            cout << root->data << " at level " << level << endl;
            pre_order(root->left, level+1);
            pre_order(root->right, level+1);
        }
};

int main(){
    BinaryTree tree;
    cout << "Enter tree elements in pre-order traversal. Enter -1 for NULL." << endl;
    tree.create_tree(tree.get_root());

    cout << "Number of nodes with degree 1: " << tree.count_degree_one(tree.get_root()) << endl;
    cout << "Number of nodes with degree 2: " << tree.count_degree_two(tree.get_root()) << endl;
    cout << "Number of leaf nodes: " << tree.count_degree_zero(tree.get_root()) << endl;
    cout << "Height of tree: " << tree.height(tree.get_root()) << endl;
    cout << "Width of tree: " << tree.width(tree.get_root()) << endl;

    cout << "Deleting leaf nodes..." << endl;
    tree.delete_leaves(tree.get_root());
    cout << "Number of leaf nodes after deletion: " << tree.count_degree_zero(tree.get_root()) << endl;

    node *p;
    int data;
    cout << "Enter a node data to find its level: ";
    cin >> data;
    p = new node;
    p->data = data;
    p->left = NULL;
    p->right = NULL;
    cout << "Level of node " << data << ": " << tree.find_level(tree.get_root(), p, 0) << endl;

    cout << "Maximum element in tree: " << tree.find_max_data(tree.get_root()) << endl;

    cout << "Pre-order traversal of tree:" << endl;
    tree.pre_order(tree.get_root(), 0);

    return 0;
}

这个程序中，我们首先输入二叉树的元素，然后分别调用成员函数来执行每个操作。在每个函数中，我们使用递归来访问树的每个节点，并执行必要的操作。注意，我们使用一个指向节点的指针作为参数，因为我们需要递归地访问树的各个部分。