数据结构 二叉排序树的代码实现

7.8、二叉排序树（BST）

二叉排序树又称二叉查找树

• 左子树上所有结点的值都小于根结点的值
• 右子树上所有结点的值都大于根结点的值
• 左子树和右子树又是一颗二叉排序树

左子树的结点值 < 根结点值 < 右子树的结点值

插入的数据的递归实现

#include <stdio.h>
#include <stdlib.h>
#include<math.h>

#define MaxSize 100
#define ElemType int
#define boolean int
#define true 1
#define false 0

//定义一颗二叉排序树
typedef struct BSTNode{
    ElemType data;
    struct BSTNode *lchild,*rchild;
}BSTNode, *BSTree; 

//插入一个结点的递归实现
boolean BST_Insert(BSTree *T,ElemType k){
    if(*T == NULL){
        (*T) = (BSTree)malloc(sizeof(BSTNode));
        if((*T) == NULL) return false;
        (*T)->data = k;
        (*T)->lchild = NULL;
        (*T)->rchild = NULL;
    }else if( (*T)->data == k) {//树中有该值，不能插入相同的值
        return false;
    }else if((*T)->data < k){
        BST_Insert(&(*T)->rchild,k);
    }else{
        BST_Insert(&(*T)->lchild,k);
    }
    return true;
}

//访问结点
void Vist(BSTNode *node){
    printf("%d , ",node->data);
}
//中序遍历
void InOrder(BSTree T){
    if(T != NULL){
        InOrder(T->lchild);
        Vist(T);
        InOrder(T->rchild);
    }
}

int main(){
    BSTree T = NULL;
    BST_Insert(&T,19);
    BST_Insert(&T,13);
    BST_Insert(&T,50);
    BST_Insert(&T,11);
    BST_Insert(&T,12);
    BST_Insert(&T,26);
    BST_Insert(&T,21);
    BST_Insert(&T,30);
    BST_Insert(&T,66);
    BST_Insert(&T,60);
    BST_Insert(&T,70);

    //中序遍历
    printf("中序遍历二叉排序树：");
    InOrder(T);

    return 0;
}
//结果：
中序遍历二叉排序树：11 , 12 , 13 , 19 , 21 , 26 , 30 , 50 , 60 , 66 , 70 ,

非递归实现

#include <stdio.h>
#include <stdlib.h>
#include<math.h>

#define MaxSize 100
#define ElemType int
#define boolean int
#define true 1
#define false 0

//定义一颗二叉排序树
typedef struct BSTNode{
    ElemType data;
    struct BSTNode *lchild,*rchild;
}BSTNode, *BSTree; 

//插入一个结点的非递归实现
boolean BST_Insert1(BSTree *T,ElemType k){
    BSTNode *p = *T;
    BSTNode *pre;
    if(p == NULL){
        *T = (BSTNode*)malloc(sizeof(BSTNode));
        if(*T == NULL) return false;
        (*T)->data = k;
        (*T)->lchild = (*T)->rchild = NULL;
        return true;
    }
    while(p != NULL){
        if(p->data == k) return false;
        if(p->data < k){
            pre = p;
            p = p->rchild;
        }else{
            pre = p;
            p = p->lchild;
        }
    }
    BSTNode *q = (BSTNode*)malloc(sizeof(BSTNode));
    if(q == NULL) return false;
    q->data = k;
    q->lchild = q->rchild = NULL;
    if(pre->data < k){
        pre->rchild = q;
    }else{
        pre->lchild = q;
    }
    return true;
}


//访问结点
void Vist(BSTNode *node){
    printf("%d , ",node->data);
}
//中序遍历
void InOrder(BSTree T){
    if(T != NULL){
        InOrder(T->lchild);
        Vist(T);
        InOrder(T->rchild);
    }
}

int main(){
    BSTree T = NULL;
    BST_Insert1(&T,19);
    BST_Insert1(&T,13);
    BST_Insert1(&T,50);
    BST_Insert1(&T,11);
    BST_Insert1(&T,12);
    BST_Insert1(&T,26);
    BST_Insert1(&T,21);
    BST_Insert1(&T,30);
    BST_Insert1(&T,66);
    BST_Insert1(&T,60);
    BST_Insert1(&T,70);

    //中序遍历
    printf("中序遍历二叉排序树：");
    InOrder(T);

    return 0;
}
//结果：
中序遍历二叉排序树：11 , 12 , 13 , 19 , 21 , 26 , 30 , 50 , 60 , 66 , 70 , 

删除操作

BSTNode *pre = NULL;//需要删除结点的前驱结点

boolean flag = 0;//0表示左子树进入 1表示右子树进入
BSTNode * BSTInOrder(BSTree T){//寻找最子树的中序遍历第一个结点
    if(T->lchild == NULL){
        return T;
    }
    return BSTInOrder(T->lchild);
}
//删除结点
boolean BST_DeleteNode(BSTree *T,ElemType e){
    if((*T) == NULL) return false;
    if((*T)->data == e){
        if((*T)->lchild == NULL && (*T)->rchild == NULL){//1.它是叶子结点
            (*T) = NULL;
        }else if((*T)->lchild == NULL){//2.删除结点的左子树为空
            if(flag){
                pre->rchild = (*T)->rchild;
            }else{
                pre->lchild = (*T)->rchild;
            }
        }else if((*T)->rchild == NULL){//3.删除结点的右子树为空
            if(flag){
                pre->rchild = (*T)->lchild;
            }else{
                pre->lchild = (*T)->lchild;
            }
        }else{//4.如果即有左子树又有右子树
            BSTNode *p = BSTInOrder((*T)->rchild);//寻找右子树的最小结点
            (*T)->data = p->data;//修改删除结点值
            BST_DeleteNode(&(*T)->rchild,p->data);//删除右子树的最小结点
        }
        return true;
    }

    pre = *T;
    if((*T)->data < e){
        flag = 1;
        BST_DeleteNode(&(*T)->rchild,e);
    }else if((*T)->data > e){
        flag = 0;
        BST_DeleteNode(&(*T)->lchild,e);
    }
}


int main(){
    BSTree T = NULL;
    BST_Insert1(&T,19);
    BST_Insert1(&T,13);
    BST_Insert1(&T,50);
    BST_Insert1(&T,11);
    BST_Insert1(&T,12);
    BST_Insert1(&T,26);
    BST_Insert1(&T,21);
    BST_Insert1(&T,30);
    BST_Insert1(&T,66);
    BST_Insert1(&T,60);
    BST_Insert1(&T,70);
    BST_Insert1(&T,68);

    //中序遍历
    printf("中序遍历二叉排序树：");
    InOrder(T);

    BST_DeleteNode(&T,50);
    //中序遍历
    printf("\n删除后中序遍历二叉排序树：");
    InOrder(T);

    return 0;
}

//结果：
中序遍历二叉排序树：11 , 12 , 13 , 19 , 21 , 26 , 30 , 50 , 60 , 66 , 68 , 70 , 
删除后中序遍历二叉排序树：11 , 12 , 13 , 19 , 21 , 26 , 30 , 60 , 66 , 68 , 70 , 

ASL（Average Search Length）