树表的查找 -- 二叉排序树

二叉排序树数据定义?

// 二叉排序树
typedef struct node {
?? ?KeyType key;
?? ?InfoType data;
?? ?struct node* lchild, * rchild;
}BSTNode;

插入

//插入
bool InsertBST(BSTNode*& bt, KeyType k)
{
?? ?//空树
?? ?if (bt == NULL)
?? ?{
?? ??? ?bt = (BSTNode*)malloc(sizeof(BSTNode));
?? ??? ?bt->key = k;
?? ??? ?bt->lchild = bt->rchild = NULL;
?? ??? ?return true;
?? ?}
?? ?//寻找并插入
?? ?else if (k == bt->key)
?? ??? ?return false;
?? ?else if (k < bt->key)
?? ??? ?return InsertBST(bt->lchild, k);
?? ?else
?? ??? ?return InsertBST(bt->rchild, k);
}

创建

//创建
BSTNode* CreateBST(KeyType A[], int n)
{
?? ?BSTNode* bt = NULL;
?? ?int i = 0;
?? ?while (i < n)
?? ?{
?? ??? ?InsertBST(bt, A[i]);
?? ??? ?i++;
?? ?}
?? ?return bt;
}

查找

//查找
BSTNode* SearchBST(BSTNode* bt, KeyType k)
{
?? ?if (bt == NULL || bt->key == k)
?? ??? ?return bt;
?? ?if (k < bt->key)
?? ??? ?return SearchBST(bt->lchild, k);
?? ?else
?? ??? ?return SearchBST(bt->rchild, k);
}

应用

找双亲结点

// 找双亲
BSTNode* SearchBST1(BSTNode* bt, KeyType k, BSTNode* f1, BSTNode*& f) //找到，f找回双亲，否则NULL
{
?? ?//SearchBST1(bt, x, NULL, f); f1 作中间参数，用于求f，初始为NULL
?? ?if (bt == NULL)
?? ?{
?? ??? ?f = NULL; //返回空
?? ??? ?return NULL;
?? ?}
?? ?else if (k == bt->key)
?? ?{
?? ??? ?f = f1; //找到了 记录
?? ??? ?return bt;
?? ?}
?? ?else if (k < bt->key)
?? ??? ?return SearchBST1(bt->lchild, k, bt, f); //f1始终为上一次遍历的，即父节点
?? ?else
?? ??? ?return SearchBST1(bt->rchild, k, bt, f);
}

找左子树最大 和 右子树最小

//找左子树最大 和 右子树最小
KeyType maxnode(BSTNode* p)
{
?? ?while (p->rchild != NULL)
?? ??? ?p = p->rchild;
?? ?return p->data;
}
KeyType minnode(BSTNode* p)
{
?? ?while (p->lchild != NULL)
?? ??? ?p = p->lchild;
?? ?return p->data;
}
void maxminnode(BSTNode* p)
{
?? ?if (p != NULL)
?? ?{
?? ??? ?if (p->lchild != NULL)
?? ??? ??? ?cout << "左子树的最大结点为" << maxnode(p->lchild);
?? ??? ?if (p->rchild != NULL)
?? ??? ??? ?cout << "右子树的最小结点为" << minnode(p->rchild);
?? ?}
}

删除

//删除原理
/*
void deletep(BSTNode* p)
{
?? ?BSTNode* q;
?? ?q = p;
?? ?p = p->rchild;
?? ?free(q);
}
bool deletek(BSTNode*& bt, KeyType k)
{
?? ?if (bt != NULL)
?? ?{
?? ??? ?if (k == bt->key)
?? ??? ?{
?? ??? ??? ?deletep(bt);
?? ??? ??? ?return true;
?? ??? ?}
?? ??? ?else if (k < bt->key)
?? ??? ??? ?deletek(bt->lchild, k);
?? ??? ?else
?? ??? ??? ?deletek(bt->rchild, k);
?? ?}
?? ?else
?? ??? ?return false;
}
*/

void Delete1(BSTNode* p, BSTNode*& r)
{
?? ?BSTNode* q;
?? ?if (r->rchild != NULL) //找到最右下结点
?? ??? ?Delete1(p, r->rchild);
?? ?else //找到了最右下结点
?? ?{
?? ??? ?p->key = r->key; //存值存关键字
?? ??? ?p->data = r->data;
?? ??? ?q = r; //记录位置
?? ??? ?r = r->lchild;//向下延顺
?? ??? ?free(q);//删除
?? ?}
}
void Delete(BSTNode*& p)
{
?? ?BSTNode* q;

?? ?if (p->rchild == NULL)
?? ?{
?? ??? ?q = p; //q记录位置
?? ??? ?p = p->lchild; //p往下延顺
?? ??? ?free(q); //释放
?? ?}
?? ?else if (p->lchild == NULL)
?? ?{
?? ??? ?q = p;
?? ??? ?p = p->rchild;
?? ??? ?free(q);
?? ?}
?? ?else
?? ??? ?Delete1(p, p->lchild); //左右子树都不空
}
bool DeleteBST(BSTNode*& bt, KeyType k)
{
?? ?//空树 不可删除
?? ?if (bt == NULL)
?? ??? ?return false;
?? ?else
?? ?{
?? ??? ?if (k < bt->key)
?? ??? ??? ?return DeleteBST(bt->lchild, k);
?? ??? ?else if (k > bt->key)
?? ??? ??? ?return DeleteBST(bt->rchild, k);
?? ??? ?// 找到该值
?? ??? ?else
?? ??? ?{
?? ??? ??? ?Delete(bt);
?? ??? ??? ?return true;
?? ??? ?}
?? ?}
}