BiTree Search_BST(BiTree T, KeyType key, BiTNode **parent) {/*在二叉排序树T上查找其关键字等于key的记录结点。若找到返回该结点指针,parent指向其双亲;否则返回空指针,parent指向访问路径上最后一个结点。*/
时间: 2024-03-27 20:36:11 浏览: 48
二叉查找树BST,可以看看
下面是一个找到二叉排序树中关键字等于key的节点的函数 Search_BST 的实现,其中 parent 指向其双亲节点,如果没有找到则指向访问路径上最后一个节点(即最后一次比较的节点)。
```c++
typedef int KeyType; // 假设关键字为整型数
typedef struct BiTNode {
KeyType data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
BiTree Search_BST(BiTree T, KeyType key, BiTNode **parent) {
BiTNode *p = T, *pre = nullptr; // p指向当前节点,pre指向其父节点
while (p) {
if (p->data == key) {
*parent = pre; // 找到节点,将其双亲节点指针记录下来
return p;
} else if (p->data > key) {
pre = p; // 记录访问路径上的最后一个节点(其父节点)
p = p->lchild;
} else {
pre = p;
p = p->rchild;
}
}
*parent = pre; // 没有找到,将最后一次比较的节点指针记录下来
return nullptr;
}
```
在该函数中,我们用 p 指向当前节点,pre 指向其父节点,在每次比较时都需要更新 pre 的值。如果找到了关键字等于 key 的节点,我们将其双亲节点指针记录下来并返回该节点的指针;如果没有找到,我们将最后一次比较的节点指针记录下来并返回空指针。
阅读全文