抽象数据类型（ADT）---二叉搜索树

发表于 更新于 分类于 阅读次数：

二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。二叉搜索树作为一种经典的数据结构，它既有链表的快速插入与删除操作的特点，又有数组快速查找的优势；所以应用十分广泛，例如在文件系统和数据库系统一般会采用这种数据结构进行高效率的排序与检索操作。

二叉树ADT

  从定义二叉树的常规内容开始，该定义假设树中不包含相同的项目，很多操作与列表操作相同。不同之处在于数据的层次性安排。

二叉搜索树是能够高效地进行如下操作的数据结构。
1.插入一个数值
2.查询是否包含某个数值
3.删除某个数值

下面是有关此ADT的非正式总结

类型名称 二叉搜索树
类型属性： 二叉树或者是一个空的节点集合（空树），或者是一个指定某一节点为根的节点集合
每个节点有两个作为其后代的树，称为左子树和右子树
每一个子树本身又是一个二叉树，也包含它是个空树的可能性
二叉搜索树是有序的二叉树，它的每个节点也包含一个项目，它的左子树的项目排在根项目的前面，而跟项目在所有右子树项目的前面
类型操作: 把树初始化为空树
确定树是否为空
确定树是否已满
确定树中项目的个数
向树中添加一个项目
向树中删除一个项目
在树中搜索一个项目
访问树中一个项目
清空树

二叉搜索树的接口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/* tree.h -- 二叉搜索树 */
/* 树中不允许有相同的项目 */
#ifndef _TREE_H_
#define _TREE_H_
#include <stdio.h>
#include <stdbool.h>

typedef struct item      // 可自定义项目结构
{
    char petname[20];
    char petkind[20];
} Item;

typedef struct node
{
    Item item;
    struct node * left;    // 指向左分支的指针
    struct node * right;    // 指向右分支的指针
} Node;

typedef struct tree
{
    Node * root;     // 指向树根的指针
    int size;         //  树中项目个数
} Tree;

#define MAXITEMS 10

// 初始化生成树
void InitializeTree(Tree * ptree);

// 判断树是否为空
bool TreeIsEmpty(const Tree * ptree);

// 判断树是否满
bool TreeIsFull(const Tree * ptree);

// 确定树中的项目个数
int TreeItemCount(const Tree * ptree);

// 向树中添加一个项目
bool AddItem(const Item * pi, Tree * ptree);

// 向树中查找一个项目
bool InTree(const Item * pi, const Tree * ptree);

// 向树中删除一个项目
bool DeleteItem(const Item * pi, Tree * ptree);

// 通过函数作用于树中的每一个项目
void Traverse(const Tree * ptree, void (* pfun)(Item item));

// 删除所有节点
void DeleteAll(Tree * ptree);

#endif

二叉搜索树的实现

添加项目步骤

  1. 判断树是否已满，添加的项目重复
  2. 创建新节点
  3. 若根节点为NULL，则新节点为根节点，否则调用AddNode()函数

    添加节点步骤(AddNode)

  4. 判断添加的节点项目大于(小于)当前根节点
  5. 判断左（右）子树为空
  6. 若左（右）子树为空，添加新节点，否则递归调用AddNode，即回到第一步

    删除项目步骤

  7. 调用SeekItem查找要删除的目标函数，返回一个结构体地址（包含目标项目的节点和其根节点）
  8. 如果返回的节点为空，说明未找到目标项目。
  9. 判断其节点位置（左/右子树或根），调用 DeleteNode()
  10. 项目减一

    删除节点步骤(DeleteNode)

  11. 创建一个临时节点
  12. 若目标节点的左（右）节点为空/无节点，保存节点信息，右（左）节点取代父节点位置，释放节点
  13. 若目标节点的含有两个节点，循环，沿着左子树的最右分支查找空位置
  14. 把目标节点的右子树放到(依附)目标节点左子树的右分支空位置
  15. 左子树取代目标节点位置，释放目标节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
/* tree.c -- 树类型的支持函数 */
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include "tree.h"

// 局部数据类型
typedef struct pair {
    Node * parent;
    Node * child;
} Pair;

// 局部函数的原型

static Node * MakeNode(const Item * pi);
static bool ToLeft(const Item * i1, const Item * i2);
static bool ToRight(const Item * i1, const Item * i2);
static void AddNode(Node * new_node, Node * root);
static void InOrder(const Node * root, void (* pfun)(Item item));
static Pair SeekItem(const Item * pi, const Tree * ptree);
static void DeleteNode(Node **ptr);
static void DeleteAllNodes(Node * ptr);

// 函数定义

// 初始化生成树
void InitializeTree(Tree * ptree)
{
    ptree->root = NULL;
    ptree->size = 0;
}

// 判断树是否为空
bool TreeIsEmpty(const Tree * ptree)
{
    if(ptree->root == NULL)
        return true;
    else
        return false;
}

