用c++构建一个完全二叉树,存储二叉树节点的编号和数据域。 要求:输入的任意结点编号,输出其左、右孩子结点的编号和数据域。
时间: 2024-03-11 11:48:19 浏览: 55
好的,以下是一个用 C++ 实现的完全二叉树的示例代码,希望能对您有所帮助。
```c++
#include <iostream>
#include <vector>
using namespace std;
// 定义二叉树节点结构体
struct TreeNode {
int val; // 数据域
int index; // 节点编号
TreeNode* left; // 左孩子指针
TreeNode* right; // 右孩子指针
TreeNode(int x, int i) : val(x), index(i), left(NULL), right(NULL) {}
};
// 构建完全二叉树
TreeNode* buildCBT(vector<int>& nums, int start, int end, int index) {
if (start > end) {
return NULL;
}
// 构建根节点
TreeNode* root = new TreeNode(nums[start], index);
// 计算左右子节点的索引
int leftIndex = 2 * index + 1;
int rightIndex = 2 * index + 2;
// 构建左右子树
root->left = buildCBT(nums, start * 2 + 1, end, leftIndex);
root->right = buildCBT(nums, start * 2 + 2, end, rightIndex);
return root;
}
// 查找节点的左右孩子
void findChildren(TreeNode* root, int index) {
if (root == NULL) {
return;
}
if (root->index == index) {
if (root->left) {
cout << "左孩子节点编号:" << root->left->index << ", 数据域:" << root->left->val << endl;
} else {
cout << "该节点没有左孩子" << endl;
}
if (root->right) {
cout << "右孩子节点编号:" << root->right->index << ", 数据域:" << root->right->val << endl;
} else {
cout << "该节点没有右孩子" << endl;
}
} else {
findChildren(root->left, index);
findChildren(root->right, index);
}
}
int main() {
vector<int> nums = {1, 2, 3, 4, 5, 6, 7}; // 完全二叉树的数据域
TreeNode* root = buildCBT(nums, 0, nums.size() - 1, 0); // 构建完全二叉树
int index;
cout << "请输入节点编号:" << endl;
cin >> index;
findChildren(root, index); // 查找节点的左右孩子
return 0;
}
```
在这个示例代码中,我们定义了一个 `TreeNode` 结构体表示二叉树的节点,包含了数据域、节点编号、左孩子指针和右孩子指针。然后我们采用递归的方式构建完全二叉树,构建完成后,用户输入任意节点编号,程序会查找该节点的左右孩子,并输出它们的编号和数据域。
阅读全文