c++ 二叉链表编写算法求二叉树的叶子结点数

根据二叉链表的定义，可以通过递归的方式求解二叉树的叶子结点数。具体算法如下：
1. 如果当前结点为空，则返回0。
2. 如果当前结点的左右子树都为空，则返回1。
3. 否则，递归计算左子树和右子树的叶子结点数，并将它们相加返回。

下面是C++代码实现：

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

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

相关问题

c++以二叉链表为存储结构编写算法求二叉树中结点x的双亲

下面是求二叉树中某个结点 x 的双亲结点的 C++ 代码，假设二叉树的结点结构体定义如下：

struct BinaryTreeNode {
    int data; //结点数据
    BinaryTreeNode *left; //左子树指针
    BinaryTreeNode *right; //右子树指针
};

算法思路：

- 如果根结点就是 x 结点，则 x 结点没有双亲结点；
- 如果 x 结点是根结点的左子结点或右子结点，则根结点就是 x 结点的双亲结点；
- 否则，递归地在左子树和右子树中查找 x 结点的双亲结点。

代码实现：

BinaryTreeNode* FindParent(BinaryTreeNode* root, BinaryTreeNode* x) {
    if (root == nullptr || root == x) {
        return nullptr; //根结点就是 x 结点或者树为空，没有双亲结点
    }
    if (root->left == x || root->right == x) {
        return root; //x 结点是根结点的左子结点或右子结点，根结点就是 x 结点的双亲结点
    }
    BinaryTreeNode* parent = FindParent(root->left, x); //在左子树中查找
    if (parent != nullptr) {
        return parent; //在左子树中找到了，返回结果
    } else {
        return FindParent(root->right, x); //在右子树中查找
    }
}

其中，root 表示二叉树的根结点，x 表示要查找双亲结点的结点。函数返回值是 x 结点的双亲结点，如果 x 结点没有双亲结点则返回 nullptr。

c++编写算法建立一棵二叉树的二叉链表

以下是C++代码，实现二叉树的二叉链表表示：

#include <iostream>
using namespace std;

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

// 建立二叉树
void createTree(TreeNode*& root){
    int val;
    cin >> val;
    if(val == -1){ // 输入-1表示该节点为空
        root = NULL;
    }else{
        root = new TreeNode(val);
        createTree(root->left);
        createTree(root->right);
    }
}

// 二叉树前序遍历
void preorder(TreeNode* root){
    if(root == NULL) return;
    cout << root->val << " ";
    preorder(root->left);
    preorder(root->right);
}

int main(){
    TreeNode* root;
    createTree(root);
    cout << "前序遍历结果为：";
    preorder(root);
    return 0;
}

在上述代码中，`TreeNode` 结构体表示二叉树的节点，其中 `val` 表示节点的值，`left` 和 `right` 分别表示左右子树的指针，初始化为 `NULL`。`createTree` 函数用于建立二叉树，其中 `-1` 表示该节点为空。`preorder` 函数实现二叉树的前序遍历。在 `main` 函数中，首先调用 `createTree` 函数建立二叉树，然后调用 `preorder` 函数进行前序遍历。