c++ 二叉树查找指定结点的双亲和兄弟 并用主函数测试
时间: 2023-08-06 19:08:31 浏览: 205
好的,下面是实现代码:
```c++
#include <iostream>
using namespace std;
// 二叉树结点定义
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 查找指定结点的双亲结点
TreeNode* findParent(TreeNode* root, TreeNode* target) {
if (root == NULL) return NULL;
if (root->left == target || root->right == target) return root;
TreeNode* left = findParent(root->left, target);
if (left != NULL) return left;
return findParent(root->right, target);
}
// 查找指定结点的兄弟结点
TreeNode* findSibling(TreeNode* root, TreeNode* target) {
if (root == NULL) return NULL;
if (root->left == target) return root->right;
if (root->right == target) return root->left;
TreeNode* left = findSibling(root->left, target);
if (left != NULL) return left;
return findSibling(root->right, target);
}
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);
// 测试查找指定结点的双亲结点和兄弟结点
TreeNode* target = root->left->right;
TreeNode* parent = findParent(root, target);
TreeNode* sibling = findSibling(parent, target);
cout << "Target: " << target->val << endl;
if (parent != NULL) cout << "Parent: " << parent->val << endl;
else cout << "Parent: NULL" << endl;
if (sibling != NULL) cout << "Sibling: " << sibling->val << endl;
else cout << "Sibling: NULL" << endl;
return 0;
}
```
运行结果如下:
```
Target: 5
Parent: 2
Sibling: 4
```
上述代码中,我们使用了递归方式查找指定结点的双亲结点和兄弟结点,时间复杂度为 $O(n)$,其中 $n$ 为二叉树中结点的个数。
阅读全文