平衡二叉树_程序输入一个字符串(只包含小写字母),请按照字符的输入顺序建立平衡二叉排序树,并

题目信息

程序输入一个字符串（只包含小写字母），请按照字符的输入顺序建立平衡二叉排序树，并分别输出二叉树的先序序列、中序序列和后序序列，最后输出该二叉树向左旋转 90 度后的结构。
例如：向左旋转 90 度后，以每层向里缩进 4 个空格的方式输出，输出结果为

        i
    g
        f
a
        d
    c
        b
1
2
3
4
5
6
7

测试样例

测试样例1

agxnzyimk
1

Preorder: xigamknzy
Inorder: agikmnxyz
Postorder: agknmiyzx
Tree:
    z
        y
x
            n
        m
            k
    i
        g
            a
1
2
3
4
5
6
7
8
9
10
11
12
13

测试样例2

asdfghjkl
1

Preorder: gdafjhlks
Inorder: adfghjkls
Postorder: afdhksljg
Tree:
            s
        l
            k
    j
        h
g
        f
    d
        a
1
2
3
4
5
6
7
8
9
10
11
12
13

解答

#include<iostream>

using namespace std;

#define LH +1   //左高
#define EH 0    //等高
#define RH -1   //右高
typedef struct NODE
{
    char data; //数据域
    int bf; //平衡因子
    NODE *Left; //左孩子
    NODE *Right; //右孩子
} BSnode, *BSTree;

void R_Rotate(BSTree *ptr)
{//右旋
    BSTree lc = (*ptr)->Left; //lc指向的*ptr的左孩子的根结点
    (*ptr)->Left = lc->Right; //lc的右子树挂接为*ptr的左子树
    lc->Right = *ptr;
    *ptr = lc; //ptr指向新的结点
}

void L_Rotate(BSTree *ptr)
{//左旋
    BSTree rc = (*ptr)->Right;   //rc指向的*ptr的由孩子的根结点
    (*ptr)->Right = rc->Left;   //rc的左子树挂接为*ptr的右子树
    rc->Left = *ptr;
    *ptr = rc;                  //ptr指向新的结点
}

void LeftBalance(BSTree *root)
{//左平衡旋转处理
    BSTree lc = (*root)->Left; //lc指向*root的左根结点
    switch (lc->bf)
    {//检测*root的左子树的平衡度，并作相应处理
        case LH:
        {//新结点插入在*root的左孩子的左子树上，要做单右旋处理
            (*root)->bf = lc->bf = EH;
            R_Rotate(root);
            break;
        }
        case RH:
        {//新结点插入在*root左孩子的右子树上要做双旋处理
            BSTree rd = lc->Right;//rd指向*root的左孩子的右子树根上
            switch (rd->bf)
            {//修改*root及其左孩子的平衡因子
                case LH:
                {
                    (*root)->bf = RH;
                    lc->bf = EH;
                    break;
                }
                case EH:
                {
                    (*root)->bf = lc->bf = EH;
                    break;
                }
                case RH:
                {
                    (*root)->bf = EH;
                    lc->bf = LH;
                    break;
                }
            }
            rd->bf = EH;
            L_Rotate(&(*root)->Left);//对*root的左子树左左旋平衡处理
            R_Rotate(root);//rd指向*t的左孩子的右子树根上
        }
    }
}

void RightBalance(BSTree *root)//右平衡旋转处理
{
    BSTree lc;
    BSTree rd;
    lc = (*root)->Right;
    switch (lc->bf)
    {
        case RH:
        {
            (*root)->bf = lc->bf = EH;
            L_Rotate(root);
            break;
        }
        case LH:
        {
            rd = lc->Left;
            switch (rd->bf)
            {
                case LH:
                {
                    (*root)->bf = EH;
                    lc->bf = RH;
                    break;
                }
                case EH:
                {
                    (*root)->bf = lc->bf = EH;
                    break;
                }
                case RH:
                {
                    (*root)->bf = LH;
                    lc->bf = EH;
                    break;
                }
            }
            rd->bf = EH;
            R_Rotate(&(*root)->Right);
            L_Rotate(root);
        }
    }
}

//我们这里的平衡二叉树还要求是保持节点为中值，左子树数值大于根节点，且存在唯一性
int InsertAVL(BSTree *root, char e, bool *taller)
{
    if ((*root) == NULL)
    {//该树为一棵空树，创建一个新节点作为根节点
        (*root) = new BSnode;
        (*root)->bf = EH;//刚建立的树是平衡的
        (*root)->data = e;
        (*root)->Left = NULL;
        (*root)->Right = NULL;
        *taller = true;
    }
    else if (e == (*root)->data)
    {//关键字相同，则不再继续插入
        *taller = false;
        return 0;
    }
    else if (e < (*root)->data)
    {
        if (!InsertAVL(&(*root)->Left, e, taller))//应该继续在*root的左子树进行搜索
        {//未插入
            return 0;
        }
        if (*taller)
        {//已插入到*root的左子树中并且左子树长高，现在来检查*root的平衡度
            switch ((*root)->bf)
            {
                case LH:
                {//原本左子树比右子树高，平衡因子为-1
                    LeftBalance(root);//需要做左旋平衡处理
                    *taller = false;
                    break;
                }
                case EH:
                {//原本左右树一样高，现在因为左子树长高树长高，平衡因子改为LH
                    (*root)->bf = LH;
                    *taller = true;//涨高了
                    break;
                }
                case RH:
                {//原本右子树比左子树高，现在等高平衡因子为1
                    (*root)->bf = EH;
                    *taller = false;
                    break;
                }
            }
        }
    }
    else
    {
        if (!InsertAVL(&(*root)->Right, e, taller))//应继续在*root的右子树中进行搜索
        {//未插入
            return 0;
        }
        if (*taller)
        {//已插入到*root的右子树且右子树长高，现在来检查*root的平衡度
            switch ((*root)->bf)
            {
                case LH:
                {//原本左子树比右子树高，现在相等
                    (*root)->bf = EH;
                    *taller = false;
                    break;
                }
                case EH:
                {//原来左右子树等高，现在因为右子树长高树长高
                    (*root)->bf = RH;
                    *taller = true;
                    break;
                }
                case RH:
                {//原本右子树比左子树高，需要做右旋平衡处理
                    RightBalance(root);
                    *taller = false;
                    break;
                }
            }
        }
    }
    return 1;
}

