tree.h

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
#ifndef TREE_H_
#define TREE_H_//防止多次包含
#include<stdbool.h>
#define PETSLEN 20//pet string length
#define MAXITEMS 10
struct item {
    char pet_name[PETSLEN];
    char pet_kind[PETSLEN];
};
typedef struct item Item;
struct trnode {
    Item item;
    struct trnode* left;
    struct trnode* right;
};
typedef struct trnode Trnode;
struct tree {
    Trnode* root;
    int size;//item of tree amount
};
typedef struct tree Tree;
typedef void (*V_FP_ITEM)(Item*);//指向函数的指针，该函数返回void，接受Item*类型的参数
/*初始化树，该接口包所有函数调用前必须执行此函数*/
void InitializeTree(Tree* ptree);
/*判断树是否为空*/
bool TreeIsEmpty(const Tree* ptree);
/*判断树是否已满*/
bool TreeIsFull(const Tree* ptree);
/*返回树中的项数,ptree必须指向一个已初始化的树*/
int TreeItemCount(const Tree* ptree);
/*添加项到树中，成功返回真，失败返回假(可能树已满或者内存分配失败)*/
bool AddItem(Item* pi, Tree* ptree);
/*判断项是否在树中*/
bool InTree(const Item* pi,const Tree* ptree);
/*删除树中的项*/
bool DeleteItem(const Item* pi, Tree* ptree);
/*将指定的函数应用与树的每一项*/
void Traverse(const Tree* ptree, V_FP_ITEM pf);
/*删除所有项*/
void DeleteAll(Tree* ptree);
#endif

tree.c

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
#include"tree.h"
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct pair {
    Trnode* parent;
    Trnode* child;
};
/*静态函数需要使用的结构体，保存父节点和当前节点*/
typedef struct pair Pair;
//在树中查找相同的项,返回一个包含该项节点信息的结构，如果child成员为NULL说明树为空或没找到项
static Pair SeekItem(const Item* pi, const Tree* ptree);
static bool ToLeft(const Item* pi1, const Item* pi2);
static bool ToRight(const Item* pi1, const Item* pi2);
static Trnode* MakeNode(const Item* pi);
static void AddNode(Trnode* new_node, Trnode* root);
static void DeleteNode(Trnode** pptrn);
static void InOrder(Trnode* ptrn, V_FP_ITEM pf);
static void DeleteAllNode(Trnode* ptrn);
void InitializeTree(Tree* ptree) {
    ptree->root = NULL;
    ptree->size = 0;
}
bool TreeIsEmpty(const Tree* ptree) {
    return !ptree->root ? true : false;
}
bool TreeIsFull(const Tree* ptree) {
    return MAXITEMS == ptree->size ? true : false;
}
int TreeItemCount(const Tree* ptree) {
    return ptree->size;
}
bool AddItem(Item* pi, Tree* ptree) {
    Trnode* new_node;
    if (TreeIsFull(ptree)) {
        fputs("Tree is full.\n", stderr);
        return false;
    }
    if (SeekItem(pi, ptree).child) {
        fputs("Attempt to add duplicate item.\n", stderr);
        return false;
    }
    if (!(new_node = MakeNode(pi))) {
        fputs("Can not create dynamic memory.\n", stderr);
        return false;
    }
    ptree->size++;
    if (!ptree->root)
        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 ? true : false;
}
bool DeleteItem(const Item* pi, Tree* ptree) {
    Pair look;
    look = SeekItem(pi, ptree);//找到包含待删除项的节点和其父节点(用于修改子节点)
    if (!look.child)
        return false;
    if (!look.parent)
        DeleteNode(&ptree->root);
    else if (look.parent->left == look.child)
        DeleteNode(&look.parent->left);//look.parent解引后得到结构 取左子节点的地址
    else
        DeleteNode(&look.parent->right);
    ptree->size--;
    return true;
}
void Traverse(const Tree* ptree, V_FP_ITEM pf) {
    if (ptree)
        InOrder(ptree->root, pf);
}
void DeleteAll(Tree* ptree) {
    if (ptree) {
        DeleteAllNode(ptree->root);
        ptree->root = NULL;//DeleteAllNode()函数只释放空间，需要初始化根节点
        ptree->size = 0;
    }
}
static Pair SeekItem(const Item* pi, const Tree* ptree) {
    Pair look;
    look.parent = NULL;
    look.child = ptree->root;
    if (!look.child)
        return look;
    while (look.child) {
        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;
    }
    return look;
}
/*比较项的排序，作用相当于对整型使用<,但无法判断是否相等*/
static bool ToLeft(const Item* pi1, const Item* pi2) {
    int compare;
    if ((compare = strcmp(pi1->pet_name, pi2->pet_name)) < 0)//按宠物名索引
        return true;
    else if (!compare && strcmp(pi1->pet_kind, pi2->pet_kind) < 0)//如果宠物名相同按种类索引
        return true;
    else
        return false;//否则返回假，可能pi1排在pi2后面或者是完全相同的项
}
/*比较项的排序，作用相当于对整型使用>,但无法判断是否相等*/
static bool ToRight(const Item* pi1, const Item* pi2) {
    int compare;
    if ((compare = strcmp(pi1->pet_name, pi2->pet_name)) > 0)
        return true;
    else if (!compare && strcmp(pi1->pet_kind, pi2->pet_kind) > 0)
        return true;
    else
        return false;
}
static Trnode* MakeNode(const Item* pi) {
    Trnode* new_node;
    if (new_node = (Trnode*)malloc(sizeof(Trnode))) {
        new_node->item = *pi;
        new_node->left = new_node->right = NULL;
    }
    return new_node;
}
static void AddNode(Trnode* new_node, Trnode* root) {
    if (ToLeft(&new_node->item, &root->item)) {
        if (!root->left)
            root->left = new_node;
        else
            AddNode(new_node, root->left);
    }
    else if (ToRight(&new_node->item, &root->item)) {
        if (!root->right)
            root->right = new_node;
        else
            AddNode(new_node, root->right);
    }
    else {
        fputs("Location error in AddNode().\n", stderr);
        system("pause");
        exit(EXIT_FAILURE);//AddItem()函数已有重复项判断，如果此时遇到相同的项说明程序错误
    }
}
static void DeleteNode(Trnode** pptrn) {
    Trnode* temp;
    if (!(*pptrn)->left) {//左子树为空时无论右子树是否为空将其替换为待删除节点
        temp = *pptrn;
        *pptrn = (*pptrn)->right;
        free(temp);
    }
    else if (!(*pptrn)->right) {
        temp = *pptrn;
        *pptrn = (*pptrn)->left;
        free(temp);
    }
    else {//如果待删除节点有2个子节点，将右子节点链接到左子节点的最右(后)边
        for (temp = (*pptrn)->left; temp->right; temp = temp->right)//遍历左子节点到右侧底部
            continue;
        temp->right = (*pptrn)->right;
        temp = *pptrn;
        *pptrn = (*pptrn)->left;
        free(temp);
    }
}
static void InOrder(Trnode* ptrn, V_FP_ITEM pf)//中序遍历二叉树 {
    if (ptrn) {
        InOrder(ptrn->left, pf);
        (*pf)(&ptrn->item);//项处理函数
        InOrder(ptrn->right, pf);
    }
}
static void DeleteAllNode(Trnode* ptrn) {
    Trnode* pright;
    if (ptrn) {
        pright = ptrn->right;//保存右子节点，否则处理完根后就索引不到了
        DeleteAllNode(ptrn->left);
        free(ptrn);
        DeleteAllNode(pright);
    }
}