首页
社区
课程
招聘
问答 CTF 排行榜 知识库 工具下载 峰会 看雪商城 证书查询
  1. 社区
  2. 科锐培训
    3. 发新帖
7
[原创]发布一个平衡二叉树[完整代码]
发表于: 2008-6-13 22:46 4059

[原创]发布一个平衡二叉树[完整代码]

happymouse 活跃值
1
2008-6-13 22:46
4059
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
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
[color=#008000]/********************************************************************
  created:  2008/06/11
  filename: BalancedTree.h
  author:   happymouse
  version:  v1.0.0.0
*********************************************************************/[/color]
[color=#0000D0]#pragma[/color] [color=#0000D0]once[/color]
 
[color=#0000D0]#include[/color] <cassert>
 
[color=#008000]// Child node balanced status[/color]
[color=#0000D0]enum[/color] EnumBalancedStatus
{
    LeanToLeft,
    Balanced,
    LeanToRight
};
 
[color=#008000]// Balanced tree template class[/color]
[color=#0000D0]template[/color]<[color=#0000D0]typename[/color] T>
[color=#0000D0]class[/color] CBalancedTree
{
[color=#0000D0]private[/color]:
    [color=#008000]// Data[/color]
    T m_data;
     
    [color=#008000]// Left child tree[/color]
    CBalancedTree<T> *m_pLeftChild;
     
    [color=#008000]// Right child tree[/color]
    CBalancedTree<T> *m_pRightChild;
     
    [color=#008000]// Current balanced status[/color]
    EnumBalancedStatus m_balancedStatus;
[color=#0000D0]public[/color]:
    [color=#008000]// Constructor[/color]
    CBalancedTree()
        :m_pLeftChild([color=#0000D0]NULL[/color]), m_pRightChild([color=#0000D0]NULL[/color]), m_balancedStatus(Balanced)
    {
    }
     
    [color=#008000]// Constructor[/color]
    CBalancedTree([color=#0000D0]const[/color] T& [color=#0000D0]data[/color])
        :m_pLeftChild([color=#0000D0]NULL[/color]), m_pRightChild([color=#0000D0]NULL[/color]), m_balancedStatus(Balanced)
    {
        m_data = [color=#0000D0]data[/color];
    }
     
    [color=#008000]// Destructor[/color]
    [color=#0000D0]virtual[/color] ~CBalancedTree()
    {
        [color=#0000D0]if[/color] ([color=#0000D0]NULL[/color] != m_pLeftChild)
        {
            [color=#0000D0]delete[/color] m_pLeftChild;
        }
        [color=#0000D0]if[/color] ([color=#0000D0]NULL[/color] != m_pRightChild)
        {
            [color=#0000D0]delete[/color] m_pRightChild;
        }
    }
     
    [color=#008000]// Get left child pointer[/color]
    CBalancedTree<T> * GetLeftChild()
    {
        [color=#0000D0]return[/color] m_pLeftChild;
    }
 
    [color=#008000]// Get right child pointer[/color]
    CBalancedTree<T> * GetRightChild()
    {
        [color=#0000D0]return[/color] m_pRightChild;
    }
 
    [color=#008000]// Set data[/color]
    [color=#0000D0]void[/color] SetData([color=#0000D0]const[/color] T& [color=#0000D0]data[/color])
    {
        m_data = [color=#0000D0]data[/color];
    }
     
    [color=#008000]// Get data[/color]
    T& GetData()
    {
        [color=#0000D0]return[/color] m_data;
    }
     
    [color=#008000]// Rotate to left[/color]
    [color=#0000D0]void[/color] LeftRotate()
    {
        [color=#008000]// Swap the data of right child[/color]
        T _swapData = m_data;
        m_data = m_pRightChild->m_data;
        m_pRightChild->m_data = _swapData;
         
        [color=#008000]// Left rotate[/color]
        CBalancedTree<T> *_swapTree = m_pRightChild;
        m_pRightChild = m_pRightChild->m_pRightChild;
        _swapTree->m_pRightChild = _swapTree->m_pLeftChild;
        _swapTree->m_pLeftChild = m_pLeftChild;
        m_pLeftChild = _swapTree;
    }
     
    [color=#008000]// Rotate to right[/color]
    [color=#0000D0]void[/color] RightRotate()
    {
        [color=#008000]// Swap the data of left child[/color]
        T _swapData = m_data;
        m_data = m_pLeftChild->m_data;
        m_pLeftChild->m_data = _swapData;
         
        [color=#008000]// Right rotate[/color]
        CBalancedTree<T> *_swapTree = m_pLeftChild;
        m_pLeftChild = m_pLeftChild->m_pLeftChild;
        _swapTree->m_pLeftChild = _swapTree->m_pRightChild;
        _swapTree->m_pRightChild = m_pRightChild;
        m_pRightChild = _swapTree;
    }
     
    [color=#008000]// Insert a data into tree. If depth is add return true[/color]
    [color=#0000D0]bool[/color] Insert([color=#0000D0]const[/color] T& [color=#0000D0]data[/color])
    {
        [color=#0000D0]bool[/color] _fAppend = [color=#0000D0]false[/color];
        [color=#0000D0]if[/color] ([color=#0000D0]data[/color] == m_data)
        {
            [color=#0000D0]return[/color] _fAppend;
        }
        [color=#0000D0]if[/color] ([color=#0000D0]data[/color] < m_data)[color=#008000]// Insert into left child[/color]
        {
            [color=#0000D0]if[/color] ([color=#0000D0]NULL[/color] == m_pLeftChild)[color=#008000]// Left child depth append[/color]
            {
                m_pLeftChild = [color=#0000D0]new[/color] CBalancedTree<T>([color=#0000D0]data[/color]);
                _fAppend = [color=#0000D0]true[/color];
            }
            [color=#0000D0]else[/color][color=#008000]// Insert into child of left child[/color]
            {
                _fAppend = m_pLeftChild->Insert([color=#0000D0]data[/color]);
            }
            [color=#0000D0]if[/color] (_fAppend)
            {
                _fAppend = [color=#0000D0]false[/color];
                [color=#0000D0]switch[/color](m_balancedStatus)
                {
                [color=#0000D0]case[/color] LeanToRight:[color=#008000]// Right child has data[/color]
                    m_balancedStatus = Balanced;
                    [color=#0000D0]break[/color];
                [color=#0000D0]case[/color] Balanced:[color=#008000]// Current depth is append[/color]
                    m_balancedStatus = LeanToLeft;
                    _fAppend = [color=#0000D0]true[/color];
                    [color=#0000D0]break[/color];
                [color=#0000D0]case[/color] LeanToLeft:[color=#008000]// Must be balaced of current node[/color]
                    [color=#0000D0]if[/color] (m_pLeftChild->m_balancedStatus == LeanToLeft)[color=#008000]// Right rotate[/color]
                    {
                        RightRotate();
                        m_pRightChild->m_balancedStatus = Balanced;
                        [color=#0000D0]break[/color];
                    }
                    [color=#0000D0]else[/color] [color=#0000D0]if[/color] (m_pLeftChild->m_balancedStatus == LeanToRight)
                    {
                        [color=#008000]// Left rotate and Right rotate[/color]
                        m_pLeftChild->LeftRotate();
                        RightRotate();
                        [color=#0000D0]if[/color]([color=#0000D0]NULL[/color] == m_pLeftChild->m_pRightChild)
                        {
                            [color=#0000D0]break[/color];
                        }
                        [color=#0000D0]switch[/color] (m_pLeftChild->m_pRightChild->m_balancedStatus)
                        {
                        [color=#0000D0]case[/color] LeanToRight:
                            m_pLeftChild->m_balancedStatus = LeanToLeft;
                            m_pRightChild->m_balancedStatus = Balanced;
                            [color=#0000D0]break[/color];
                        [color=#0000D0]case[/color] Balanced:
                            m_pLeftChild->m_balancedStatus = Balanced;
                            m_pRightChild->m_balancedStatus = Balanced;
                            [color=#0000D0]break[/color];
                        [color=#0000D0]case[/color] LeanToLeft:
                            m_pLeftChild->m_balancedStatus = Balanced;
                            m_pRightChild->m_balancedStatus = LeanToRight;
                            [color=#0000D0]break[/color];
                        }
                    }
                    m_balancedStatus = Balanced;
                    [color=#0000D0]break[/color];
                }
            }
        }
        [color=#0000D0]else[/color][color=#008000]// Insert into right child[/color]
        {
            [color=#0000D0]if[/color] ([color=#0000D0]NULL[/color] == m_pRightChild)[color=#008000]// Right child depth append[/color]
            {
                m_pRightChild = [color=#0000D0]new[/color] CBalancedTree<T>([color=#0000D0]data[/color]);
                _fAppend = [color=#0000D0]true[/color];
            }
            [color=#0000D0]else[/color][color=#008000]// Insert into child of right child[/color]
            {
                _fAppend = m_pRightChild->Insert([color=#0000D0]data[/color]);
            }
            [color=#0000D0]if[/color] (_fAppend)[color=#008000]// Right node depth append[/color]
            {
                _fAppend = [color=#0000D0]false[/color];
                [color=#0000D0]switch[/color](m_balancedStatus)
                {
                [color=#0000D0]case[/color] LeanToLeft:[color=#008000]// Left child has data[/color]
                    m_balancedStatus = Balanced;
                    [color=#0000D0]break[/color];
                [color=#0000D0]case[/color] Balanced:[color=#008000]// Current depth is append[/color]
                    m_balancedStatus = LeanToRight;
                    _fAppend = [color=#0000D0]true[/color];
                    [color=#0000D0]break[/color];
                [color=#0000D0]case[/color] LeanToRight:[color=#008000]// Must be balaced of current node[/color]
                    [color=#0000D0]if[/color] (m_pRightChild->m_balancedStatus == LeanToRight)[color=#008000]// Left rotate[/color]
                    {
                        LeftRotate();
                        m_pLeftChild->m_balancedStatus = Balanced;
                        [color=#0000D0]break[/color];
                    }
                    [color=#0000D0]else[/color] [color=#0000D0]if[/color] (m_pRightChild->m_balancedStatus == LeanToLeft)
                    {
                        [color=#008000]// Right rotate and Left rotate[/color]
                        m_pRightChild->RightRotate();
                        LeftRotate();
                        [color=#0000D0]if[/color] ([color=#0000D0]NULL[/color] == m_pRightChild->m_pLeftChild)
                        {                        
                            [color=#0000D0]break[/color];
                        }
                        [color=#0000D0]switch[/color] (m_pRightChild->m_pLeftChild->m_balancedStatus)
                        {
                        [color=#0000D0]case[/color] LeanToRight:
                            m_pLeftChild->m_balancedStatus = LeanToLeft;
                            m_pRightChild->m_balancedStatus = Balanced;
                            [color=#0000D0]break[/color];
                        [color=#0000D0]case[/color] Balanced:
                            m_pLeftChild->m_balancedStatus = Balanced;
                            m_pRightChild->m_balancedStatus = Balanced;
                            [color=#0000D0]break[/color];
                        [color=#0000D0]case[/color] LeanToLeft:
                            m_pLeftChild->m_balancedStatus = Balanced;
                            m_pRightChild->m_balancedStatus = LeanToRight;
                            [color=#0000D0]break[/color];
                        }
                    }
                    m_balancedStatus = Balanced;
                    [color=#0000D0]break[/color];
                }
            }
        }
        [color=#0000D0]return[/color] _fAppend;
    }
     
    [color=#008000]// If the balanced tree. if sucessed return the depth of tree.[/color]
    [color=#008000]// failed return -1[/color]
    [color=#0000D0]int[/color] IsBalanced()
    {
        [color=#0000D0]int[/color] _nLeftDepth = 0, _nRightDepth = 0;
        [color=#0000D0]if[/color] ([color=#0000D0]NULL[/color] != m_pLeftChild)
        {
            _nLeftDepth = m_pLeftChild->IsBalanced();[color=#008000]// Get left child tree depth[/color]
        }
        [color=#0000D0]if[/color] ([color=#0000D0]NULL[/color] != m_pRightChild)
        {
            _nRightDepth = m_pRightChild->IsBalanced();[color=#008000]// Get right child tree depth[/color]
        }
        [color=#0000D0]if[/color] (-1 == _nLeftDepth || -1 == _nRightDepth ||
            abs(_nLeftDepth - _nRightDepth) > 1)[color=#008000]// |ldepth - rdepth|  > 1[/color]
        {
            [color=#0000D0]return[/color] -1;
        }
        [color=#0000D0]else[/color] [color=#0000D0]if[/color] (_nLeftDepth >= _nRightDepth)
        {
            [color=#0000D0]return[/color] _nLeftDepth + 1;[color=#008000]// return left child depth[/color]
        }
        [color=#0000D0]else[/color]
        {
            [color=#0000D0]return[/color] _nRightDepth + 1;[color=#008000]// return right child depth[/color]
        }
    }
     
    [color=#008000]// Make a tree by a data array[/color]
    [color=#0000D0]static[/color] [color=#0000D0]void[/color] MakeTree(T *pData, [color=#0000D0]int[/color] nSize, CBalancedTree<T>& [color=#0000D0]out[/color])
    {
        [color=#b000b0]assert[/color](nSize > 0);
        [color=#0000D0]out[/color].SetData(pData[0]);
        [color=#0000D0]for[/color] ([color=#0000D0]int[/color] i = 1; i <= nSize; i++)
        {
            [color=#0000D0]out[/color].Insert(pData[i]);
        }
    }
};

[招生]科锐逆向工程师培训(2025年3月11日实地，远程教学同时开班, 第52期)！

收藏
免费 ・7
支持
分享
赞赏记录
参与人
雪币
留言
时间
Youlor
为你点赞~
2024-1-3 04:17
伟叔叔
为你点赞~
2023-10-31 00:08
QinBeast
为你点赞~
2023-8-9 00:00
PLEBFE
为你点赞~
2023-8-5 05:23
shinratensei
为你点赞~
2023-7-15 00:17
心游尘世外
为你点赞~
2023-7-5 00:10
飘零丶
为你点赞~
2023-6-25 00:41
最新回复 (1)
likunkun
雪    币： 334
活跃值： (22)
能力值： ( LV4，RANK：50 )
在线值：
发帖
回帖
粉丝
私信
2 楼
期待AVL树的删除操作~~
2008-6-14 13:15
0
游客
登录 | 注册 方可回帖
回帖 表情 雪币赚取及消费
高级回复
返回

账号登录
验证码登录

忘记密码？
没有账号？立即免费注册
我已同意 《看雪服务条款》 《看雪课程免责声明》 《看雪隐私政策》