二叉树的常用操作

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
//
// Created by maochongxin on 2018/7/31.
// Copyright © 2018 maochongxin. All rights reserved.
//

#include <iostream>
#include <algorithm>
//#include <boost/array.hpp>
//#include <boost/lockfree/queue.hpp>
//#include <boost/lambda/lambda.hpp>
#include <queue>
using namespace std;

template <class T>
struct Node {
T data;
Node* Left;
Node* Right;
Node():data(0),Left(NULL),Right(NULL){};
};

template <class T>
class BinTree {
private:
Node<T>* root;
protected:
bool _empty() { return root == NULL; }
Node<T>* _Create(T* arr,size_t lengh,const T& invalid,size_t& index) { //index需要写引用的原因是C++的函数有值传递当递归到下一层,会重新开辟一块栈空间,这时候会新生成一个index,这个index不会影响上一层的index,因此必须传指针或者传引用
Node<T>* root = NULL;
if(index < lengh && arr[index] != invalid) {
root = new Node<T>();
root -> data = arr[index];
root -> Left = _Create(arr, lengh, invalid, ++index);
root -> Right = _Create(arr, lengh, invalid, ++index);
}
return root;
}
//拷贝构造
Node<T>* _Copy(const Node<T>* root) {
if(root == NULL) {
return NULL;
}
Node<T>* copyroot = new Node<T>();
copyroot -> data = root -> data;
copyroot -> Left = _Copy(root -> Left);
copyroot -> Right = _Copy(root -> Right);
return copyroot;
}
//前序遍历
void _PreOrder(Node<T>* root) {
if(root == NULL) {
return;
}
cout << root -> data << endl;
_PreOrder(root -> Left);
_PreOrder(root -> Right);
}
//中序遍历
void _InOrder(Node<T>* root) {
if(root == NULL) {
return;
}
_InOrder(root -> Left);
cout << root -> data << endl;
_InOrder(root -> Right);
}
//后序遍历
void _PostOrder(Node<T>* root) {
if(root == NULL) {
return;
}
_PreOrder(root -> Left);
_PreOrder(root -> Right);
cout << root -> data << endl;
}
//层序遍历
void _LevelOrder(Node<T>* root) {
// boost::lockfree::queue<Node<T>*,boost::lockfree::fixed_sized<false> > que;
queue<Node<T>*> que;
if(root) {
que.push(root);
} else {
return;
}
while (!que.empty()) {
Node<T>* cur = que.front();
que.pop();
cout << cur -> data << endl;
if(cur -> Left) {
que.push(cur -> Left);
}
if(cur -> Right) {
que.push(cur -> Right);
}
}
cout << endl;
return ;
}
//节点个数
size_t _Size(Node<T>* root) {
if(root == NULL) {
return 0;
}
if((root -> Left == NULL && root -> Right == NULL)) {
return 1;
}
return _Size(root -> Left) + _Size(root -> Right) + 1;
}
//第K层节点数目
size_t _K_Level_Size(Node<T>* root,int K) {
if(root == NULL) {
return 0;
} else if(K == 1) {
return 1;
} else if(K > 1) {
return _K_Level_Size(root -> Left, K - 1) + _K_Level_Size(root -> Right, K - 1);
} else
return 0;
}

//深度
size_t _Depth(Node<T>* root) {
if(root == NULL) {
return 0;
}
if(root -> Left == NULL && root -> Right == NULL) {
return 1;
}
size_t leftDepth = _Depth(root -> Left);
size_t rightDepth = _Depth(root -> Right);
return max(leftDepth, rightDepth) + 1; //+1是根节点
}

//翻转 HomeBrew作者没写出来的那个🐶
void _Reverise(Node<T>* root) {
if(root == NULL) {
return ;
}
swap(root -> Left, root -> Right);
_Reverise(root -> Left);
_Reverise(root -> Right);
}
void _Destory(Node<T>* root) {
if(root == NULL) {
return;
}
_Destory(root -> Left);
_Destory(root -> Right);
delete root;
root = NULL;

}
public:
BinTree():root(NULL){}
BinTree(T* arr,const T& invalid,size_t len) {
size_t index = 0;
root = _Create(arr, len, invalid,index);
}
BinTree(const BinTree<T>& t) {
root = _Copy(t.root);
}
void PreOrder() {
_PreOrder(root);
cout << endl;
return;
}
void InOrder() {
_InOrder(root);
cout << endl;
return;
}
void PostOrder() {
_PostOrder(root);
cout << endl;
return;
}
void LevelOrder() {
_LevelOrder(root);
cout << endl;
return;
}
size_t Size() {
return _Size(root);
}

size_t K_Level_Size(int K) {
return _K_Level_Size(root, K);
}

size_t Depth() {
return _Depth(root);
}

void Reverse() {
_Reverise(root);
}

~BinTree() {
_Destory(root);
root = NULL;
}

};

int main(int argc, const char * argv[]) {
int arr[] = {1, 2, 3, '#', '#', 4, '#', '#', 5, 6};
BinTree<int> bt(arr,'#',sizeof(arr) / sizeof(arr[0]));

bt.PreOrder();
cout << "-------" << endl;
bt.InOrder();
cout << "-------" << endl;
bt.PostOrder();
cout << "-------" << endl;
bt.LevelOrder();
cout << "-------" << endl;
bt.Reverse();
bt.PreOrder();
cout << "-------" << endl;
BinTree<int> bt2(bt);
bt2.PreOrder();

return 0;
}
script>