利用编程思维做题之求节点 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)!