news 2026/10/4 12:35:38

C++ 超详细快速掌握二叉搜索树

作者头像

张小明

前端开发工程师

1.2k 24
文章封面图
C++ 超详细快速掌握二叉搜索树

二叉搜索树概念与操作

二叉搜索树的概念

二叉搜索树又称二叉排序树，若它的左子树不为空，则左子树上所有节点的值都小于根节点的值；若它的右子树不为空，则右子树上所有节点的值都大于根节点的值，它的左右子树也分别未二叉搜索树。也可以是一颗空树。

int a[] = { 5, 3, 4, 1, 7, 8, 2, 6, 0, 9 };

二叉搜索树的操作

查找

迭代：

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

Node* Find(constK& key)

{

Node* cur = _root;

while(cur)

{

if(cur->_key < key)

{

cur = cur->_right;

}

elseif(cur->_key > key)

{

cur = cur->_left;

}

else

{

returncur;

}

}

returnnullptr;

}

递归：

1

2

3

4

5

6

7

8

9

10

11

12

Node* _FindR(Node* root,constK& key)

{

if(root == nullptr)

returnnullptr;

if(root->_key < key)

return_FindR(root->_right, key);

elseif(root->_key > key)

return_FindR(root->_left, key);

else

returnroot;

}

插入

树为空，则直接插入

树不为空，按二叉搜索树性质查找插入位置，插入新节点

迭代：

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

boolInsert(constK& key)

{

if(_root == nullptr)

{

_root =newNode(key);

returntrue;

}

//查找要插入的位置

Node* parent = nullptr;

Node* cur = _root;

while(cur)

{

if(cur->_key < key)

{

parent = cur;

cur = cur->_right;

}

elseif(cur->_key > key)

{

parent = cur;

cur = cur->_left;

}

else

{

returnfalse;

}

}

cur =newNode(key);

if(parent->_key < cur->_key)

{

parent->_right = cur;

}

else

{

parent->_left = cur;

}

returntrue;

}

递归：

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

bool_InsertR(Node*& root,constK& key)

{

if(root == nullptr)

{

root =newNode(key);

returntrue;

}

else

{

if(root->_key < key)

{

return_InsertR(root->_left, key);

}

elseif(root->_key > key)

{

return_InsertR(root->_left, key);

}

else

{

returnfalse;

}

}

}

删除

首先查找元素是否在二叉搜索树中，如果不存在，则返回，否则要删除的结点可能分下面四种情况：

  • 要删除的结点无孩子结点
  • 要删除的结点只有左孩子结点
  • 要删除的结点只有右孩子结点
  • 要删除的结点只有左、右结点

实际情况中1和2或3可以合并，因此真正的删除过程如下：

  • 删除该结点且使被删除结点的双亲结点指向被删除结点的左孩子结点
  • 删除该结点且使被删除结点的双亲结点指向被删除结点的右孩子结点
  • 替代法。在它的右子树中寻找中序下的第一个结点（关键码最小），用它的值填补到被删除结点中，再来处理该结点的删除问题。

迭代：

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

boolErase(constK& key)

{

Node* parent = nullptr;

Node* cur = _root;

while(cur)

{

if(cur->_key < key)

{

parent = cur;

cur = cur->_right;

}

elseif(cur->_key > key)

{

parent = cur;

cur = cur->_left;

}

else

{

//删除

if(cur->_left == nullptr)

{

if(cur == _root)

{

_root = cur->_right;

}

else

{

if(cur == parent->_left)

{

parent->_left = cur->_right;

}

else

{

parent->_right = cur->_right;

}

}

deletecur;

}

elseif(cur->_right == nullptr)

{

if(cur == _root)

{

_root = cur->_left;

}

else

{

if(cur == parent->_left)

{

parent->_left = cur->_left;

}

else

{

parent->_right = cur->_left;

}

}

}

else

{

//找到右树最小节点去替代删除

Node* minRightParent = cur;

Node* minRight = cur->_right;

while(minRight->_left)

{

minRightParent = minRight;

minRight = minRight->_left;

}

cur->_key = minRight->_key;

if(minRight == minRightParent->_left)

minRightParent->_left = minRight->_right;

else

minRightParent->_right = minRight->_right;

deleteminRight;

}

returntrue;

}

}

returnfalse;

}

