二叉搜索树——C++

二叉搜索树

概念

（二叉排序树或二叉查找树）
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:

• 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
• 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
• 它的左右子树也分别为二叉搜索树
  最多查找高度次，不是暴力查找了，效率会高很多

 

二叉搜索树的操作

1. 二叉搜索树的查找

a、从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。
b、最多查找高度次，走到到空，还没找到，这个值不存在。

//查找
bool Find(const K& key)
{
   
Node* cur = _root;
while (cur)
{
   
if (cur->_key < key)
{
   
cur = cur->_right;
}
else if (cur->_key > key)
{
   
cur = cur->_left;
}
else//相同
{
   
return true;
}
}

return false;
}
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

 

2. 二叉搜索树的插入

插入的具体过程如下：
a. 树为空，则直接新增节点，赋值给root指针
b. 树不空，按二叉搜索树性质查找插入位置，插入新节点

//插入
bool Insert(const K& key)
{
   
if (_root == nullptr)
{
   
_root = new Node(key);
return true;
}

//先查找插入的位置
//需要parent,前后链接起来
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
   
//插入的值大
if (cur->_key < key)
{
   
parent = cur;
cur = cur->_right;
}
//插入的值小
else if (cur->_key > key)
{
   
parent = cur;
cur = cur->_left;
}
else
{
   
return false;//这个值在树里已经有了就会插入失败
}
}

//赋值
cur = new Node(key);
if (parent->_key < key)
{
   
parent->_right = cur;
}
else
{
   
parent->_left = cur;
}

return true;
}
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

 

3. 二叉搜索树的删除

首先查找元素是否在二叉搜索树中，如果不存在，则返回, 否则要删除的结点可能分下面四种情
况：
a. 要删除的结点无孩子结点
b. 要删除的结点只有左孩子结点
c. 要删除的结点只有右孩子结点
d. 要删除的结点有左、右孩子结点
看起来有待删除节点有4中情况，实际情况a可以与情况b或者c合并起来，因此真正的删除过程

如下：
情况b：删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点–直接删除
情况c：删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点–直接删除
情况d：在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被删除节点中，再来处理该结点的删除问题–替换法删除
左子树的最大节点——左子树最右结点
右子树的最小结点——右子树最左结点
替换结点要么没有孩子，要么只有一个孩子

//删除
bool Erase(const K& key)
{
   
//查找要删除的结点是否存在——不存在就返回FALSE
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
   
if (cur->_key < key)
{
   
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)
{
   
parent = cur;
cur = cur->_left;
}
else//找到了
{
   
// 开始删除
// 1、左为空


if (cur->_left == nullptr)
{
   
//极端情况——删除的是根结点
if (cur == _root)
{
   
//更新根结点
_root = cur->_right;
}
else
{
   
if (cur == parent->_left)
{
   
parent->_left = cur->_right;
}
else
{
   
parent->_right = cur->_right;
}
}

delete cur;
cur = nullptr;
}

// 2、右为空
else if (cur->_right == nullptr)
{
   
if (_root == cur)
{
   
_root = cur->_left;
}
else
{
   
if (cur == parent->_left)
{
   
parent->_left = cur->_left;
}
else
{
   
parent->_right = cur->_left;
}
}

delete cur;
cur = nullptr;
}

// 3、左右都不为空
else
{
   
//可以用左子树最大结点或者右子树最小结点

Node* minParent =
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