// 判断树是否满
bool TreeIsFull(const Tree * ptree)
{
    if(ptree->size == MAXITEMS)
        return true;
    else
        return false;
}

// 确定树中的项目个数
int TreeItemCount(const Tree * ptree)
{
    return ptree->size;
}

// 向树中添加一个项目
bool AddItem(const Item * pi, Tree * ptree)
{
    Node * new_node;

    if(TreeIsFull(ptree))    // 树是否满了
    {
        fprintf(stderr, "Tree is full\n");
        return false;
    }
    if(SeekItem(pi, ptree).child != NULL)   // 判断项目是否重复
    {
        fprintf(stderr, "Attempted to add duplicate item\n");
        return false;
    }
    new_node = MakeNode(pi);   // 创建新节点
    if(new_node == NULL)
    {
        fprintf(stderr, "Could't creat node\n");
        return false;
    }
    ptree->size++;   // 创建成功，size+1

    if(ptree->root == NULL)     // 树为空，新节点作为根节点
        ptree->root = new_node;  
    else                      // 树不为空，新节点加入数中
        AddNode(new_node, ptree->root); 
    return true;
}

// 向树中查找一个项目
bool InTree(const Item * pi, const Tree * ptree)
{
    return (SeekItem(pi, ptree).child == NULL) ? false : true;
}

// 向树中删除一个项目
bool DeleteItem(const Item * pi, Tree * ptree)
{
    Pair look;
    look = SeekItem(pi, ptree);  //查找，返回含两个指针的结构体

    if(look.child == NULL) // look.child为空，说明没有找到要删除的项目
        return false;       // look.child 为目标节点
    
    if(look.parent == NULL) // look.parent为空 说明目标节点是根节点
        DeleteNode(&ptree->root);
    else if(look.parent->left == look.child)
        DeleteNode(&look.parent->left);
    else
        DeleteNode(&look.parent->right);
    ptree->size--;
    return true;
}

// 通过函数作用于树中的每一个节点的项目
void Traverse(const Tree * ptree, void (* pfun)(Item item))
{
    if(ptree != NULL)
        InOrder(ptree->root, pfun);
}

// 删除所有节点
void DeleteAll(Tree * ptree)
{
    if(ptree != NULL)
        DeleteAllNodes(ptree->root);
    ptree->root = NULL;
    ptree->size = 0;
}

// 局部函数的实现

// 创建一个新的节点，并返回新节点地址 
static Node * MakeNode(const Item * pi)
{
    Node * new_node;

    new_node = (Node *)malloc(sizeof(Node));
    if(new_node != NULL)
    {
        new_node->item = *pi;  // 项目复制
        new_node->left = NULL;
        new_node->right = NULL;
    }
    return new_node;
}

// 判断目标项目在左分支树， 相当于 "<"
static bool ToLeft(const Item * i1, const Item * i2)
{
    int comp1;

    if((comp1 = strcmp(i1->petname, i2->petname)) < 0)
        return true;
    else if(comp1 == 0 && strcmp(i1->petkind, i2->petkind) < 0)
        return true;
    else
        return false;
}

// 判断目标项目在右分支树， 相当于 ">"
static bool ToRight(const Item * i1, const Item * i2)
{
    int comp1;

    if((comp1 = strcmp(i1->petname, i2->petname)) > 0)
        return true;
    else if(comp1 == 0 && strcmp(i1->petkind, i2->petkind) > 0)
        return true;
    else
        return false;
}

// 添加节点
static void AddNode(Node * new_node, Node * root)
{
    if(ToLeft(&new_node->item, &root->item))  // 添加的节点项目大于当前根节点
    {
        if(root->left == NULL)      // 空子树或左子树为空
            root->left = new_node;      // 添加节点到左子树
        else
            AddNode(new_node, root->left);     //  节点不为空，递归
    }
    else if(ToRight(&new_node->item, &root->item))   // 添加的节点项目小于当前根节点
    {
        if(root->right == NULL)       // 右子树为空
            root->right = new_node;    // 添加节点到右子树
        else
            AddNode(new_node, root->right);   // 节点不为空，递归
    }
    else   // 新节点项目相同
    { 
        fprintf(stderr, "location error in AddNode() \n");
        exit(EXIT_FAILURE);
    }
}

