假设二叉树b采用二叉链存储结构,设计一个算法void findparent(BTNode *b,ElemType x,BTNode *&p)求指定值为x的结点的双亲结点p,提示,根结点的双亲为NULL,若未找到这样的结点,p亦为NULL。解:算法如下:
时间: 2024-02-25 16:59:49 浏览: 25
```
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为二叉树中结点的个数。
相关问题
试编写代码:对于二叉树中每一个元素值为x的结点,删除以它为根的子树,并释放相应空间。函数原型为:void delSub(bTNode* T, ElemType x)
我明白了,请给我一点时间编写这个函数。以下是代码实现:
```c++
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。如果不是,就递归遍历左右子树。
删除值为d的二叉树节点 BTNode* Delete_bitTree(BTNode* root,ElemType d)
好的,针对你的问题,我可以给出以下的代码实现:
```
BTNode* Delete_bitTree(BTNode* root, ElemType d) {
if (root == NULL) {
return NULL;
}
if (root->data == d) {
if (root->left == NULL && root->right == NULL) {
delete root;
return NULL;
}
else if (root->left == NULL) {
BTNode* temp = root->right;
delete root;
return temp;
}
else if (root->right == NULL) {
BTNode* temp = root->left;
delete root;
return temp;
}
else {
BTNode* temp = root->right;
while (temp->left != NULL) {
temp = temp->left;
}
root->data = temp->data;
root->right = Delete_bitTree(root->right, temp->data);
return root;
}
}
else if (root->data > d) {
root->left = Delete_bitTree(root->left, d);
return root;
}
else {
root->right = Delete_bitTree(root->right, d);
return root;
}
}
```
该函数的作用是删除二叉树中值为 `d` 的节点。函数首先检查当前节点是否为 `NULL`,如果是,直接返回 `NULL`。如果当前节点的值等于 `d`,则根据其子节点的情况进行删除操作。如果当前节点没有子节点,直接删除并返回 `NULL`;如果只有一边有子节点,将该子节点替换当前节点并删除当前节点;如果两边都有子节点,找到当前节点右子树中最小的节点,将其值替换到当前节点中,再递归删除右子树中的最小节点。如果当前节点的值大于 `d`,则递归到左子树中查找;否则递归到右子树中查找。