什么是二叉搜索树

二叉搜索树的定义是一颗二叉树的所有节点满足:根的左右孩子存在时，满足 左孩子 < 根 < 右孩子

递归定义则是:

  1. 左子树的根 < 根 < 右子树的根
  2. 左子树是二叉搜索树,右子树是二叉搜索树

写一个验证二叉搜索树的函数

Leetecode题目链接🔗

封装一个二叉树类

文件布置

  • BSTree.h用于声明和实现BSTree类
  • test.cpp用于测试

头文件

BSTree.h

1
2
3
#include <iostream>
#include <utility>

test.cpp

1
#include "BSTree.h"

命名空间

1
namespace key_value

这里使用key_value作为命名空间，表示这是键值表示的搜索二叉树

定义节点

二叉树的节点用于储存键值对和左右指针，并提供默认构造函数,使用初始化列表初始化成员变量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template<class K,class V>
class BSTNode
{
public:
    BSTNode(const K& key = K(), const V& value = V())
        :_left(nullptr)
        , _right(nullptr)
        , _key(key)
        , _value(value)
    {}
    BSTNode<K, V>* _left;//指向左子树
    BSTNode<K, V>* _right;//指向右子树
    K _key;//储存键
    V _value;//储存值
};

封装二叉搜索树

Binary Search Tree,这里用简称BSTree封装

基本架构

鉴于该类的接口基本依赖于成员变量，所以先组织好成员变量

作为一颗二叉树类,成员变量仅需一个指向根的指针即可

再次之前先用typedef定义一个节点类出来用于简化代码

最后提供一个默认构造函数将_root初始化为nullptr

1
2
3
4
5
6
7
8
9
template<class K,class V>
class BSTree
{
	typedef BSTNode<K, V> Node;//使用typedef简化代码
public:
	BSTree() :_root(nullptr) {}//提供默认构造函数
private:
	Node* _root;//指向根节点的指针作为成员变量
};

insert函数

准备好后第一个接口就是insert,用于构建搜索二叉树

这里需要考虑的情况有

  • 空树时的插入
  • 插入的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
public:
bool insert(const K& key, const V& value)
{
    if (_root == nullptr)//空树
    {
        _root = new Node(key, value);
        return true;
    }

    Node* cur = _root;
    Node* parent = nullptr;
    while (cur)
    {
        if (key < cur->_key)//key比当前节点小，往左子树走
        {
            parent = cur;
            cur = cur->_left;
        }
        else if (key > cur->_key)//往右子树走
        {
            parent = cur;
            cur = cur->_right;
        }
        else
        {
            return false;//key已存在，插入失败
        }
    }
    //此时cur为nullptr, parent为cur的结点
    if (key < parent->_key)parent->_left = new Node(key, value);
    else parent->_right = new Node(key, value);
    return true;//成功插入
}

in_order函数

使用此函数前序遍历打印二叉树来验证其满足搜索树的性质

这里使用递归打印,所以要借助_in_order子函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public:
    void in_order()
    {
        _in_order(_root);//传入根结点
        std::cout << std::endl;
    }
protected:
    void _in_order(Node* root)
    {
        if (root == nullptr) return;
        _in_order(root->_left);//先访问左结点
        std::cout << root->_value << " " << std::endl;//再访问根结点
        _in_order(root->_right);//最后访问右结点
    }

然后写一段测试代码测试性质

test.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include "BSTree.h"
#include <vector>
using namespace std;
int main()
{
	vector<int> arr({ 2,3,1,5,4,6,8,7 });//准备待插入的键值对
	key_value::BSTree<int, int> bst;
	for (int i = 0; i < arr.size(); ++i)
	{
		bst.insert(arr[i],arr[i]);//这里使键值相同，方便观察
	}

	bst.in_order();//测试

	return 0;
}

find函数

可以用find函数查找对应key的结点。

同时观察可知，控制cur和parent的移动的代码段和前面的函数很像，所以给find函数分出来一个_find子函数，并使它返回pair<Node*,Node*>，将这两个指针返回利于其它函数对_find的回调

同时为了简化代码，继续用typedef封装类型

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
public:
    typedef std::pair< Node*, Node* > PNN;//简化代码
    bool find(const K& key)
    {
        return _find(key).first != nullptr;//检查是否找到
    }
protected:

    PNN _find(const K& key)//返回PNN用于简化其它接口
    {
        if (_root == nullptr) return {nullptr,nullptr};
        Node* cur = _root;
        Node* parent = nullptr;
        while (cur)
        {
            if (key < cur->_key)//key比当前节点小，往左子树走
            {
                parent = cur;
                cur = cur->_left;
            }
            else if (key > cur->_key)//往右子树走
            {
                parent = cur;
                cur = cur->_right;
            }
            else
            {
                //找到key
                return { cur,parent };
            }
        }
        //没找到key,cur为nullptr
        return { nullptr,parent };
    }