// 递归遍历二叉树
static void InOrder(const Node * root, void (* pfun)(Item item))
{
    if(root != NULL)
    {
        InOrder(root->left, pfun);
        (*pfun)(root->item);
        InOrder(root->right, pfun);
    }
}
static Pair SeekItem(const Item * pi, const Tree * ptree)
{
    Pair look;
    look.parent = NULL;
    look.child = ptree->root;

    if(look.child == NULL)   // 根节点为空
        return look;
    while(look.child != NULL)
    {
        if(ToLeft(pi, &(look.child->item)))    // 目标在左分支
        {
            look.parent = look.child;
            look.child = look.child->left;
        }
        else if(ToRight(pi, &(look.child->item)))    // 目标在左分支
        {
            look.parent = look.child;
            look.child = look.child->right;
        }
        else         // 前面两种都不是，就是相等的情况
            break;      //look.child是目标节点的地址
    }
    return look;
}
static void DeleteNode(Node **ptr)
{
    // ptr是指向目标节点的父节点指针成员的地址
    Node * temp;   // *ptr == temp
    puts((*ptr)->item.petname);

    if((*ptr)->left == NULL)   // 目标节点的左节点为空/无节点
    {
        temp = *ptr;      
        *ptr = (*ptr)->right;  // 右节点取代父节点位置
        free(temp);
    }
    else if((*ptr)->right == NULL) // 目标节点的右节点为空
    {
        temp = *ptr;      
        *ptr = (*ptr)->left;  // 左节点取代父节点位置
        free(temp);
    }
    else     // 目标节点的含有两个节点
    {
        // 循环，沿着左子树的最右分支查找空位置
        for (temp = (*ptr)->left; temp->right != NULL; temp = temp->right)
            continue;
        temp->right = (*ptr)->right; // 把目标节点的右子树放到(依附)目标节点左子树的右分支空位置
        temp = *ptr;    
        *ptr = (*ptr)->left; // 左子树取代目标节点位置
        free(temp);   // 释放目标节点
    }
}

// 删除所有节点
static void DeleteAllNodes(Node * root)
{
    Node * pright;

    if(root !=NULL)
    {
        pright = root->right;
        DeleteAllNodes(root->left);
        free(root);
        DeleteAllNodes(pright);
    }
}

二叉搜索树的应用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
/* petclub.c -- 使用二叉树 */
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include "tree.h"

char menu(void);
void addpet(Tree * pt);
void droppet(Tree * pt);
void showpets(const Tree * pt);
void findpets(const Tree * pt);
void printitem(Item item);
void uppercase(char * str);

int main(void)
{
    Tree pets;
    char choice;

    InitializeTree(&pets);
    while((choice = menu()) != 'q')
    {
        switch (choice)
        {
        case 'a': addpet(&pets); break;
        case 'l': showpets(&pets); break;
        case 'f': findpets(&pets); break;
        case 'n': printf("%d pets in club\n", TreeItemCount(&pets)); break;
        case 'd': droppet(&pets); break;
        
        default: puts("Switching error");
        }
    }
    DeleteAll(&pets);
    puts("Bye.");
    return 0;
}

char menu(void)
{
    int ch;

    puts("Nerfville Pet Club Membership Program");
    puts("Enter the letter coresponding your choice: ");
    puts("a) add a pet        l) show list of pets");
    puts("n) number of pet    f) find pets");
    puts("d)delete a pet      q) quit");
    while((ch = getchar()) != EOF)
    {
        while(getchar() != '\n')   /* 清空缓冲 */
            continue;
        ch = tolower(ch);
        if(strchr("alrfndq", ch) == NULL)
            puts("Please enter an a, l, f, n, d, or q");
        else
            break;
    }
    if(ch == EOF)     // 令EOF导致程序退出
        ch = 'q';
    
    return ch;
}

void addpet(Tree * pt)
{
    Item temp;

    if(TreeIsFull(pt))
        puts("No room in the club!");
    else
    {
        puts("Please enter name of pets: ");
        gets(temp.petname);
        puts("Please enter pet kind: ");
        gets(temp.petkind);
        uppercase(temp.petname);
        uppercase(temp.petkind);
        AddItem(&temp, pt);
    }
}

void droppet(Tree * pt)
{
    Item temp;

    if(TreeIsEmpty(pt))
    {
        puts("No entries!");
        return;
    }

    puts("Please enter name of pet you wish to delete: ");
    gets(temp.petname);
    puts("Please enter pet kind: ");
    gets(temp.petkind);
    printf("%s the %s ", temp.petname, temp.petkind);
    if(DeleteItem(&temp, pt))
        printf("is dropped from the club.\n");
    else
        printf("is not a member.\n");
}

void showpets(const Tree * pt)
{
    if(TreeIsEmpty(pt))
        puts("No entries!");
    else
        Traverse(pt, printitem);
}

void findpets(const Tree * pt)
{
    Item temp;

    if(TreeIsEmpty(pt))
    {
        puts("No entries!");
        return;
    }

    puts("Please enter name of pet you wish to delete: ");
    gets(temp.petname);
    puts("Please enter pet kind: ");
    gets(temp.petkind);
    uppercase(temp.petname);
    uppercase(temp.petkind);
    printf("%s the %s ", temp.petname, temp.petkind);
    if(InTree(&temp, pt))
        printf("is a member.\n");
    else
        printf("is not a member.\n");

}

void printitem(Item item)
{
    printf("Pet: %-19s Kind: %-19s\n", item.petname, item.petkind);
}

void uppercase(char * str)
{
    while(*str)
    {
        *str = toupper(*str);
        str++;
    }
}