c++以二叉链表为存储结构编写算法求二叉树中结点x的双亲

下面是求二叉树中某个结点 x 的双亲结点的 C++ 代码，假设二叉树的结点结构体定义如下：

struct BinaryTreeNode {
    int data; //结点数据
    BinaryTreeNode *left; //左子树指针
    BinaryTreeNode *right; //右子树指针
};

算法思路：

- 如果根结点就是 x 结点，则 x 结点没有双亲结点；
- 如果 x 结点是根结点的左子结点或右子结点，则根结点就是 x 结点的双亲结点；
- 否则，递归地在左子树和右子树中查找 x 结点的双亲结点。

代码实现：

BinaryTreeNode* FindParent(BinaryTreeNode* root, BinaryTreeNode* x) {
    if (root == nullptr || root == x) {
        return nullptr; //根结点就是 x 结点或者树为空，没有双亲结点
    }
    if (root->left == x || root->right == x) {
        return root; //x 结点是根结点的左子结点或右子结点，根结点就是 x 结点的双亲结点
    }
    BinaryTreeNode* parent = FindParent(root->left, x); //在左子树中查找
    if (parent != nullptr) {
        return parent; //在左子树中找到了，返回结果
    } else {
        return FindParent(root->right, x); //在右子树中查找
    }
}

其中，root 表示二叉树的根结点，x 表示要查找双亲结点的结点。函数返回值是 x 结点的双亲结点，如果 x 结点没有双亲结点则返回 nullptr。