假设二叉树b采用二叉链存储结构，设计一个算法void findparent(BTNode *b,ElemType x,BTNode *&p)求指定值为x的结点的双亲结点p，提示，根结点的双亲为NULL，若未找到这样的结点，p亦为NULL。解：算法如下：

void findparent(BTNode *b, ElemType x, BTNode *&p) {
    if (b == NULL || (b->lchild == NULL && b->rchild == NULL)) {
        p = NULL;
        return;
    }
    if ((b->lchild != NULL && b->lchild->data == x) || (b->rchild != NULL && b->rchild->data == x)) {
        p = b;
        return;
    }
    findparent(b->lchild, x, p);
    if (p != NULL) {
        return;
    }
    findparent(b->rchild, x, p);
}

算法思路：

首先判断当前结点是否为空或为叶子结点，如果是，则返回NULL。然后判断当前结点的左右孩子是否为要查找的结点，如果是，则将当前结点作为要查找结点的双亲结点，返回。如果当前结点不是要查找的结点的双亲结点，则递归查找其左右子树，直到找到要查找的结点为止。

算法时间复杂度为O(n)，其中n为二叉树中结点的个数。

相关问题

以二叉链存储二叉树b，设计算法求二叉树的高度。 typedef struct node { ElemType data; struct node* lchild; struct node* rchild; }BTNode; int GetHeight(BTNode* b)

为了求解二叉树的高度，可以采用递归的方式，因为二叉树的高度就是其左右子树高度的最大值加1。以下是用给定的二叉链表示的结构体`BTNode`编写的一个算法：

int GetHeight(BTNode* b) {
    // 如果树为空，则高度为0
    if (b == NULL) {
        return 0;
    }
    
    // 分别计算左右子树的高度
    int left_height = GetHeight(b->lchild);
    int right_height = GetHeight(b->rchild);

    // 返回较大的那一边的高度加1（即当前节点的高度）
    return (left_height > right_height ? left_height + 1 : right_height + 1);
}

这个函数接受一个指向二叉树根节点的指针`b`，然后递归地访问左子树和右子树，直到找到空节点（表示到达叶节点或空树）。每次递归调用都会增加1来表示当前层级，所以最终返回的是整个树的高度。

如果你想要直接查看二叉树的高度而不是编写算法，可以遍历整棵树并记录深度，但在没有额外数据结构的情况下，递归是最直观且常用的方法。

试编写代码：对于二叉树中每一个元素值为x的结点，删除以它为根的子树，并释放相应空间。函数原型为：void delSub(bTNode* T, ElemType x)

我明白了，请给我一点时间编写这个函数。以下是代码实现：

typedef struct bTNode {
    ElemType data;
    struct bTNode *lchild, *rchild;
} bTNode, *bTree;

void delSub(bTNode* T, ElemType x) {
    if (T) {
        if (T->data == x) {
            if (T->lchild) {
                delSub(T->lchild, T->lchild->data);
                free(T->lchild);
                T->lchild = NULL;
            }
            if (T->rchild) {
                delSub(T->rchild, T->rchild->data);
                free(T->rchild);
                T->rchild = NULL;
            }
        } else {
            delSub(T->lchild, x);
            delSub(T->rchild, x);
        }
    }
}

这个函数可以先判断当前结点是否为要删除的结点。如果是，就递归释放左右子树，并将当前结点的左右孩子指针设为NULL。如果不是，就递归遍历左右子树。