用c++构建一个完全二叉树,存储二叉树节点的编号和数据域。 要求:输入的任意结点编号,输出其左、右孩子结点的编号和数据域。
时间: 2024-03-14 19:47:34 浏览: 32
以C++类的方式实现二叉树数据结构完整版
5星 · 资源好评率100%
好的,我可以为您提供一个C++代码示例来构建一个完全二叉树,并输出指定节点的左右孩子的编号和数据域。
```c++
#include <iostream>
#include <vector>
using namespace std;
// 定义二叉树节点结构体
struct TreeNode {
int val;
int id;
TreeNode *left, *right;
TreeNode(int x, int idx) : val(x), id(idx), left(NULL), right(NULL) {}
};
// 构建完全二叉树
TreeNode* buildCompleteBinaryTree(vector<int> nums) {
int n = nums.size();
if (n == 0) return NULL;
vector<TreeNode*> nodes(n);
for (int i = 0; i < n; i++) {
nodes[i] = new TreeNode(nums[i], i + 1);
}
for (int i = 0; i < n / 2; i++) {
nodes[i]->left = nodes[i * 2 + 1];
nodes[i]->right = nodes[i * 2 + 2];
}
if (n % 2 == 1) {
nodes[n / 2]->left = nodes[n - 1];
}
return nodes[0];
}
// 查找指定节点的左右孩子
void findChild(TreeNode* root, int nodeId) {
if (root == NULL) return;
if (root->id == nodeId) {
if (root->left != NULL) {
cout << "Left child: " << root->left->id << " " << root->left->val << endl;
}
if (root->right != NULL) {
cout << "Right child: " << root->right->id << " " << root->right->val << endl;
}
return;
}
findChild(root->left, nodeId);
findChild(root->right, nodeId);
}
int main() {
// 构建完全二叉树
vector<int> nums = {1, 2, 3, 4, 5, 6, 7, 8, 9};
TreeNode* root = buildCompleteBinaryTree(nums);
// 查找指定节点的左右孩子
int nodeId = 3;
findChild(root, nodeId);
return 0;
}
```
这段代码首先定义了一个结构体`TreeNode`,表示二叉树的节点,包括数据域`val`和节点编号`id`,以及左右孩子节点的指针`left`和`right`。然后,我们通过`buildCompleteBinaryTree`函数构建了一个完全二叉树,并通过`findChild`函数查找指定节点的左右孩子。在`main`函数中,我们可以自定义输入一个节点编号,然后输出其左右孩子的编号和数据域。
希望这个代码示例能够帮助到您!
阅读全文