数据结构_排序二叉树(C语言)_采用逐点排序法建立二叉树

数据结构总目录

排序二叉树

1. 结构解析

排序二叉树的结构规则很简单，只遵循一个基本规则：
那就是在二叉树中，选择任意根结点，其左子树都比根节点小，右子树都比根节点大。

排序二叉树结构图

观察如下二叉树，即可发现排序二叉树左小右大的规律，如图：

排序二叉树的基本操作

对于排序二叉树的插入操作较为简单，只需按照左小右大的规则进行判断即可。
而对于排序二叉树的删除操作，因为删除结点后依然要保持排序二叉树的基本规则，所以需要分类讨论

一、当所删除的结点【p】存在空的子树，共有三种情况（在代码中可归为一类），如下图：
（1）当p结点的左右子树均为空时，直接删除结点p即可

（2）当 p 结点左子树不为空，而右子树为空时，只需要将 p 的左子树接到 父结点 f 下即可

（3）同理，当 p 结点右子树不为空，而左子树为空时，只需要将 p 的右子树接到父结点 f 下即可

二、当所删除的结点《p》的左右子树都存在时，且有如下已知条件：

已知条件： s 结点为 p 结点的左子树中最大的结点，则结点s的右子树必定为空

（1）第一种删除方式：将p结点的右子树转接到s结点的右子树上。
注意：虽然这样保证了排序二叉树基本规则，但是增加了二叉树的深度（高度），不利于查找

（2）第二种方式：将p结点和结点s的数据进行交换，由 f 结点继承 s 结点的左子树

2. 源代码：

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

typedef int DataType;
typedef struct BiTNode
{
    DataType data;
    struct BiTNode *lchild, *rchild;
}LinkBiTree;

void InitBiTree(LinkBiTree **T)
{
    (*T) = NULL;
    printf("二叉树已初始化!\n");
}

// 排序二叉树的插入操作
void SortBiTreeInsert(LinkBiTree **T, DataType x)
{
    if ((*T) == NULL)
    {
        // 如果当前二叉树结点为空, 则为分配新的结点空间
        (*T) = (LinkBiTree *)malloc(sizeof(LinkBiTree));
        (*T)->data = x;
        (*T)->lchild = (*T)->rchild = NULL;
    }
    else if (x < (*T)->data)
    {
        SortBiTreeInsert(&(*T)->lchild, x);
    }
    else if(x > (*T)->data)
    {
        SortBiTreeInsert(&(*T)->rchild, x);
    }
    else
    {
        printf("插入失败!存在相同数据!\n");
    }
}

// 排序二叉树的删除操作
void SortBiTreeDelete(LinkBiTree *T, DataType key)
{
    // 首先查询 [需要删除的结点(p)] 和 [被删除结点的父结点(f)]
    LinkBiTree *p = T, *f = NULL;
    while (p)
    {
        if (key == p->data)
        {
            break;
        }
        f = p;
        p =  key < p->data ? p->lchild : p->rchild; 
    }
    if (!p)
    {
        printf("删除失败!未查询到该结点%d\n", key);
        return;
    }

    LinkBiTree *q = p;
    // *****************1. 结点p存在空子树******************
    if(!p->lchild || !p->rchild)
    { 
        // 1.1 选择非空的子孩子
        p = p->lchild ? p->lchild : p->rchild;

        // 1.2 父结点接入p结点的子树
        if (f->lchild == q)     // 被删除的是左孩子
        {
            f->lchild = p;      // 接入右子树
        }
        else if (f->rchild == q)// 被删除的是右孩子
        {
            f->rchild = p;      // 接入右子树
        }

        // 1.3 销毁结点
        free(q);
    }
    // *****************2. 结点p的左右子树都不为空******************
    else
    {
        // 2.1 从p结点的左子树中查找最大结点，用于替换p结点
        f = p;
        LinkBiTree *s = p->lchild;
        while (s->rchild)
        {
            f = s;          //s的父结点
            s = s->rchild;  
        }

        // 2.2 替换结点p的数据
        p->data = s->data;

        // 2.3 s父结点f  接入 s的左子树
        if (f != p)
        {
            f->rchild = s->lchild;
        }
        else
        {
            f->lchild = s->lchild;
        }

        // 2.4 销毁结点
        free(s);
    }
    printf("已完成删除操作!\n");
}

// 先序遍历二叉树
void PreOrderTraverse(LinkBiTree *T)
{
    if (T != NULL)
    {
        printf("%d ", T->data);
        PreOrderTraverse(T->lchild);
        PreOrderTraverse(T->rchild);
    }
}

// 中序遍历二叉树
void InOrderTraverse(LinkBiTree *T)
{
    if (T != NULL)
    {
        InOrderTraverse(T->lchild);
        printf("%d ", T->data);
        InOrderTraverse(T->rchild);
    }
}

// 后序遍历二叉树
void PostOrderTraverse(LinkBiTree *T)
{
    if (T != NULL)
    {
        PostOrderTraverse(T->lchild);
        PostOrderTraverse(T->rchild);
        printf("%d ", T->data);
    }
}

int main()
{   
    printf("**********************************\n");
    printf("0:退出\t\t1:插入结点\t2:删除结点\n");
    printf("3:先序遍历\t4:中序遍历\t5:后序遍历\n");
    printf("**********************************\n");

    int k;
    DataType x;
    LinkBiTree *T;
    InitBiTree(&T);
    while (1)
    {
        printf("请输入操作序号:");
        scanf("%d", &k);
        if (!k)
        {
            break;
        }
        switch (k)
        {
            case 1:
                //参考用例:40 18 8 30 20 50 100 60 55 90 70 95 120 -9999
                printf("请输入插入数据:");
                while (scanf("%d", &x) != -1)
                {
                    if (x == -9999)
                    {
                        break;
                    }
                    SortBiTreeInsert(&T, x);
                }
                printf("插入完成!\n");
                break;
            case 2:
                printf("请输入删除数据:");
                scanf("%d", &x);
                SortBiTreeDelete(T, x);
                break;
            case 3:
                printf("先序遍历:"); 
                PreOrderTraverse(T);
                printf("\n");
                break;
            case 4: 
                printf("中序遍历:"); 
                InOrderTraverse(T); 
                printf("\n");
                break;
            case 5: 
                printf("后序遍历:"); 
                PostOrderTraverse(T);
                printf("\n");
                break;
            default:break;
        }
        printf("\n");
    }
    system("pause");
    return 0;
}
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

3. 测试结果

用例参考图

测试结果