递归：

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

bool_EraseR(Node*& root,constK& key)

{

if(root == nullptr)

returnfalse;

if(root->_key < key)

{

return_EraseR(root->_right, key);

}

elseif(root->_key > key)

{

return_EraseR(root->_left, key);

}

else

{

//删除

Node* del = root;

if(root->_left == nullptr)

{

root = root->_right;

}

elseif(root->_right == nullptr)

{

root = root->_left;

}

else

{

//替代法删除

Node* minRight = root->_right;

while(minRight->_left)

{

minRight = minRight->_left;

}

root->_key = minRight->_key;

//转换成递归在右子树中删除最小节点

return_EraseR(root->_right, minRight->_key);

}

deletedel;

returntrue;

}

}

二叉搜索树的应用

1.K模型：K模型即只有key作为关键码，结构中只需要存储key即可，关键码即为需要搜索到的值。比如：给一个单词word，判断该单词是否拼写正确。具体方法如下：1.以单词集合中的每个单词作为key，构建一棵二叉搜索树。2.在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。

2.KV模型：每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。该种方式在现实生活中非常常见：比如英汉词典就是英语与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文<word, chinese>就构成一种键值对；再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是<word, count>就构成一种键值对。

比如：实现一个简单的英汉词典dict，可以通过英文找到与其对应的中文，具体实现方式如下：1.<单词，中文含义>为键值对构造二叉搜索树，注意：二叉搜索树需要比较，键值对比较时只比较Key。2.查询英文单词时，只需要给出英文单词，就可快速找到与其对应的Key。

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

namespaceKEY_VALUE {

template<classK,classV>

structBSTreeNode

{

BSTreeNode<K, V>* _left;

BSTreeNode<K, V>* _right;

K _key;

V _value;

BSTreeNode(constK& key,constV& value)

:_left(nullptr)

,_right(nullptr)

,_key(key)

,_value(value)

{}

};

template<classK,classV>

classBSTree {

typedefBSTreeNode<K, V> Node;

public:

V& operator[](constK& key)

{

pair<Node*,bool> ret = Insert(key, V());

returnret.first->_value;

}

pair<Node*,bool> Insert(constK& key,constV& value)

{

if(_root == nullptr)

{

_root =newNode(key, value);

returnmake_pair(_root,true);

}

//查找要插入的位置

Node* parent = nullptr;

Node* cur = _root;

while(cur)

{

if(cur->_key < key)

{

parent = cur;

cur = cur->_right;

}

elseif(cur->_key > key)

{

parent = cur;

cur = cur->_left;

}

else

{

returnmake_pair(cur,false);

}

}

cur =newNode(key, value);

if(parent->_key < cur->_key)

{

parent->_right = cur;

}

else

{

parent->_left = cur;

}

returnmake_pair(cur,true);

}

Node* Find(constK& key)

{

Node* cur = _root;

while(cur)

{

if(cur->_key < key)

{

cur = cur->_right;

}

elseif(cur->_key > key)

{

cur = cur->_left;

}

else

{

returncur;

}

}

returnnullptr;

}

boolErase(constK& key)

{

Node* cur = _root;

Node* parent = nullptr;

while(cur)

{

if(cur->_key < key)

{

parent = cur;

cur = cur->_right;

}

elseif(cur->_key > key)

{

parent = cur;

cur = cur->_left;

}

else

{

//删除

if(cur->_left == nullptr)

{

if(cur == _root)

{

_root = cur->_right;

}

else

{

if(cur == parent->_left)

{

parent->_left = cur->_left;

}

else

{

parent->_right = cur->_right;

}

}

deletecur;

}

elseif(cur->_right == nullptr)

{

if(cur == _root)

{

_root = cur->_left;

}

else

{

if(cur == parent->_left)

{

parent->_left = cur->_left;

}

else

{

parent->_right = cur->_right;

}

}

deletecur;

}

else

{

//找到右树最小结点去替代删除

Node* minRightParent = cur;

Node* minRight = cur->_left;

while(minRight->_left)

{

minRightParent = minRight;

minRight = minRight->_left;

}

cur->_key = minRight->_key;

if(minRight = minRightParent->_left)

minRightParent->_left = minRight->right;

else

minRightParent->_right = minRight->_right;

deleteminRight;

}

returntrue;

}

}

returnfalse;

}

voidInOrder()

{

_InOrder(_root);

cout << endl;

}

private:

void_InOrder(Node* root)

{

if(root == nullptr)

{

return;

}

_InOrder(root->_left);

cout << root->_key <<":"<< root->_value << endl;

_InOrder(root->_right);

}

private:

Node* _root = nullptr;

};

}

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

