排序二叉树

1 分部

1.1 头文件以及宏定义

1
2
3
4
5
6
7
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <time.h>

#define TREE_TYPE int

1. 2 结构体 TREE_NODE 定义

1
2
3
4
5
6
7
typedef struct TREE_NODE {
    TREE_TYPE value;
    struct TREE_NODE *left;
    struct TREE_NODE *right;
}TreeNode;

static TreeNode *tree = NULL;

1.3 insert 插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void insert(TREE_TYPE value)
{
    TreeNode *current;
    TreeNode **link;

    link = &tree;

    while((current = *link) != NULL) {
        if (value < current->value)
            link = &current->left;
        else {
            link = &current->right;
        }
    }

    current = malloc(sizeof(TreeNode));
    assert(current != NULL);
    current->value = value;
    current->left = NULL;
    current->right = NULL;
    current->right = NULL;
    *link = current;
}

1.4 find 查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
TreeNode *find(TreeNode *current, TREE_TYPE value)
{
    while(current != NULL && current->value != value) {
        if (value < current->value)
            current = current->left;
        else
            current = current->right;
    }

    if (current != NULL)
        return current;
    else
        return NULL;
}

1.5 delete 删除

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
void delete(TREE_TYPE value)
{
    TreeNode *current;
    TreeNode **link;

    link = &tree;

    while((current = *link) != NULL && value != current->value) {
        if (value < current->value)
            link = &current->left;
        else
            link = &current->right;
    }
    assert(current != NULL);

    if (current->left == NULL && current->right == NULL) {
        *link = NULL;
        free(current);
    }
    else if (current->left == NULL || current->right == NULL) {
        if (current->left != NULL)
            *link = current->left;
        else
            *link = current->right;
        free(current);
    }
    else {//左右子树都不为空
        TreeNode *this_child;
        TreeNode *next_child;

        /*转左，然后向右到尽头*/
        this_child = current;
        next_child = this_child->left;
        while (next_child->right != NULL) {
            this_child = next_child;
            next_child = next_child->right;
        }

        current->value = next_child->value;
        if (this_child != current)
            this_child->right = next_child->left;
        else
            this_child->left = next_child->left;
        free(next_child);
    }

}

1.6  pre_order_traverse

1
2
3
4
5
6
7
8
9
static void pre_order_traverse(TreeNode *current,
        void (*callback)(TREE_TYPE value))
{
    if (current != NULL) {
        callback(current->value);
        pre_order_traverse(current->left, callback);
        pre_order_traverse(current->right, callback);
    }
}

1.7 print_tree

1
2
3
4
void print_tree(TREE_TYPE value)
{
    printf("%3d", value);
}

1.8 inner_order_traverse

1
2
3
4
5
6
7
8
9
void inner_order_traverse(TreeNode *current,
        void (*callback)(TREE_TYPE value))
{
    if (current != NULL) {
        inner_order_traverse(current->left, callback);
        callback(current->value);
        inner_order_traverse(current->right, callback);
    }
}

1.9 post_order_traverse

1
2
3
4
5
6
7
8
9
void post_order_traverse(TreeNode *current,
        void (*callback)(TREE_TYPE value))
{
    if (current != NULL) {
        post_order_traverse(current->left, callback);
        post_order_traverse(current->right, callback);
        callback(current->value);
    }
}

1.10 main

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int main(int argc, char *argv[])
{
    TreeNode *p;
    srand(time(NULL));
    int i = 0, value = 0;
    for (i = 0; i < 5; i++) {
        value = rand() % 100;
        insert(i);
    }
//    pre_order_traverse(tree, print_tree); //前序
    inner_order_traverse(tree, print_tree); //中序
    printf("\n");
//    post_order_traverse(tree, print_tree); //后序

    delete(1);   //删除某个节点
    inner_order_traverse(tree, print_tree);
    return 0;
}

2 完整代码

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <time.h>

#define TREE_TYPE int

typedef struct TREE_NODE {
    TREE_TYPE value;
    struct TREE_NODE *left;
    struct TREE_NODE *right;
}TreeNode;

static TreeNode *tree = NULL;

void insert(TREE_TYPE value)
{
    TreeNode *current;
    TreeNode **link;

    link = &tree;

    while((current = *link) != NULL) {
        if (value < current->value)
            link = &current->left;
        else {
            link = &current->right;
        }
    }

    current = malloc(sizeof(TreeNode));
    assert(current != NULL);
    current->value = value;
    current->left = NULL;
    current->right = NULL;
    current->right = NULL;
    *link = current;
}

TreeNode *find(TreeNode *current, TREE_TYPE value)
{
    while(current != NULL && current->value != value) {
        if (value < current->value)
            current = current->left;
        else
            current = current->right;
    }

    if (current != NULL)
        return current;
    else
        return NULL;
}

void delete(TREE_TYPE value)
{
    TreeNode *current;
    TreeNode **link;

    link = &tree;

    while((current = *link) != NULL && value != current->value) {
        if (value < current->value)
            link = &current->left;
        else
            link = &current->right;
    }
    assert(current != NULL);

    if (current->left == NULL && current->right == NULL) {
        *link = NULL;
        free(current);
    }
    else if (current->left == NULL || current->right == NULL) {
        if (current->left != NULL)
            *link = current->left;
        else
            *link = current->right;
        free(current);
    }
    else {//左右子树都不为空
        TreeNode *this_child;
        TreeNode *next_child;

        /*转左，然后向右到尽头*/
        this_child = current;
        next_child = this_child->left;
        while (next_child->right != NULL) {
            this_child = next_child;
            next_child = next_child->right;
        }

        current->value = next_child->value;
        if (this_child != current)
            this_child->right = next_child->left;
        else
            this_child->left = next_child->left;
        free(next_child);
    }

}

static void pre_order_traverse(TreeNode *current,
        void (*callback)(TREE_TYPE value))
{
    if (current != NULL) {
        callback(current->value);
        pre_order_traverse(current->left, callback);
        pre_order_traverse(current->right, callback);
    }
}

void print_tree(TREE_TYPE value)
{
    printf("%3d", value);
}

void inner_order_traverse(TreeNode *current,
        void (*callback)(TREE_TYPE value))
{
    if (current != NULL) {
        inner_order_traverse(current->left, callback);
        callback(current->value);
        inner_order_traverse(current->right, callback);
    }
}

void post_order_traverse(TreeNode *current,
        void (*callback)(TREE_TYPE value))
{
    if (current != NULL) {
        post_order_traverse(current->left, callback);
        post_order_traverse(current->right, callback);
        callback(current->value);
    }
}

int main(int argc, char *argv[])
{
    TreeNode *p;
    srand(time(NULL));
    int i = 0, value = 0;
    for (i = 0; i < 5; i++) {
        value = rand() % 100;
        insert(i);
    }
//    pre_order_traverse(tree, print_tree); //前序
    inner_order_traverse(tree, print_tree); //中序
    printf("\n");
//    post_order_traverse(tree, print_tree); //后序

    delete(1);   //删除某个节点
    inner_order_traverse(tree, print_tree);
    return 0;
}