用递归算法求二叉树中的二度结点C 语言

假设二叉树的结点结构体定义如下：

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

可以使用递归算法来求二叉树中的二度结点。具体思路如下：

1. 如果当前结点为 NULL，则返回 0；
2. 如果当前结点左右子树均存在，则当前结点为二度结点，返回 1；
3. 否则，分别递归遍历当前结点的左右子树，将返回值相加。

下面是具体的 C 语言实现：

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

可以通过调用 `countSecondDegreeNodes` 函数来统计二叉树中的二度结点个数。

相关问题

帮我编写一个程序，要求如下，给出完整定义的代码 1、先序遍历二叉树的递归算法 2、中序遍历二叉树的递归算法 3、后序遍历二叉树的递归算法 4、计算二叉树的深度的递归算法 5、统计二叉树的结点个数的递归算法 6、统计二叉树的叶子结点个数的递归算法 7、设计该二叉树第K层的结点个数。 8、求该二叉树中所有结点值最大的元素。 9、打印二叉树的叶子结点数的递归算法 给出完整的程序代码

好的，以下是完整的程序代码：

#include <iostream>

using namespace std;

// 二叉树节点的定义
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// 先序遍历二叉树的递归算法
void preorderTraversal(TreeNode* root) {
    if (root == NULL) return;
    cout << root->val << " ";
    preorderTraversal(root->left);
    preorderTraversal(root->right);
}

// 中序遍历二叉树的递归算法
void inorderTraversal(TreeNode* root) {
    if (root == NULL) return;
    inorderTraversal(root->left);
    cout << root->val << " ";
    inorderTraversal(root->right);
}

// 后序遍历二叉树的递归算法
void postorderTraversal(TreeNode* root) {
    if (root == NULL) return;
    postorderTraversal(root->left);
    postorderTraversal(root->right);
    cout << root->val << " ";
}

// 计算二叉树的深度的递归算法
int maxDepth(TreeNode* root) {
    if (root == NULL) return 0;
    int leftDepth = maxDepth(root->left);
    int rightDepth = maxDepth(root->right);
    return max(leftDepth, rightDepth) + 1;
}

// 统计二叉树的结点个数的递归算法
int countNodes(TreeNode* root) {
    if (root == NULL) return 0;
    return countNodes(root->left) + countNodes(root->right) + 1;
}

// 统计二叉树的叶子结点个数的递归算法
int countLeaves(TreeNode* root) {
    if (root == NULL) return 0;
    if (root->left == NULL && root->right == NULL) return 1;
    return countLeaves(root->left) + countLeaves(root->right);
}

// 设计该二叉树第K层的结点个数
int countNodesInKthLevel(TreeNode* root, int k) {
    if (root == NULL || k < 1) return 0;
    if (k == 1) return 1;
    return countNodesInKthLevel(root->left, k - 1) + countNodesInKthLevel(root->right, k - 1);
}

// 求该二叉树中所有结点值最大的元素
int findMax(TreeNode* root) {
    if (root == NULL) return INT_MIN;
    int leftMax = findMax(root->left);
    int rightMax = findMax(root->right);
    return max(root->val, max(leftMax, rightMax));
}

// 打印二叉树的叶子结点数的递归算法
void printLeaves(TreeNode* root) {
    if (root == NULL) return;
    if (root->left == NULL && root->right == NULL) cout << root->val << " ";
    printLeaves(root->left);
    printLeaves(root->right);
}

// 示例代码
int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->left = new TreeNode(6);
    root->right->right = new TreeNode(7);

    cout << "先序遍历：";
    preorderTraversal(root);
    cout << endl;

    cout << "中序遍历：";
    inorderTraversal(root);
    cout << endl;

    cout << "后序遍历：";
    postorderTraversal(root);
    cout << endl;

    cout << "深度为：" << maxDepth(root) << endl;

    cout << "结点个数为：" << countNodes(root) << endl;

    cout << "叶子结点个数为：" << countLeaves(root) << endl;

    cout << "第3层的结点个数为：" << countNodesInKthLevel(root, 3) << endl;

    cout << "节点值最大的元素为：" << findMax(root) << endl;

    cout << "叶子结点的值为：";
    printLeaves(root);
    cout << endl;

    return 0;
}

