从控制台输入树的双亲-孩子有序对,调用树的创建算法,生成树的二叉链表的存储结构T c++代码
时间: 2024-12-20 15:18:16 浏览: 5
在C++中,我们可以编写一个简单的程序来读取从控制台输入的树的双亲-孩子有序对,并通过递归的方式构建一棵二叉树。这里是一个基本的示例代码:
```cpp
#include <iostream>
#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 根据输入创建二叉树
TreeNode* createTreeFromPairs(vector<pair<int, int>>& pairs) {
if (pairs.empty()) return NULL; // 如果输入为空,返回空指针
int rootVal = pairs[0].first;
TreeNode* root = new TreeNode(rootVal); // 创建根节点
for (const auto& pair : pairs) { // 遍历所有输入对
int parentVal = pair.first;
int childVal = pair.second;
// 如果当前元素是根节点,则跳过
if (parentVal == -1) continue;
// 找到并更新孩子的双亲
TreeNode* parent = findParent(root, parentVal);
if (!parent) {
cout << "Invalid input: Parent not found!" << endl;
return NULL; // 如果找不到双亲,返回NULL
}
if (childVal > parentVal) { // 保持左孩子的顺序
parent->left = findOrCreateNode(parent->left, childVal);
} else { // 右孩子
parent->right = findOrCreateNode(parent->right, childVal);
}
}
return root;
}
// 辅助函数,用于查找节点或新建节点
TreeNode* findOrCreateNode(TreeNode* &node, int val) {
if (!node) node = new TreeNode(val);
return node;
}
// 辅助函数,查找指定值的父节点
TreeNode* findParent(TreeNode* root, int target) {
while (root && root->val != target) {
root = root->val > target ? root->left : root->right;
}
return root;
}
int main() {
vector<pair<int, int>> pairs = {{-1, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 5}, {2, 6}};
TreeNode* tree = createTreeFromPairs(pairs);
// 现在你可以打印或操作树了
// ...
return 0;
}
```
这个程序首先定义了一个`TreeNode`结构体表示树节点,然后实现了`createTreeFromPairs`函数来根据输入的双亲-孩子对构建树。注意,输入的第一个元素作为根节点,其值为-1表示没有双亲。
运行这个程序时,你需要提供一个正确的双亲-孩子有序对列表,例如上述例子中的`pairs`。如果输入有误(比如双亲不存在),程序会输出错误消息并返回NULL。
阅读全文