-
Notifications
You must be signed in to change notification settings - Fork 1.5k
/
main.cpp
77 lines (61 loc) · 1.65 KB
/
main.cpp
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
#include <iostream>
using namespace std;
// 二分搜索树
template <typename Key, typename Value>
class BST{
private:
// 树中的节点为私有的结构体, 外界不需要了解二分搜索树节点的具体实现
struct Node{
Key key;
Value value;
Node *left;
Node *right;
Node(Key key, Value value){
this->key = key;
this->value = value;
this->left = this->right = NULL;
}
};
Node *root; // 根节点
int count; // 树中的节点个数
public:
// 构造函数, 默认构造一棵空二分搜索树
BST(){
root = NULL;
count = 0;
}
~BST(){
// TODO: ~BST()
}
// 返回二分搜索树的节点个数
int size(){
return count;
}
// 返回二分搜索树是否为空
bool isEmpty(){
return count == 0;
}
// 向二分搜索树中插入一个新的(key, value)数据对
void insert(Key key, Value value){
root = insert(root, key, value);
}
private:
// 向以node为根的二分搜索树中, 插入节点(key, value), 使用递归算法
// 返回插入新节点后的二分搜索树的根
Node* insert(Node *node, Key key, Value value){
if( node == NULL ){
count ++;
return new Node(key, value);
}
if( key == node->key )
node->value = value;
else if( key < node->key )
node->left = insert( node->left , key, value);
else // key > node->key
node->right = insert( node->right, key, value);
return node;
}
};
int main() {
return 0;
}