已知以二叉链表作存储结构,使用C++语言创建二叉树,并编写代码实现在二叉树中查找某个节点值,如果找到,返回该节点的父节点,否则返回空,然后测试函数功能
时间: 2024-12-19 20:26:57 浏览: 11
在C++中,我们可以首先定义一个二叉链表节点(Binary Search Tree Node),包含值、左孩子和右孩子的指针。然后定义二叉树的类,包含插入节点、查找节点和获取父节点的方法。以下是部分代码实现:
```cpp
#include <iostream>
// 定义二叉链表节点
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class BinaryTree {
public:
// 插入节点
void insert(int value) {
if (root == nullptr) {
root = new TreeNode(value);
} else {
insertHelper(root, value);
}
}
private:
// 插入辅助函数
void insertHelper(TreeNode*& node, int value) {
if (value < node->val) {
if (node->left == nullptr) {
node->left = new TreeNode(value);
} else {
insertHelper(node->left, value);
}
} else {
if (node->right == nullptr) {
node->right = new TreeNode(value);
} else {
insertHelper(node->right, value);
}
}
}
// 查找节点并返回其父节点
TreeNode* findParent(TreeNode* node, int target) {
if (node == nullptr || node->val == target) return nullptr;
if (target < node->val) {
return findParent(node->left, target);
} else {
return findParent(node->right, target);
}
}
TreeNode* root; // 树根节点
};
// 测试函数
int main() {
BinaryTree tree;
tree.insert(50); // 插入根节点
tree.insert(30);
tree.insert(70);
tree.insert(20);
tree.insert(40);
tree.insert(60);
// 测试查找
int search_value = 40;
TreeNode* parent = tree.findParent(tree.root, search_value);
if (parent != nullptr) {
std::cout << "找到节点 " << search_value << " 的父节点: " << parent->val << std::endl;
} else {
std::cout << "未找到节点 " << search_value << std::endl;
}
return 0;
}
```
在这个例子中,`findParent` 函数会在给定的节点值 `target` 下寻找它的父节点。如果找到,返回指向父节点的引用;否则返回 `nullptr`。
阅读全文