重写insert函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
bool insert(const K& key, const V& value)
{
    if (_root == nullptr)//空树
    {
        _root = new Node(key, value);
        return true;
    }
    //====修改的部分====
    PNN pnn = _find(key);

    Node* cur = pnn.first;
    Node* parent = pnn.second;

    if (cur != nullptr)//该key已存在，插入失败
    {
        return false;
    }
    //================
    
    //此时cur为nullptr, parent为cur的结点
    if (key < parent->_key)parent->_left = new Node(key, value);
    else parent->_right = new Node(key, value);
    return true;//成功插入
}

erase函数

这里也可以复用_find来方便地删除结点

这里要考虑的情况有:

  • 树为空
  • 删除最后一个结点
  • 删除根节点
  • 左子树为空（包括叶子结点）
  • 右子树为空
  • 删除一般的结点

当树有>=2个结点，且要删除非叶子结点时，要考虑结点替换，否则二叉树会断掉，这里一般两种策略，取左子树的最右结点（最大结点），或取右子树的最左结点（最小结点）

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
public:
    bool erase(const K& key)
    {
        if (_root == nullptr)return false;//空树无法删除
        if (_root->_key == key && _root->_left == nullptr && _root->_right == nullptr)//删除最后一个结点
        {
            delete _root;
            _root = nullptr;
        }
        PNN pnn = _find(key);
        Node* cur = pnn.first;
        Node* parent = pnn.second;
        if (cur == nullptr) return false;//没找到该结点

        //下面的cur必不为空
        if(cur->_left == nullptr)
        {
            if (cur == _root)//为根节点时要替换根节点
            {
                Node* right = _root->_right;
                delete _root;
                _root = right;
            }
            //没有左子树，则直接移除结点,右子树替代原结点
            if (cur == parent->_left) parent->_left = cur->_right;
            else parent->_right = cur->_right;
            delete cur;
        }
        else if (cur->_right == nullptr)
        {
            if (cur == _root)
            {
                Node* left = _root->_left;
                delete _root;
                _root = left;
            }
            //直接过继左子树
            if (cur == parent->_left)parent->_left = cur->_left;
            else parent->_right = cur->_left;
        }
        else 
        {
            //找到左子树的最右结点
            Node* _cur = cur->_left;
            Node* _parent = cur;
            while (_cur->_right != nullptr)
            {
                _parent = _cur;
                _cur = _cur->_right;
            }
            //移走结点
            if (_cur == _parent->_left) _parent->_left = nullptr;
            else _parent->_right = nullptr;
            //获取cur的左右结点,必须再移走结点后，否则可能出现指向自己的结点
            _cur->_left = cur->_left;
            _cur->_right = cur->_right;
            //代替cur的位置
            if (cur == _root)//删除根结点时
            {
                delete _root;
                _root = _cur;
            }
            else//删除普通结点时
            {
                if (cur == parent->_left) parent->_left = _cur;
                else parent->_right = _cur;
                delete cur;
            }

        }
        return true;
    }

拷贝构造

利用二叉树的性质，可以再构建个copy子函数来递归拷贝

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public:
    BSTree(const BSTree<K>& t)
    {
        _root = Copy(t._root);
    }
protected:
    Node* copy(Node* root)
    {
        if (root == nullptr) return nullptr;//递归出口
        Node* pnode = new Node(root->_key, root->_value);//复制结点
        pnode->_left = copy(root->_left);
        pnode->_right = copy(root->_right);
        return pnode;
    }

析构函数

这里也用destroy子函数来递归地后序遍历依次删除各个结点

1
2
3
4
5
6
7
8
9
10
11
12
13
public:
    ~BSTree()
    {
        destroy(_root);
    }
protected:
    void destroy(Node* root)
    {
        if (root == nullptr) return;
        destroy(root->_left);
        destroy(root->_right);
        delete root;
    }

至此，一个基本的二叉搜索树已封装完成

实现的功能有

  • 构建二叉搜索树
  • 拷贝复制二叉树
  • 按key值查找
  • 按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
202
203
204
205
206
207
208
209
#pragma once
#include <iostream>
#include <utility>

namespace key_value
{
	template<class K,class V>
	class BSTNode
	{
	public:
		BSTNode(const K& key = K(), const V& value = V())
			:_left(nullptr)
			, _right(nullptr)
			, _key(key)
			, _value(value)
		{}
		BSTNode<K, V>* _left;//指向左子树
		BSTNode<K, V>* _right;//指向右子树
		K _key;//储存键
		V _value;//储存值
	};

