c++ 树集合实现记录

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
#include<iostream>
#include<stack>
#include<queue>
using namespace std;
template<class Elem>
struct BinNode//定义二叉树链表
{
Elem data;
BinNode <Elem>* left;
BinNode <Elem>* right;
int h;
BinNode(Elem x) {
//初始化
data = x;
h = -1;
left = right = NULL;
}
};
//定义某种类的模板类型复杂数据时需要用 类名<..> 来声明类型
template<class Elem>
class BinTree {
protected:
BinNode<Elem>* root;
void rpreprint(BinNode<Elem>* r) {
//递归遍历
if (r == NULL) return;
cout << r->data << " ";
rpreprint(r->left);
rpreprint(r->right);
}
BinNode<Elem>* rfindx(Elem x, BinNode<Elem>* r) {
//树为空树,或者没找到
if (!r) return NULL;
//刚好找到了
if (r->data == x) return r;
//遍历查找
BinNode<Elem>* found;
found = rfindx(x, r->left);
//不在左边，就在右边或者不存在
// .....？ x:y 三元表达式
return found ? found : rfindx(x, r->right);
}
void rprint(BinNode<Elem>* r, int depth) {
for (int i = 0; i < depth; i++) {
cout << "
";//深度越大，打印的空格越多
}
if (!r) {
cout << "[/]" << endl;
}
else
{
cout << r->data << endl;
rprint(r->left, depth + 1);//先打印左
rprint(r->right, depth + 1);//后打印右
}
}
void rinprint(BinNode<Elem>* r) {
//递归遍历
if (r == NULL) return;
rpreprint(r->left);
cout << r->data << " ";
rpreprint(r->right);
}
void rbackprint(BinNode<Elem>* r) {
//递归遍历
if (r == NULL) return;
rpreprint(r->left);
rpreprint(r->right);
cout << r->data << " ";
}
void ipreprint(BinNode<Elem>* r) {
//用stack是为了记录路径
stack<BinNode<Elem>*> st;
if (!r) return;
while (r)
{
cout << r->data << ' ';
st.push(r);
r = r->left;
while (r == NULL && !st.empty()) {
r = st.top();
st.pop();
r = r->right;
}
}
}
void i_in_print(BinNode<Elem>* r) {
//用stack是为了记录路径
stack<BinNode<Elem>*> st;
if (!r) return;
while (r)
{
st.push(r);
r = r->left;
while (r == NULL && !st.empty()) {
r = st.top();
st.pop();
cout << r->data << ' ';
r = r->right;
}
}
}
public://public部分是接口，不显示细节
BinTree() { root = NULL; }
BinTree(Elem r) {
root = new BinNode<Elem>(r);
}
~BinTree() { }
void preprint() {
//
rpreprint(root);
ipreprint(root);
cout << endl;
}
void in_print() {
//
rinprint(root);
cout << endl;
}
BinNode<Elem>* findX(Elem x) {
return rfindx(x, root);
}
bool insert(Elem p, int l_or_r, Elem x) {
//首先找到p节点
BinNode<Elem>* found;
found = findX(p);
if (!found) return false;
if (l_or_r == 0) {
//左边
//类的函数使用类的指针来操作较方便
if (found->left) return false;
//通过new来直接插入
found->left = new BinNode<Elem>(x);
}
else
{
if (found->right) return false;
found->right = new BinNode<Elem>(x);
}
return true;
}
void print_tree() {
rprint(root, 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
#include<iostream>
#include"bintree.h"
using namespace std;
template<class Elem>
class BSTree :public BinTree<Elem> {
protected:
BinNode<Elem>* rfindMax(BinNode<Elem>* r) {
if (r->right == NULL) return r;
return rfindMax(r->right);//尾递归
}
BinNode<Elem>* rinsert(Elem x, BinNode<Elem>* r) {
if (r == NULL) {
r = new BinNode<Elem>(x);
//申请内存失败
if (r == NULL) throw - 1;
return r;
}
//递归插入，当x小于当前值，往左节点插入，直到找到的点为空
else if (x < r->data) {
r->left = rinsert(x, r->left);
}
else if (x > r->data) {
r->right = rinsert(x, r->right);
}
else
{
//等于
throw - 2;
}
return r;
}
BinNode<Elem>* remove(Elem x, BinNode<Elem>* r) {
//r可能为空
BinNode<Elem>* temp;
if (r == NULL) throw - 1;
else if (x < r->data) {
r->left = remove(x, r->left);//更新树根
}
else if (x > r->data) {
r->right = remove(x, r->left);
}
else
{
//节点有两个子节点
if (r->left && r->right) {
temp = rfindMax(r->left);
r->data = temp->data;
r->left = remove(temp->data, r->left);
}
else
{
temp = r;
r = r->left ? r->left : r->right;
delete temp;
}
}
return r;
}
public:
BSTree() {
this->root = NULL;
}
BinNode<Elem>* findMax() {
//return rfindMax(this->root);
BinNode<Elem>* temp;
temp = this->root;
while (temp && temp->right)
{
temp = temp->right;
}
return temp;
}
BinNode<Elem>* findMin() {
BinNode<Elem>* temp;
temp = this->root;
while (temp && temp->left)
{
temp = temp->left;
}
return temp;
}
BinNode< Elem>* findX(Elem x) {
BinNode<Elem>* temp;
temp = this->root;
while (temp && x != temp->data)
{
if (x > temp->data) temp = temp->right;
else temp = temp->left;
}
return temp;
}
bool insert(Elem x) {
//BST不能有重复值
//判断大小
try
{
this->root = rinsert(x, this->root);
}
catch (const std::exception&)
{
return false;
}
return true;
}
//?循环remove
bool remove(Elem x) {
try
{
this->root = remove(x, this->root);
}
catch (const std::exception&)
{
return false;
}
return true;
}
};
int main() {
BSTree<int> bt;
bt.insert(10);
bt.insert(20);
bt.insert(30);
bt.insert(15);
bt.print_tree();
cout << bt.findMax()->data << endl;
cout << bt.findMin()->data << endl;
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
//空树高度为-1
#include<iostream>
#include<math.h>
#include"bst.h"
using namespace std;
template<class Elem>
class Avltree :public BSTree<Elem> {
//class ... : public ...继承
protected:
int height(BinNode<Elem>* r) {
if (r == NULL) return -1;
return r->h;
}
BinNode<Elem>* ll_rotate(BinNode<Elem>* r) {
BinNode<Elem>* temp;
temp = r->left;
r->left = temp->right;
temp->right = r;
r->h = max(height(r->left), height(r->right)) + 1;
temp->h = max(height(temp->left), height(temp->right)) + 1;
return temp;
}
BinNode<Elem>* rr_rotate(BinNode<Elem>* r) {
BinNode<Elem>* temp;
temp = r->right;
r->right = temp->left;
temp->left = r;
r->h = max(height(r->left), height(r->right)) + 1;
temp->h = max(height(temp->left), height(temp->right)) + 1;
return temp;
}
BinNode<Elem>* lr_rotate(BinNode<Elem>* r) {
r->left = rr_rotate(r->left);
return ll_rotate(r);
}
BinNode<Elem>* rl_rotate(BinNode<Elem>* r) {
r->right = ll_rotate(r->right);
return rr_rotate(r);
}
//插入函数加个判断
BinNode<Elem>* rinsert(Elem x, BinNode<Elem>* r) {
if (r == NULL) {
r = new BinNode<Elem>(x);
if (r == NULL) throw - 1;
}
else if (x < r->data)
{
r->left = rinsert(x, r->left);
if (height(r->left) - height(r->right) == 2) {
if (x < r->left->data) {
r = ll_rotate(r);
}
else
{
r = lr_rotate(r);
}
}
}
else if(x > r->data)
{
r->right = rinsert(x, r->right);
if (height(r->right) - height(r->left) == 2) {
if (x > r->right->data) {
r = rr_rotate(r);
}
else
{
r = rl_rotate(r);
}
}
}
else {
throw - 2;
}
r->h = max(height(r->left), height(r->right)) + 1;
return r;
}
public:
Avltree() {
this->root = NULL;
}
};

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
#include<stdio.h>
#include<stdlib.h>
typedef int Elem;
struct Heap
{
Elem* data;
int capcacity;
int size;
};
typedef struct Heap* heap;
heap init_heap(int maxsize) {
//创建堆结构体
heap h;
h = (heap)malloc(sizeof(struct Heap));
if (h == NULL) return NULL;
//创建数组
h->data = (Elem*)malloc(sizeof(Elem) * (maxsize + 1));
if (h->data == NULL) return NULL;
//初始化
h->size = 0;//记录元素个数
h->capcacity = maxsize;//用于记录有效大小，为实际大小减1
return h;
}
void print_heap(heap h) {
for (int i = 1; i < h->size; i++) {
printf("%d ,", h->data[i]);
}
putchar('n');
}
void percolate_up(int k, heap h) {
int x;
//保存k节点的值
x = h->data[k];
int i;
for (i = k; i > 1 && h->data[i] < h->data[i / 2]; i = i / 2) {
//如果i不为树根处，且父节点比子节点更大，交换
h->data[i] = h->data[i / 2];
}
h->data[i] = x;
h->size++;
}
int isfull(heap h) {
return h->capcacity == h->size;
}
int insert_heap(heap h, Elem x) {
if (isfull(h)) return 0;
h->data[++h->size] = x;//插入
percolate_up(h->size, h); //把顺序表向上过滤
return 1;
}
void destroy(heap h) {
free(h->data);
free(h);
}
int main() {
heap h;
h = init_heap(10);
insert_heap(h, 20);
insert_heap(h, 10);
insert_heap(h, 5);
print_heap(h);
destroy(h);
return 0;
}