C++ 完全二叉树节点与子节点

在完全二叉树中，每个节点都有左子节点和右子节点，除了叶子节点外。假设节点的编号为 i：

1. 左子节点的编号为 2i。
2. 右子节点的编号为 2i+1。
3. 父节点的编号为 i/2（向下取整）。

需要注意的是，在实现完全二叉树时，通常使用数组来存储节点。因此，编号从 1 开始而不是从 0 开始。也就是说，数组中的第一个元素代表根节点，其编号为 1。因此，左子节点和右子节点在数组中的下标分别为 2i 和 2i+1。

相关问题

C++求二叉树指定结点到根节点的路径

二叉树的每个结点都有两个指针，指向其左、右子树，可以使用递归的方式来求解指定结点到根节点的路径。

具体步骤如下：

1. 如果当前结点为空，则返回false。

2. 如果当前结点为目标结点，则返回true。

3. 递归遍历左子树，如果左子树中存在目标结点，则将当前结点加入路径中，并返回true。

4. 递归遍历右子树，如果右子树中存在目标结点，则将当前结点加入路径中，并返回true。

5. 如果左、右子树都不存在目标结点，则返回false。

6. 如果返回true，则将当前结点加入路径中。

7. 返回路径。

下面是C语言实现代码：

#include <stdio.h>
#include <stdbool.h>

// 二叉树结点结构体
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

// 递归求解路径
bool findPath(struct TreeNode* root, int target, int* path, int* pathLen) {
    // 如果当前结点为空，则返回false
    if (root == NULL) {
        return false;
    }

    // 如果当前结点为目标结点，则返回true
    if (root->val == target) {
        path[*pathLen] = root->val;
        (*pathLen)++;
        return true;
    }

    // 递归遍历左子树
    if (findPath(root->left, target, path, pathLen)) {
        path[*pathLen] = root->val;
        (*pathLen)++;
        return true;
    }

    // 递归遍历右子树
    if (findPath(root->right, target, path, pathLen)) {
        path[*pathLen] = root->val;
        (*pathLen)++;
        return true;
    }

    // 如果左、右子树都不存在目标结点，则返回false
    return false;
}

// 求解指定结点到根节点的路径
int* getPath(struct TreeNode* root, int target, int* returnSize) {
    // 定义路径数组
    int* path = (int*)malloc(1000 * sizeof(int));

    // 定义路径长度
    int pathLen = 0;

    // 递归求解路径
    findPath(root, target, path, &pathLen);

    // 将路径数组反转，得到从根节点到指定结点的路径
    int i, j;
    for (i = 0, j = pathLen - 1; i < j; i++, j--) {
        int temp = path[i];
        path[i] = path[j];
        path[j] = temp;
    }

    // 设置返回值
    *returnSize = pathLen;

    // 返回路径数组
    return path;
}

使用方法如下：

int main() {
    // 构建二叉树
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = 1;
    root->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->left->val = 2;
    root->left->left = NULL;
    root->left->right = NULL;
    root->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->right->val = 3;
    root->right->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->right->left->val = 4;
    root->right->left->left = NULL;
    root->right->left->right = NULL;
    root->right->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->right->right->val = 5;
    root->right->right->left = NULL;
    root->right->right->right = NULL;

    // 求解路径
    int* path;
    int pathLen;
    path = getPath(root, 4, &pathLen);

    // 输出路径
    int i;
    for (i = 0; i < pathLen; i++) {
        printf("%d ", path[i]);
    }
    printf("\n");

    return 0;
}

输出结果为：3 4

统计二叉树结点个数c++

要统计二叉树的节点个数，可以使用递归的方式来实现。下面是一个使用C++实现的示例代码：

#include <iostream>

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

// 统计二叉树结点个数的函数
int countNodes(TreeNode* root) {
    if (root == nullptr) {
        return 0;
    }
    
    // 递归统计左子树和右子树的结点个数，加上根结点自身的个数
    return 1 + countNodes(root->left) + countNodes(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);
    
    // 统计结点个数并输出结果
    int nodeCount = countNodes(root);
    std::cout << "二叉树的结点个数为：" << nodeCount << std::endl;
    
    return 0;
}

上述代码定义了一个二叉树结点`TreeNode`，其中`val`表示结点的值，`left`和`right`分别指向左子树和右子树的指针。`countNodes`函数使用递归的方式统计二叉树的结点个数，如果根结点为空，则返回0；否则，返回左子树结点个数、右子树结点个数和根结点本身的个数之和。在`main`函数中创建了一个二叉树，并调用`countNodes`函数统计结点个数并输出结果。