二叉排序树的相关操作
文章目录
- 二叉排序树的相关操作
-
- @[toc]
- 一：二叉排序树的构建
- 二：二叉排序树的搜索
-
- 1、递归查找目标结点，并返回地址
- 2、查找
- 三：插入操作
- 四：遍历
- 五：删除结点
- 六：主函数
- @[toc]
- 一：二叉排序树的构建
- 二：二叉排序树的搜索
-
- 1、递归查找目标结点，并返回地址
- 2、查找
- 三：插入操作
- 四：遍历
- 五：删除结点
- 六：主函数
一：二叉排序树的构建
/**
* 二叉排序树的构建
* @param T
* @param array 数组
* @param numsize 数组长度
* @return
*/
int CreatBSTTree(BSTTree* T,int* array,int numsize){
*T = NULL;
for (int i = 0; i < numsize; ++i) {
InsertBST(T,array[i]);
}
return 1;
}
二：二叉排序树的搜索
1、递归查找目标结点，并返回地址
/**
* 查找关键节点，并返回查找到的位置，否则为null
* @param T
* @param ele
* @return
*/
BSTTree SearchBST_1(BSTTree T,ElemType_BST ele){
if (T!=NULL){
if (ele == T->data){
return T;
} else if (ele>T->data){
return SearchBST_1(T->rchild,ele);
} else if (ele<T->data){
return SearchBST_1(T->lchild,ele);
}
} else{
return NULL;
}
}
2、查找
/**
* 在T所指向的二叉排序中递归查找关键字等于ele的数据元素，若查找成功，则指针p指向该数据元素结点，并返回1，
* 否则，p指向的是该条查找路径上的最后一个结点并返回0，指针f为指针T的双亲，初始值为NULL
* @param T
* @param ele
* @param f
* @param p
* @return
*/
int SearchBST_2(BSTTree T,ElemType_BST ele,BSTTree f,BSTTree* p){
if (!T){
*p=f;
return 0;
} else if (ele == T->data){
*p = T;
return 1;
} else if (ele > T->data){
return SearchBST_2(T->rchild,ele,T,p);
} else if (ele< T->data){
return SearchBST_2(T->lchild,ele,T,p);
}
}
三：插入操作
/**
* 插入之前，先进行查找，因为，我们使用二叉排序树是就是为了查找一个元素，那么当该元素不在树中时，
* 便需要将结点插入，而插入的路径就是查找路径
* 插入元素
* @param T
* @param ele
* @return
*/
int InsertBST(BSTTree* T,ElemType_BST ele){
BSTTree p;
if (!SearchBST_2(*T,ele,NULL,&p)){
BSTTree s = (BSTTree)malloc(sizeof (BSTNode));
s->data = ele;
s->lchild = NULL;
s->rchild = NULL;
if (!p){ //表示当前待插入的排序树，一个节点都没有，带插入节点为根节点
*T = s;
} else if (p->data > ele){
p->lchild = s;
} else{
p->rchild = s;
}
return 1;
} else{
return 0;
}
}
四：遍历
使用中序遍历遍历二叉排序树可以得到一个有序的数列
/**
* 中序遍历会得到一个有序的序列
*/
void BSTInOrder(BSTTree T){
if (T){
BSTInOrder(T->lchild);
printf("\t%d",T->data);
BSTInOrder(T->rchild);
}
}
五：删除结点
/**
* 删除操作的入口函数
* @param T
* @param ele
* @return
*/
int BSTDelete(BSTTree *T,ElemType_BST ele){
if (!(*T)){
return 0;
} else{
if ((*T)->data == ele){
return Delete(T);
} else if ((*T)->data > ele){
return BSTDelete(&(*T)->lchild,ele);
} else{
return BSTDelete(&(*T)->rchild,ele);
}
}
}
/**
* 删除一个结点，使之删除之后仍然是一个二叉排序树
* 1、如果待删除结点p是叶子节点，则直接删除
* 2、如果待删除节点p只有左孩子或者右孩子，那么删除之后，将p结点的左孩子作为p双亲结点的左孩子，或者将p结点
* 的右孩子作为p双亲结点的右孩子
* 3、如果p节点同时有左孩子和右孩子，那么有以下两种操作方式：
* 1、令结点p的左子树作为其双亲结点的左子树；结点p的右子树作为其自身直接前驱结点到右子树
* 2、用节点p的直接前驱（或者直接后继）来代替p结点，同时在二叉排序树中对其前驱结点（或直接后继）结点做删除操作。
* （本代码中使用第2种方法）
*
* @param T
* @return
*/
int Delete(BSTTree *p){
BSTTree q,s; //s来表示待删除结点p的前驱节点，q表示s的双亲结点
if ((*p)->lchild == NULL &&(*p)->rchild == NULL){ //叶子节点，直接删除
q = (*p);
free(q);
} else if (!(*p)->rchild){ //表示右子树为空，左子树不为空
(*p)->data = (*p)->lchild->data;
(*p)->lchild = NULL;
free((*p)->lchild);
} else if (!(*p)->lchild){ //表示左子树为空，右子树不为空
(*p)->data = (*p)->rchild->data;
(*p)->rchild = NULL;
free((*p)->rchild);
} else{ //左右子树借不为空，使用第二种方式
//寻找当前节点的前驱节点
q = *p;
s = q->lchild;
while (s->rchild){
q = s;
s = s->rchild;
}
//赋值
(*p)->data = s->data;
//s必然没有右子树，只需要判断s是否有左子树
if (s->lchild!=NULL){
s->data = s->lchild->data;
s->lchild = NULL;
free(s->lchild);
} else{
if (q!=(*p)){
q->rchild = NULL;
free(s);
} else{
q->lchild = NULL;
free(s);
}
}
}
return 1;
}
对于删除操作，详细的解析可以看这篇博客：
二叉排序树
六：主函数
void main(){
BSTTree Tree;
int array[] = {7,3,9,1,5,8,10,2,4,6,11};
CreatBSTTree(&Tree,array,sizeof (array)/4);
printf("the PreBST:");
BSTPreOrder(Tree);
printf("\n");
printf("the inBSTOrder:");
BSTInOrder(Tree);
printf("\n");
BSTTree node = SearchBST_1(Tree,7);
if (node){
printf("node:%d\n",node->data);
if (node->rchild){
printf("node's child:%d\n",node->rchild->data);
}
}
// Delete(&node);
// BSTInOrder(Tree);
BSTDelete(&Tree,5);
printf("After delete:");
BSTInOrder(Tree);
printf("\n");
}
结果展示：
测试二叉排序树：