以上是完整的程序代码，你可以直接在 C++ 编译器中运行。注意要先定义二叉树节点的结构体 `TreeNode`，然后实现每个函数的具体逻辑。

一、问题描述 已知一棵二叉树,求该二叉树的叶结点的个数 、基本要求 (1)采用二叉链表存储二叉树。 (2)采用递归算法求二叉树中叶结点个数。 (3) 采用非递归算法求二叉树中叶结点个数 、设计提示 1.数据结构设计 根据“基本要求”,二叉树采用二叉链表存储结构 2.功能设计 完成该实验至少涉及以下 4 个功能: (1) 创建二叉树。(2)显示二叉树.用于了解创建的二叉树是否正确。 (3)采用递归算法求叶结点个数。 (4)采用非递归算法求叶结点个数

二、解决方案

1.数据结构设计

二叉树采用二叉链表存储结构，每个节点包含三个成员变量：data表示节点的数据域，left表示节点的左子树指针，right表示节点的右子树指针。

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

2.功能设计

(1) 创建二叉树。

采用递归方式创建二叉树，输入-1表示该节点为空。

TreeNode* createTree() {
    int val;
    cin >> val;
    if (val == -1) {
        return NULL;
    }
    TreeNode* root = new TreeNode(val);
    root->left = createTree();
    root->right = createTree();
    return root;
}

(2) 显示二叉树。

采用前序遍历方式显示二叉树。

void displayTree(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    cout << root->data << " ";
    displayTree(root->left);
    displayTree(root->right);
}

(3) 采用递归算法求叶结点个数。

如果当前节点为空，返回0；如果当前节点为叶子节点，返回1；否则递归计算左子树和右子树的叶子节点个数之和。

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);
}

(4) 采用非递归算法求叶结点个数。

采用栈来存储节点，先将根节点入栈。每次取出栈顶元素，如果该元素为叶子节点，则计数器加1，否则将其左右子节点依次入栈，直到栈为空。

int countLeafNodesNonRecursive(TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    stack<TreeNode*> s;
    s.push(root);
    int count = 0;
    while (!s.empty()) {
        TreeNode* node = s.top();
        s.pop();
        if (node->left == NULL && node->right == NULL) {
            count++;
        } else {
            if (node->right != NULL) {
                s.push(node->right);
            }
            if (node->left != NULL) {
                s.push(node->left);
            }
        }
    }
    return count;
}

三、完整代码

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

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

TreeNode* createTree() {
    int val;
    cin >> val;
    if (val == -1) {
        return NULL;
    }
    TreeNode* root = new TreeNode(val);
    root->left = createTree();
    root->right = createTree();
    return root;
}

void displayTree(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    cout << root->data << " ";
    displayTree(root->left);
    displayTree(root->right);
}

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 countLeafNodesNonRecursive(TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    stack<TreeNode*> s;
    s.push(root);
    int count = 0;
    while (!s.empty()) {
        TreeNode* node = s.top();
        s.pop();
        if (node->left == NULL && node->right == NULL) {
            count++;
        } else {
            if (node->right != NULL) {
                s.push(node->right);
            }
            if (node->left != NULL) {
                s.push(node->left);
            }
        }
    }
    return count;
}

int main() {
    TreeNode* root = createTree();
    displayTree(root);
    cout << endl;
    cout << "Number of leaf nodes (recursive): " << countLeafNodes(root) << endl;
    cout << "Number of leaf nodes (non-recursive): " << countLeafNodesNonRecursive(root) << endl;
    return 0;
}