目录
第3题 查找给定结点的双亲结点（二叉树）
得分点（必背）
题解
定义函数和初始化变量：
处理特殊情况：
遍历树：
中序遍历左子树：
处理右子树：
返回结果：
🌈 嗨，我是命运之光！
🌌 2024，每日百字，记录时光，感谢有你，携手前行~
🚀 携手启航，我们一同深入未知的领域，挖掘潜能，让每一步成长都充满意义。
第3题 查找给定结点的双亲结点（二叉树）
编写算法，在以二叉链表存储的二叉树中，已知某结点数据元素值x（该结点最多存在一个），求该结点的双亲结点。
得分点（必背）
//查找给定结点的双亲结点
TreeNode* Find_X_Parent(TreeNode* T, int x){TreeNode* STACK[MAX_STACK];//用于保存当前结点的双亲结点TreeNode* Q=NULL;TreeNode* P=T;int top=-1;//判断特殊情况//如果树为空，或只有根结点，则无双亲结点if(T==NULL||(T->left==NULL&&T->right==NULL)){return NULL;}while(P!=NULL||top!=-1){//中序遍历左子树while(P!=NULL){if(P->data==x){return Q;}STACK[++top]=P;//保存双亲结点Q=P;P=P->left;}P=STACK[top--];//保存双亲结点Q=P;P=P->right;}return NULL;
}题解
定义函数和初始化变量：
TreeNode* Find_X_Parent(TreeNode* T, int x) {TreeNode* STACK[MAX_STACK];TreeNode* Q = NULL; // 用于保存当前结点的双亲结点TreeNode* P = T;int top = -1;
该函数 Find_X_Parent 用于在二叉树 T 中查找值为 x 的结点的双亲结点。函数首先定义了一个栈 STACK，用于模拟递归调用栈，并定义了指针 Q 和 P。Q 用于保存当前结点的双亲结点，P 用于遍历树。top 是栈顶指针，初始化为 -1。
处理特殊情况：
if (T == NULL || (T->left == NULL && T->right == NULL)) {return NULL;
}
如果树 T 为空，或者树只有根结点（没有左、右子结点），则直接返回 NULL，表示没有双亲结点。
遍历树：
while (P != NULL || top != -1) {
使用 while 循环模拟递归遍历树，条件是当前结点 P 不为空或栈不为空（即 top != -1）。
中序遍历左子树：
while (P != NULL) {if (P->data == x) {return Q;}STACK[++top] = P;// 保存双亲结点Q = P;P = P->left;}
使用嵌套的 while 循环进行中序遍历的左子树。首先检查当前结点的值是否等于 x，如果是则返回 Q，即当前结点的双亲结点。否则，将当前结点 P 入栈，并保存 Q 为当前结点 P 的双亲结点，然后继续遍历左子树。
处理右子树：
P = STACK[top--];// 保存双亲结点Q = P;P = P->right;
如果左子树遍历完毕，从栈中弹出一个结点，并处理其右子树。再次保存 Q 为当前结点 P 的双亲结点，然后继续遍历右子树。
返回结果：
return NULL;
如果遍历完所有结点仍未找到值为 x 的结点，则返回 NULL，表示树中不存在该结点，或该结点是根结点没有双亲结点。
#include <iostream>
#define MAX_STACK 50using namespace std;// 定义二叉树结点结构
struct TreeNode {int data;TreeNode* left;TreeNode* right;
};// 创建一个新结点
TreeNode* newNode(int data) {TreeNode* node = new TreeNode();node->data = data;node->left = node->right = NULL;return node;
}// 查找给定结点的双亲结点
TreeNode* Find_X_Parent(TreeNode* T, int x);int main() {// 创建示例二叉树TreeNode* root = newNode(1);root->left = newNode(2);root->right = newNode(3);root->left->left = newNode(4);root->left->right = newNode(5);root->right->left = newNode(6);root->right->right = newNode(7);int x = 5;TreeNode* parent = Find_X_Parent(root, x);if (parent != nullptr) {cout << "节点 " << x << " 的双亲结点是: " << parent->data << endl;} else {cout << "节点 " << x << " 没有双亲结点（可能是根结点或不存在于树中）。" << endl;}return 0;
}
通过这个示例代码，可以创建一个二叉树并查找某个节点的双亲结点。
嗨，我是命运之光。如果你觉得我的分享有价值，不妨通过以下方式表达你的支持：👍 点赞来表达你的喜爱，📁 关注以获取我的最新消息，💬 评论与我交流你的见解。我会继续努力，为你带来更多精彩和实用的内容。
点击这里👉 ，获取最新动态，⚡️ 让信息传递更加迅速。