	template<class K,class V>
	class BSTree
	{
		typedef BSTNode<K, V> Node;//使用typedef简化代码
	public:
		BSTree() :_root(nullptr) {}//提供默认构造函数

		BSTree(const BSTree<K, V>& bst)
		{
			_root = copy(bst._root);
		}

		~BSTree()
		{
			destroy(_root);
		}

		bool insert(const K& key, const V& value)
		{
			if (_root == nullptr)//空树
			{
				_root = new Node(key, value);
				return true;
			}
			//====修改的部分====
			PNN pnn = _find(key);

			Node* cur = pnn.first;
			Node* parent = pnn.second;

			if (cur != nullptr)//该key已存在，插入失败
			{
				return false;
			}
			//================
			
			//此时cur为nullptr, parent为cur的结点
			if (key < parent->_key)parent->_left = new Node(key, value);
			else parent->_right = new Node(key, value);
			return true;//成功插入
		}

		void in_order()
		{
			_in_order(_root);//传入根结点
			std::cout << std::endl;
		}
	protected:
		void _in_order(Node* root)
		{
			if (root == nullptr) return;
			_in_order(root->_left);//先访问左结点
			std::cout << root->_value << " ";//再访问根结点
			_in_order(root->_right);//最后访问右结点
		}


	public:
		typedef std::pair< Node*, Node* > PNN;//简化代码
		bool find(const K& key)
		{
			return _find(key).first != nullptr;//检查是否找到
		}
	protected:
	
		PNN _find(const K& key)//返回PNN用于简化其它接口
		{
			if (_root == nullptr) return {nullptr,nullptr};
			Node* cur = _root;
			Node* parent = nullptr;
			while (cur)
			{
				if (key < cur->_key)//key比当前节点小，往左子树走
				{
					parent = cur;
					cur = cur->_left;
				}
				else if (key > cur->_key)//往右子树走
				{
					parent = cur;
					cur = cur->_right;
				}
				else
				{
					//找到key
					return { cur,parent };
				}
			}
			//没找到key,cur为nullptr
			return { nullptr,parent };
		}
	public:

		bool erase(const K& key)
		{
			if (_root == nullptr)return false;//空树无法删除
			if (_root->_key == key && _root->_left == nullptr && _root->_right == nullptr)//删除最后一个结点
			{
				delete _root;
				_root = nullptr;
			}
			PNN pnn = _find(key);
			Node* cur = pnn.first;
			Node* parent = pnn.second;
			if (cur == nullptr) return false;//没找到该结点

			//下面的cur必不为空
			if(cur->_left == nullptr)
			{
				if (cur == _root)//为根节点时要替换根节点
				{
					Node* right = _root->_right;
					delete _root;
					_root = right;
				}
				//没有左子树，则直接移除结点,右子树替代原结点
				if (cur == parent->_left) parent->_left = cur->_right;
				else parent->_right = cur->_right;
				delete cur;
			}
			else if (cur->_right == nullptr)
			{
				if (cur == _root)
				{
					Node* left = _root->_left;
					delete _root;
					_root = left;
				}
				//直接过继左子树
				if (cur == parent->_left)parent->_left = cur->_left;
				else parent->_right = cur->_left;
			}
			else 
			{
				//找到左子树的最右结点
				Node* _cur = cur->_left;
				Node* _parent = cur;
				while (_cur->_right != nullptr)
				{
					_parent = _cur;
					_cur = _cur->_right;
				}
				//移走结点
				if (_cur == _parent->_left) _parent->_left = nullptr;
				else _parent->_right = nullptr;
				//获取cur的左右结点,必须再移走结点后，否则可能出现指向自己的结点
				_cur->_left = cur->_left;
				_cur->_right = cur->_right;
				//代替cur的位置
				if (cur == _root)//删除根结点时
				{
					delete _root;
					_root = _cur;
				}
				else//删除普通结点时
				{
					if (cur == parent->_left) parent->_left = _cur;
					else parent->_right = _cur;
					delete cur;
				}

			}
			return true;
		}


	protected:
		Node* copy(Node* root)
		{
			if (root == nullptr) return nullptr;//递归出口
			Node* pnode = new Node(root->_key, root->_value);//复制结点
			pnode->_left = copy(root->_left);
			pnode->_right = copy(root->_right);
			return pnode;
		}

		void destroy(Node* root)
		{
			if (root == nullptr) return;
			destroy(root->_left);
			destroy(root->_right);
			delete root;
		}
	private:
		Node* _root;//指向根节点的指针作为成员变量
	};
}