利用编程思维做题之求节点 x 在二叉树中的双亲节点算法
在二叉树中查找某个节点 x 的双亲节点是一个典型的树操作问题。双亲节点的概念是指某个节点的直接上级节点，即它的父节点。我们将通过遍历树的结构，查找并返回 x 的双亲节点。
1. 理解问题
我们需要设计一个算法来查找给定二叉树中节点 x 的双亲节点。目标是通过遍历树结构，找到 x 的父节点。如果 x 是根节点，或者不存在于树中，则返回 NULL。
示例：
假设我们有如下的二叉树：
5
/ \
3 7
/ \ / \
2 4 6 8
如果我们查找节点 4 的双亲节点，则返回节点 3。
如果我们查找节点 5 的双亲节点，结果应为 NULL，因为 5 是根节点。
如果我们查找一个不存在的节点，结果也应为 NULL。
关键点：
-
递归遍历：我们将使用递归方式遍历树，检查每个节点是否为目标节点 x 的父节点。
-
特殊处理根节点：如果查询的节点为根节点（没有双亲），直接返回
NULL。
2. 输入输出
输入：
-
root：指向二叉树根节点的指针，表示二叉树的起始节点。 -
x：要查找其双亲节点的目标节点。
输出：
-
返回值：若节点 x 的双亲节点存在，返回该节点的指针；否则返回
NULL。
3. 二叉树结构
二叉树节点的定义如下：
struct TreeNode {
int data; // 节点的值
struct TreeNode* left; // 指向左子节点的指针
struct TreeNode* right; // 指向右子节点的指针
};
4. 制定策略
为实现查找二叉树节点双亲节点的算法，我们可以使用递归遍历的方法。在遍历过程中，检查当前节点的左子节点和右子节点是否为目标节点 x。如果是，则返回当前节点作为 x 的双亲节点。
关键步骤：
-
递归遍历：从根节点开始递归遍历二叉树，依次检查每个节点的左右子节点。
-
检查左右子节点：如果当前节点的左子节点或右子节点等于目标节点 x，则返回当前节点作为 x 的双亲节点。
-
递归向下查找：如果当前节点不是双亲节点，递归查找左右子树，直到找到 x 的双亲节点为止。
5. 实现代码
5.1 关键函数实现
// 定义二叉树节点
struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
};
// 查找节点 x 的双亲节点
struct TreeNode* findParent(struct TreeNode* root, struct TreeNode* x) {
// 如果树为空或 x 是根节点，则返回 NULL
if (root == NULL || root == x) return NULL;
// 如果当前节点的左子节点或右子节点是 x，则当前节点是 x 的双亲
if (root->left == x || root->right == x) {
return root;
}
// 递归查找左子树
struct TreeNode* leftResult = findParent(root->left, x);
// 这里判断不等于NULL的作用：在左子树中找到了就返回，否则就递归右子树返回结果，仅且返回一个
if (leftResult != NULL) {
return leftResult;
}
// 递归查找右子树
return findParent(root->right, x);
}
5.2 完整c代码
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树节点结构
struct TreeNode {
int data; // 节点的数据
struct TreeNode* left; // 指向左子节点的指针
struct TreeNode* right; // 指向右子节点的指针
};
// 创建一个新节点
struct TreeNode* createNode(int data) {
struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode)); // 分配内存给新节点
newNode->data = data; // 设置节点的数据
newNode->left = NULL; // 初始化左子节点为 NULL
newNode->right = NULL; // 初始化右子节点为 NULL
return newNode; // 返回新节点
}
// 查找节点 x 的双亲节点
struct TreeNode* findParent(struct TreeNode* root, struct TreeNode* x) {
// 如果树为空或 x 是根节点，则返回 NULL
if (root == NULL || root == x) return NULL;
// 如果当前节点的左子节点或右子节点是 x，则当前节点是 x 的双亲
if (root->left == x || root->right == x) {
return root;
}
// 递归查找左子树
struct TreeNode* leftResult = findParent(root->left, x);
// 如果在左子树中找到了双亲节点，则返回该节点
if (leftResult != NULL) {
return leftResult;
}
// 递归查找右子树
return findParent(root->right, x);
}
// 打印双亲节点信息
void printParent(struct TreeNode* parent, struct TreeNode* node) {
if (parent != NULL) {
printf("节点 %d 的双亲是 %d\n", node->data, parent->data);
} else {
printf("节点 %d 没有双亲（它是根节点）\n", node->data);
}
}
int main() {
// 创建二叉树的节点
struct TreeNode* root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
root->right->left = createNode(6);
root->right->right = createNode(7);
// 查找某个节点的双亲节点
struct TreeNode* node = root->left->right; // 查找节点 5 的双亲
struct TreeNode* parent = findParent(root, node);
// 打印结果
printParent(parent, node);
return 0;
}
5.3 代码说明
findParent(struct TreeNode* root, struct TreeNode* x)：查找某个节点 x 的双亲节点。
-
如果当前节点是空或
x本身是根节点，返回NULL。 -
如果当前节点的左子节点或右子节点是
x，则返回当前节点，即x的双亲。 -
如果左子树中找到了双亲节点，直接返回结果，否则递归查找右子树。
5.4 模拟过程
二叉树结构：
5
/ \
3 7
/ \ / \
2 4 6 8
Step 1: 查找节点 4 的双亲节点
-
从根节点 5 开始查找，节点 5 的左子节点是 3，右子节点是 7，都不是目标节点 4。
-
递归查找左子树，节点 3 的左子节点是 2，右子节点是 4。此时找到了目标节点 4，返回节点 3 作为双亲节点。
结果：节点 4 的双亲节点是 3。
Step 2: 查找节点 7 的双亲节点
-
从根节点 5 开始查找，节点 5 的右子节点是 7，找到了目标节点 7，返回根节点 5 作为双亲节点。
结果：节点 7 的双亲节点是 5。
Step 3: 查找不存在的节点（如 9）
-
从根节点 5 开始查找，递归查找左右子树均未找到目标节点，最终返回
NULL。
结果：节点 9 不存在，返回 NULL。
6. 运行结果
- 查找节点 4 的双亲节点：返回节点 3。
- 查找节点 7 的双亲节点：返回节点 5。
- 查找不存在的节点（如 9）：返回
NULL。
7. 时间和空间复杂度分析
时间复杂度：O(n)
在最坏情况下，算法需要遍历整个二叉树中的所有节点，因此时间复杂度为 O(n)，其中 n 为树中节点的总数。
空间复杂度：O(h)
由于递归调用栈的深度最多为树的高度 h，因此空间复杂度为 O(h)，其中 h 为二叉树的高度。在平衡二叉树中，h = O(log n)，而在最坏情况下（如链状树），h = O(n)。
8. 总结
通过递归遍历二叉树，可以有效地查找目标节点的双亲节点。如果树结构较为复杂，递归的方法也能较为清晰地处理问题。
原文地址：https://blog.csdn.net/qq_39178993/article/details/142881017
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！