你能用C++以二叉链表为存储结构,编写算法求二叉树中结点x的双亲
时间: 2024-06-09 18:05:38 浏览: 116
二叉树实现源码(数据结构、C++语言)
可以,以下是C++代码:
```c++
#include <iostream>
using namespace std;
// 二叉树结点的定义
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
};
// 求二叉树中结点x的双亲
TreeNode* getParent(TreeNode* root, TreeNode* x) {
if (root == nullptr || root == x) {
return nullptr;
}
if (root->left == x || root->right == x) {
return root;
}
TreeNode* parent = getParent(root->left, x);
if (parent == nullptr) {
parent = getParent(root->right, x);
}
return parent;
}
int main() {
// 创建一棵二叉树
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
root->right->left = new TreeNode(6);
root->right->right = new TreeNode(7);
// 求结点5的双亲
TreeNode* parent = getParent(root, root->left->right);
if (parent != nullptr) {
cout << "结点5的双亲为:" << parent->val << endl;
} else {
cout << "结点5没有双亲!" << endl;
}
return 0;
}
```
这里假设二叉树是已知的,并且输入的结点x在二叉树中。如果x不在二叉树中,需要进行额外的判断。
阅读全文