void printBIT(BSTree root, int x)
{
    if (root != NULL)
    {
        printBIT(root->Right, x + 1);
        for (int i = 0; i < x; i++)
            cout << "    ";
        cout << root->data << endl;
        printBIT(root->Left, x + 1);
    }
}

void preorder(BSTree root)
{
    if (root != NULL)
    {
        cout << root->data;
        preorder(root->Left);
        preorder(root->Right);
    }
}

void inorder(BSTree root)//二叉树的中序遍历
{
    if (root != NULL)
    {
        inorder(root->Left);
        cout << root->data;
        inorder(root->Right);
    }
}

void postorder(BSTree root)
{
    if (root != NULL)
    {
        postorder(root->Left);
        postorder(root->Right);
        cout << root->data;
    }
}

int main()
{
    //freopen("/Users/zhj/Downloads/test.txt", "r", stdin);
    bool taller;//taller变量反应T长高与否
    BSTree root = NULL;
    string x;
    cin >> x;
    for (int i = 0; x[i]; i++)
    {
        InsertAVL(&root, x[i], &taller);
    }
    cout << "Preorder: ";//先序
    preorder(root);
    cout << endl << "Inorder: ";//中序
    inorder(root);
    cout << endl << "Postorder: ";//后序
    postorder(root);
    cout << endl << "Tree:" << endl;
    printBIT(root, 0);
    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
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

想法

平衡二叉树又称AVL树，它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。将二叉树上结点的平衡因子定义为该结点的左子树深度减去右子树的深度，平衡二叉树上所有结点的平衡因子只能是-1、0或1。

类型定义

typedef struct NODE
{
	char data; 			//数据域 
	int bf; 			//平衡因子 
	NODE *lchild; //左孩子 
	NODE *rchild; //右孩子 
}BSnode, *BSTree;
1
2
3
4
5
6
7

平衡化

• L平衡旋转
  将5的左孩子3向右上旋转代替5成为根结点，将5结点向右下旋转成为3的右子树的根结点，而3的原右子树4作为5结点的左子树。
  这一项操作对应着左平衡旋转处理中新结点插入在左孩子的左子树上，要做单右旋处理。
  在操作之后3节点和5节点都是平衡的。
  
• R平衡旋转
  与上述L平衡旋转一致。
  将Root的右孩子R向左上旋转代替Root成为根结点，将Root结点向左下旋转成为R的左子树的根结点，而R的原左子树作为Root结点的右子树。
  这一项操作对应着右平衡旋转处理中新结点插入在右孩子的右子树上，要做单左旋处理。
  在操作之后Root和Right节点都是平衡的。
• LR平衡旋转

1. 类型一
   先将5结点的左孩子2的右子树的根节点4向右上旋转提升到原2结点的位置，而4的原左子树3作为2结点的右子树，然后再把该4结点向右上旋转提升到5结点的位置成为根节点，将5结点向右下旋转成为4的右子树的根结点。
   这一项操作对应着左平衡旋转处理中新节点插入在左孩子的右子树上，同时右子树有左高的特征。
   在操作之后5节点变为右高的特征，2节点变为平衡的特征。
   
2. 类型二
   先将6结点的左孩子2的右子树的根节点4向右上旋转提升到原2结点的位置，而4的原左子树3作为2结点的右子树，然后再把该4结点向右上旋转提升到5结点的位置成为根节点，而4的原右子树5作为6结点的左子树，将6结点向右下旋转成为4的右子树的根结点.
   这一项操作对应着左平衡旋转处理中新节点插入在左孩子的右子树上，同时这个右子树有等高的特征。
   在操作之后6节点和2节点都变为平衡的特征。
   
3. 类型三
   先将5结点的左孩子2的右子树的根节点3向右上旋转提升到原2结点的位置，再把3结点向右上旋转提升到5结点的位置成为根节点，将5结点向右下旋转成为3的右子树的根结点，而3的原右子树4作为5结点的左子树。
   这一项操作对应着左平衡旋转处理中新节点插入在左孩子的右子树上，同时这个右子树有右高的特征。
   在操作之后5节点变为平衡的特征，2节点变为左高的特征。
   

• RL平衡旋转
  与上述LR平衡旋转一致，左右相互交换即可。