二叉排序树

发表于 更新于 分类于 ，
本文字数： 3.6k

二叉排序树 —— 具有特殊性质的二叉树

数据结构课代码实现 之 二叉排序树

简要理解

二叉排序树具有如下性质：

  1. 二叉排序树可为空
  2. 如果二叉排序树不为空树，则排序树上每个结点都满足：
    1. 若左子树不空，则左子树上所有结点的值均小于它的根结点的值
    2. 若右子树不空，则右子树上所有结点的值均大于它的根结点的值
    3. 该结点的左、右子树也分别为一棵二叉排序树

代码实现

插入过程：

  1. 初始为空树，直接插入根节点
  2. 不为空树时，进行查找操作
    1. 如果在树中找到插入的数据，则不需要插入
    2. 如果找不到，查找函数会返回需要插入结点的父节点 (查找操作中会记录父结点，方便插入操作)

删除过程：

需要注意一下，删除一个结点分为两种情况：

  1. 该结点只有左右子树，则将该结点的左 (右) 子树的根结点代替此结点即可，不会破坏二叉排序树性质
  2. 该结点既有左子树又有右子树，则需要利用二叉排序树的性质（中序输出这棵二叉树即为一个由小到大的序列），所以删除该结点，相当于用删除结点的 前驱 或者 后继结点 的 data值 来代替删除结点的 data值，然后删除 前驱 或者 后继结点，以下代码是用前驱结点来代替
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
#include<iostream>

using namespace std;

typedef struct BiNode
{
    int data;
    struct BiNode* lc;
    struct BiNode* rc; 
}BiNode, *BiTree;

bool EQ(int key1, int key2)
{
    if(key1 == key2)
        return true;
    else 
        return false;
}

bool LT(int key1, int key2)
{
    if(key1 < key2)
        return true;
    else
        return false;
}

bool SearchBST(BiTree T, int key, BiTree f, BiTree &p)
{
    if(!T)
    {
        p = f;
        return false; 
    }
    else if(EQ(key, T->data))
    {
        p = T;
        return true;
    }
    else if(LT(key, T->data))
    {
        return SearchBST(T->lc, key, T, p);
    }
    else
        return SearchBST(T->rc, key, T, p);
}

bool InsertBST(BiTree &T, int key)
{
    BiTree p;
    if(!SearchBST(T, key, NULL, p))
    {
        BiTree s = (BiTree)malloc(sizeof(BiNode));
        s->data = key;
        s->lc = NULL;
        s->rc = NULL;
        if(!p) T = s;
        else if(LT(key, p->data))
            p->lc = s;
        else
            p->rc = s;
        return true;
    }
    else
        return false;
}

bool Delete(BiTree &p)
{
    BiTree q;
    if(!p->rc)
    {
        q = p;
        p = p->lc;
        free(q);
    }
    else if(!p->lc)
    {
        q = p;
        p = p->rc;
        free(q);
    }
    else
    {
        q = p;
        BiTree s = p->lc; // 左移至删除结点的左儿子
        while(s->rc) // 左儿子有右子树的情况
        {
            q = s; // q记录前驱结点的前一个结点
            s = s->rc; // s记录前驱结点
        }
        p->data = s->data; // 用前驱结点的 data 代替 删除结点的 data
        if(q != p) // q != p 的情况即是删除结点的左儿子有右子树
            q->rc = s->lc; // 将前驱结点的左子树接到前一个结点的右子树上
        else
            q->lc = s->lc; // 删除结点的左儿子无右子树 左儿子就是前驱结点 将其左子树接到被删除结点的左子树上
        free(s);
    }
    return true;
}

bool DeleteBST(BiTree &T, int key)
{
    if(!T) return false;
    else
    {
        if(EQ(key, T->data)) return Delete(T);
        else if(LT(key, T->data)) return DeleteBST(T->lc, key);
        else
            return DeleteBST(T->rc, key);
    }
}

void OnOrder(BiTree T, int l, int r, int cen, int fa)
{
    if(T)
    {
        OnOrder(T->lc, 1, 0, cen + 1, T->data); 
        if(fa == -1)
            cout << "根节点" << " 该点为：" << T->data << " 层数为：" << cen << endl;
        else
        {
            if(l)
                cout << "该点为：" << T->data << " 该节点为 " << fa << " 的左儿子" << " 层数为：" << cen << endl;
            if(r)
                cout << "该点为：" << T->data << " 该节点为 " << fa << " 的右儿子" << " 层数为：" << cen << endl;
        }
        OnOrder(T->rc, 0, 1, cen + 1, T->data);
    }
}

int main()
{
    BiTree T;
    T = NULL;
    int n;
    cout << "请输入要插入的结点数：" << endl;
    cin >> n;
    cout << "依次输入每个结点的data, 空格分开" << endl;
    for(int i = 0;i < n;i++)
    {
        int x;
        cin >> x;
        InsertBST(T, x);
    }
    
    BiTree p = NULL;
    int x;
    cout << "输入查找的data：" << endl;
    cin >> x;
    if(SearchBST(T, x, NULL, p))
        cout << "找见了";
    else
        cout << "没找见";
    cout << endl;
    cout << "输入删除的点：" << endl;
    cin >> x;
    if(DeleteBST(T, x))
        cout << "删除了" << x;
    else
        cout << "没有" << x << "怎么删除啊？";
    cout << endl;
    cout << endl << "这是这棵树：" << endl; 
    OnOrder(T, 0, 0, 1, -1);
    return 0;
}