编写算法，在以二叉链表存储的二叉树中，已知某结点数据元素值x（该结点最多存在一个），求该结点的双亲结点。
得分点（必背）
代码语言：javascript复制//查找给定结点的双亲结点
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;
}题解
定义函数和初始化变量：
代码语言：javascript复制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。
处理特殊情况：
代码语言：javascript复制if (T == NULL || (T->left == NULL && T->right == NULL)) {
return NULL;
}如果树 T 为空，或者树只有根结点（没有左、右子结点），则直接返回 NULL，表示没有双亲结点。
遍历树：
代码语言：javascript复制while (P != NULL || top != -1) {使用 while 循环模拟递归遍历树，条件是当前结点 P 不为空或栈不为空（即 top != -1）。
中序遍历左子树：
代码语言：javascript复制 while (P != NULL) {
if (P->data == x) {
return Q;
}
STACK[ top] = P;
// 保存双亲结点
Q = P;
P = P->left;
}使用嵌套的 while 循环进行中序遍历的左子树。首先检查当前结点的值是否等于 x，如果是则返回 Q，即当前结点的双亲结点。否则，将当前结点 P 入栈，并保存 Q 为当前结点 P 的双亲结点，然后继续遍历左子树。
处理右子树：
代码语言：javascript复制 P = STACK[top--];
// 保存双亲结点
Q = P;
P = P->right;如果左子树遍历完毕，从栈中弹出一个结点，并处理其右子树。再次保存 Q 为当前结点 P 的双亲结点，然后继续遍历右子树。
返回结果：
代码语言：javascript复制return NULL;如果遍历完所有结点仍未找到值为 x 的结点，则返回 NULL，表示树中不存在该结点，或该结点是根结点没有双亲结点。
#include <iostream>
#define MAX_STACK 50
using 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;
}通过这个示例代码，可以创建一个二叉树并查找某个节点的双亲结点。