voidTest2()

{

KEY_VALUE::BSTree<string, string> dict;

dict.Insert("sort","排序");

dict.Insert("insert","插入");

dict.Insert("tree","树");

dict.Insert("right","右边");

string str;

while(cin >> str)

{

if(str =="q")

{

break;

}

else

{

auto ret = dict.Find(str);

if(ret == nullptr)

{

cout <<"拼写错误，请检查你的单词"<< endl;

}

else

{

cout << ret->_key <<"->"<< ret->_value << endl;

}

}

}

}

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

voidTest3()

{

//统计字符串出现次数，也是经典key/value

string str[] = {"sort","sort","tree","insert","sort","tree","sort","test","sort"};

KEY_VALUE::BSTree<string,int> countTree;

//for (auto& e : str)

//{

// auto ret = countTree.Find(e);

// if (ret == nullptr)

// {

// countTree.Insert(e, 1);

// }

// else

// {

// ret->_value++;

// }

//}

for(auto& e : str)

{

countTree[e]++;

}

countTree.InOrder();

}

二叉树的性能分析

插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。

对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，比较的次数越多。

但对于同一个关键码集合，如果关键码插入的次序不同，可能得到不同结构的二叉搜索树

最优情况下，二叉搜索树为完全二叉树，其平均比较次数为：logN

最差情况下，二叉搜索树退化为单支树，其平均比较次数为：N/2


版权声明: 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：809451989@qq.com进行投诉反馈，一经查实，立即删除！
网站建设 2026/10/4 12:32:03

公司内部服务器搭建：从选型到部署的避坑指南

简介&#xff1a;面向企业管理者及技术选型人员的《公司内部服务器搭建-企业服务器搭建方案》文档&#xff0c;聚焦“小公司到底需不需要买服务器”这一核心困惑&#xff0c;围绕如何设置公司服务器展开。文档结合典型业务场景给出选型思路&#xff1a;小型Web/APP、企业官网等…

作者头像 李华
网站建设 2026/10/4 12:30:52

SkillClaw 实战：用 Agentic Evolver 让 LLM 智能体技能集体进化

/* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

作者头像 李华
网站建设 2026/10/4 12:15:03

DeepSeek Harness 插件实战：dsh plugin 命令与内网部署指南

1. 从一条命令说起&#xff1a;dsh plugin 到底解决了什么问题第一次接触 DeepSeek Harness 的人&#xff0c;大概率会被它那一堆子命令绕晕。dsh web、dsh plugin、dsh skill、dsh agent&#xff0c;每个词单拎出来都认识&#xff0c;拼在一起就不知道从哪下手。我最初也是这个…

作者头像 李华
网站建设 2026/10/4 12:14:27

Java咖啡厅系统实战：高并发订单与跨浏览器兼容方案

简介&#xff1a;本资源是一份面向计算机专业本科生的毕业设计文档&#xff0c;聚焦基于Java技术栈的咖啡厅管理系统开发实践&#xff0c;适用于课程设计、毕设参考及Web应用开发初学者。文档完整覆盖系统需求分析、JSP前端实现、MySQL数据库设计&#xff08;含E-R图与逻辑建模…

作者头像 李华