输入格式:第一行输入n表示二叉树共有n个节点,编号分别为1到n,第二行输入包含n个用空格分隔的正整数,其中第i个数表示编号为i的节点的权重,第三行输入包含(n-1)个用空格分开的正整数,表示编号2到n的节点的父节点编号。用C++给出建立树的代码
时间: 2024-09-21 19:07:39 浏览: 49
找出链表倒数第n个节点元素的二个方法
在C++中,我们可以使用`vector`和`map`来表示二叉树并构建节点。下面是一个简单的例子,展示了如何根据输入创建一棵带权重的二叉树:
```cpp
#include <iostream>
#include <vector>
#include <map>
// 定义二叉树节点
struct TreeNode {
int id;
int weight;
TreeNode* left = nullptr;
TreeNode* right = nullptr;
};
// 创建一个新的二叉树节点
TreeNode* createNode(int id, int weight) {
TreeNode* node = new TreeNode();
node->id = id;
node->weight = weight;
return node;
}
// 根据输入构建二叉树
void buildBinaryTree(std::vector<int>& nodes, std::map<int, TreeNode*>& treeMap, int n) {
for (int i = 1; i <= n; i++) {
int weight = nodes[i - 1]; // 从0开始计数
TreeNode* node = createNode(i, weight);
if (i != 1) { // 如果不是根节点
int parent = nodes[i - 2]; // 父节点编号减1
treeMap[parent].right = node; // 将右孩子指针指向新节点
node->left = nullptr; // 初始化左孩子为空,因为是二叉树
} else {
treeMap[i] = node; // 根节点直接添加到map中
}
}
}
int main() {
int n;
std::cin >> n;
std::vector<int> nodes(n);
for (auto& node : nodes) {
cin >> node;
}
std::map<int, TreeNode*> treeMap;
std::vector<int> parentNodes(n - 1);
for (int i = 0; i < n - 1; i++) {
cin >> parentNodes[i];
}
buildBinaryTree(nodes, treeMap, n);
// 现在你可以通过treeMap来操作树了
// 例如遍历、搜索或修改节点
return 0;
}
```
在这个代码中,`buildBinaryTree`函数接收一个节点列表和映射,根据给定的父节点信息逐步构造二叉树。注意,这里假设输入的数据总是有效的,并且每个节点都有一个唯一的父节点。
阅读全文