<7>键盘输入一个元素x,求其父节点、兄弟结点、子结点的值,不存在时给出相应提示信息。对兄弟结点和孩子结点,存在时要明确指出是左兄弟、左孩子、右兄弟或右孩子。
时间: 2024-02-06 18:02:18 浏览: 76
好的,这里给出一个基于二叉树类实现的程序,可以实现键盘输入一个元素x,求其父节点、兄弟结点、子结点的值:
```cpp
#include <iostream>
using namespace std;
// 节点结构体
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// 二叉树类
class BinaryTree {
public:
BinaryTree() : root(nullptr) {}
// 插入节点
void insert(int val) {
if (root == nullptr) {
root = new TreeNode(val);
return;
}
TreeNode* cur = root;
while (cur != nullptr) {
if (val < cur->val) {
if (cur->left == nullptr) {
cur->left = new TreeNode(val);
return;
}
cur = cur->left;
} else {
if (cur->right == nullptr) {
cur->right = new TreeNode(val);
return;
}
cur = cur->right;
}
}
}
// 查找节点
TreeNode* find(int val) {
TreeNode* cur = root;
while (cur != nullptr) {
if (cur->val == val) {
return cur;
} else if (cur->val > val) {
cur = cur->left;
} else {
cur = cur->right;
}
}
return nullptr;
}
// 获取父节点
TreeNode* getParent(int val) {
return getParentNode(root, val);
}
// 获取兄弟节点
TreeNode* getSibling(int val) {
TreeNode* cur = find(val);
if (cur == nullptr || cur == root) {
return nullptr;
}
TreeNode* parent = getParent(val);
if (parent == nullptr) {
return nullptr;
}
if (parent->left == cur) {
return parent->right;
} else {
return parent->left;
}
}
// 获取左孩子节点
TreeNode* getLeftChild(int val) {
TreeNode* cur = find(val);
if (cur == nullptr) {
return nullptr;
}
return cur->left;
}
// 获取右孩子节点
TreeNode* getRightChild(int val) {
TreeNode* cur = find(val);
if (cur == nullptr) {
return nullptr;
}
return cur->right;
}
private:
// 根节点
TreeNode* root;
// 获取父节点
TreeNode* getParentNode(TreeNode* root, int val) {
if (root == nullptr || root->val == val) {
return nullptr;
}
if ((root->left != nullptr && root->left->val == val) || (root->right != nullptr && root->right->val == val)) {
return root;
}
TreeNode* left = getParentNode(root->left, val);
TreeNode* right = getParentNode(root->right, val);
if (left != nullptr) {
return left;
}
return right;
}
};
int main() {
BinaryTree tree;
tree.insert(5);
tree.insert(3);
tree.insert(7);
tree.insert(2);
tree.insert(4);
tree.insert(6);
tree.insert(8);
int x;
cout << "请输入要查找的元素x:" << endl;
cin >> x;
TreeNode* node = tree.find(x);
if (node == nullptr) {
cout << "元素x不存在" << endl;
return 0;
}
TreeNode* parent = tree.getParent(x);
if (parent != nullptr) {
cout << "元素x的父节点为:" << parent->val << endl;
} else {
cout << "元素x为根节点,没有父节点" << endl;
}
TreeNode* sibling = tree.getSibling(x);
if (sibling != nullptr) {
if (parent->left == node) {
cout << "元素x的右兄弟节点为:" << sibling->val << endl;
} else {
cout << "元素x的左兄弟节点为:" << sibling->val << endl;
}
} else {
cout << "元素x没有兄弟节点" << endl;
}
TreeNode* leftChild = tree.getLeftChild(x);
if (leftChild != nullptr) {
cout << "元素x的左孩子节点为:" << leftChild->val << endl;
} else {
cout << "元素x没有左孩子节点" << endl;
}
TreeNode* rightChild = tree.getRightChild(x);
if (rightChild != nullptr) {
cout << "元素x的右孩子节点为:" << rightChild->val << endl;
} else {
cout << "元素x没有右孩子节点" << endl;
}
return 0;
}
```
以上程序实现了根据输入的元素x,输出其父节点、兄弟结点、子结点的值。注意,在查找兄弟节点时,需要判断当前节点是否为根节点或者是其父节点的左/右子节点,以确定兄弟节点是左兄弟还是右兄弟。
阅读全文