二叉树的查找算法的实现与运用
这里我们需要运用到之前二叉树建立的知识点
每一次调用Insert函数时，都会开辟一个BiNode类型的空间，同时递归调用。其次，我们在建立平衡二叉树时，当前节点的左结点小于该结点，当前节点的右结点大于该结点，所以，我们在递归之前添加了一个判断条件。最后，Insert插入函数是一个返回BiNode结点类型的函数。
//构造函数
BiSortTree::BiSortTree(int a[], int n) {
root = NULL;
for (int i = 0; i < n; i++) {//递归调用二叉平衡树的的插入函数
root = InsertBST(root, a[i]);
}
}
//二叉平衡树的插入函数
BiNode* BiSortTree::InsertBST(BiNode* bt, int x) {
if (bt == NULL) {
BiNode* s = new BiNode;
s->data = x;
s->lchild = s->rchild = NULL;
bt = s;
return bt;
} else if (bt->data > x) {//bt->data指的是上一个结点的数据域
bt->lchild = InsertBST(bt->lchild, x);
} else {
bt->rchild = InsertBST(bt->rchild, x);
}
return bt;
}
平衡二叉树的删除函数
平衡二叉树的删除函数分为三种情况，情况1是被删结点是叶子结点，情况2是被删结点是有左子树或者右子树，情况3是被删结点既有左子树
又有右子树。
//二叉平衡树的删除函数
void BiSortTree::DeleteBST(BiNode* p, BiNode* f) {
if ((p->lchild == NULL) && (p->rchild == NULL)) {//情况1
f->rchild = NULL;
delete p;
return;
}
if (p->rchild == NULL) {//情况2
f->lchild = p->lchild;
delete p;
return ;
}
if (p->lchild == NULL) {//情况2
f->lchild = p->rchild;
delete p;
return;
}
//情况3
BiNode* par = p, *s = p->rchild;
while (s->lchild != NULL) {
par = s;
s = s->lchild;
}
p->data = s->data;
if (par == p) {
par->rchild = s->rchild;
} else {
par->lchild = s->rchild;
}
delete s;
cout << "DeleteBST删除成功！" << endl;
}