数据结构--二叉查找树頭條網

2021-04-05 06:58:38 佚名

1.二叉查找树的定义

对于树中的每个节点X,它的左子树中所有关键字值小于X的关键字值，而它的右子树中所有关键字值大于X的关键字值。

2.主要实现插入，删除等操作，代码如下：

<code> 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
typedef
 
struct
 _tagST{
    
    int data;
    
struct
 _tagST
* left;
    
struct
 _tagST
* right;
    
}SerachTree;
 
 
 
SerachTree* 
STCreate
();
 
 
SerachTree* 
STInsert
(SerachTree* t,
int data);
 
 
SerachTree* 
STDelete
(SerachTree* t,
int data);
 
 
SerachTree* 
STFind
(SerachTree* t,
int data);
 
 
SerachTree* 
STFindMin
(SerachTree* t);
 
 
SerachTree* 
STFindMax
(SerachTree* t);
 
 
void
 STDestroy
(SerachTree* t);
 
/<code>

<code> 
 
 
 
 
 
 
 
 
 
static SerachTree* MakeEmpty(SerachTree* t){
    if
 (t != NULL) {
        MakeEmpty(t->left);
        MakeEmpty(t->right);
        free(t);
        t = NULL;
    }
    
    return
 NULL;
}
 
 
 
SerachTree* STCreate(){
    return
 NULL;
}
 
 
SerachTree* STInsert(SerachTree* t,int data){
    if
 (t == NULL) {
        t = (SerachTree*)malloc(sizeof(SerachTree));
        if
 (t == NULL) {
            return
 NULL;
        }
        t->data = data;
        t->left = t->right = NULL;
    }
    else
 if (data < t->data){
        t->left = STInsert(t->left, data);
    }
    else
 if (data > t->data){
        t->right = STInsert(t->right, data);
    }
    
    return t;
}
 
 
SerachTree* STDelete(SerachTree* t,int data){
    if
 (t == NULL) {
        return
 NULL;
    }
    SerachTree* tmp = NULL;
    
    if (data < t->data) {
        t->left = STDelete(t->left, data);
    }
    else
 if (data > t->data){
        t->right = STDelete(t->right, data);
    }
    else{
        if (t->left && t->right) {  
             
            tmp = STFindMin(t);
            t->data = tmp->data;
            t->right = STDelete(t->right, data);   
        }
        else{   
            tmp = t;
            if
 (t->left == NULL) {
                t = t->right;
            }
            else
 if
 (t->right == NULL){
                t = t->left;
            }
 
            free(tmp);
            tmp = NULL;
        }
    }
    
    return t;
}
 
 
 
SerachTree* STFind(SerachTree* t,int data){
    if
 (t == NULL) {
        return
 NULL;
    }
    if (data < t->data) {
        return STFind(t->left, data);
    }
    else
 if (data > t->data){
        return STFind(t->right, data);
    }
    else{
        return t;
    }
}
 
 
SerachTree* STFindMin(SerachTree* t){
    if
 (t == NULL) {
        return
 NULL;
    }
    
    if
 (t->left == NULL) {
        return t;
    }
    else{
        return STFindMin(t->left);
    }
}
 
 
SerachTree* STFindMax(SerachTree* t){
    if
 (t == NULL) {
        return
 NULL;
    }
    SerachTree* tmp = t;
    while
 (tmp->right != NULL) {
        tmp = tmp->right;
    }
    return tmp;
}
 
 
 
void STDestroy(SerachTree* t){
    MakeEmpty(t);
}/<code>

<code> 
 
 
 
 
 
 
 
 
 
 
int
 main
(
int
 argc, const
 char * argv[]) {
     
    
    SerachTree * t = STCreate();
    
    for
 (int
 i = 0
; i 100; i++) {
        t = STInsert(t, i+1);
    }
    
    fprintf
(stderr
, "dd %d\n",t->data);
    
    SerachTree* f = STFind(t, 26);
    if
 (f == NULL) {
        fprintf
(stderr
, "没有找到结点\n");
        return
 -1;
    }
    fprintf
(stderr
, "%d\n",f->data);
 
    fprintf
(stderr
, "%d\n",f->right->data);
    
    t = STDelete(t, 100);
    t = STDelete(t, 0);
    t = STDelete(t, 3);
    
    SerachTree* minNode = STFindMin(t);
    if
 (minNode == NULL) {
        return
 -2;
    }
    fprintf
(stderr
, "min node = %d\n",minNode->data);
    
    SerachTree* maxNode = STFindMax(t);
    if
 (maxNode == NULL) {
        return
 -2;
    }
    fprintf
(stderr
, "max node = %d\n",maxNode->data);
    
    
    STDestroy(t);
    
    return
 0;
}/<code>