数据结构之二叉查找树的定义与实现

发表于 | 分类于

二叉查找树基础

二叉查找树是指一种满足以下性质的二叉树：

1. 对于每个节点X，该节点的所有左子树节点关键字值小于该节点关键字值
2. 该节点的所有右子树节点关键字值大于该节点关键字值
3. 关键字需要支持“>”、“<”、“==”运算符

对于二叉树ADT，一般需要提供如下操作：

  • 清空二叉查找树：MakeEmpty
  • 查找某个节点：Find
  • 删除某个节点：DeleteElement
  • 查找最大值：FindMax
  • 查找最小值：FindMin
  • 插入一个节点：InsertElement

二叉查找树的平均深度为O(log(N))，不过如果插入元素序列递增或者递减，二叉查找树将退化成单链表。

二叉查找树的实现

由于二叉查找树是一种统一排序的查找树，在进行删除插入时需要保持排序关系，以下为二叉查找树的基本结构定义：

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
template <typename DataType>
struct Node
{
	DataType data;
	Node *left;
	Node *right;
	Node(DataType inData): data(inData), left(nullptr), right(nullptr) {}
};

template <typename DataType>
class BinarySearchTree
{
public:
	BinarySearchTree(): root(nullptr) {}
	~BinarySearchTree();
	void MakeEmpty(); //清空二叉查找树
	void MakeEmptyNon(); //非递归清空二叉树
	Node<DataType> * Find(DataType inElement); //查找某个元素
	Node<DataType> * FindNon(DataType inElement); //非递归查找
	void DeleteElement(DataType inElement); //删除一个节点
	Node<DataType> * FindMax(); //查找最大元素
	Node<DataType> * FindMaxNon(); //非递归查找最大元素
	Node<DataType> * FindMin(); //查找最小元素
	Node<DataType> * FindMinNon(); //非递归查找最小元素
	Node<DataType> * InsertElementNon(DataType inElement); //非递归插入一个元素
private:
	void MakeEmptyCore(Node<DataType> *inNode);
	Node<DataType> *FindCore(Node<DataType> *inNode, DataType inElement);
	//删除一个节点
	Node<DataType> * DeleteElementCore(Node<DataType> *inNode, DataType inElement);
	Node<DataType> *FindMaxCore(Node<DataType> *inNode);
	Node<DataType> *FindMinCore(Node<DataType> *inNode);
	Node<DataType> *root;
};

如上所示，二叉查找树的基本数据成员为根节点，初始化为空指针，通过插入节点函数建立二叉查找树，以下为各函数实现：

  • 递归清空核心函数
1
2
3
4
5
6
7
8
9
10
template <typename DataType>
void BinarySearchTree<DataType>::MakeEmptyCore(Node<DataType> *inNode)
{
	if (inNode == nullptr) {
		return;
	}
	MakeEmptyCore(inNode->left);
	MakeEmptyCore(inNode->right);
	delete inNode;
}
  • 递归清空入口函数，调用清空核心函数
1
2
3
4
5
template <typename DataType>
void BinarySearchTree<DataType>::MakeEmpty()
{
	MakeEmptyCore(root); root = nullptr;
}
  • 非递归清空函数，采用某种非递归遍历函数思想即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
template <typename DataType>
void BinarySearchTree<DataType>::MakeEmptyNon()
{
	stack<Node<DataType> *> nodeStack;
	Node<DataType> *cycleIter = root;
	while (cycleIter != nullptr || !nodeStack.empty()) {
		while (cycleIter != nullptr) {
			nodeStack.push(cycleIter);
			cycleIter = cycleIter->left;
		}
		
		if (!nodeStack.empty()) {
			Node<DataType> * tmp = nodeStack.top();
			cycleIter = tmp->right;
			delete tmp; nodeStack.pop();
		}
	}
	root = nullptr;
}
  • 递归查找核心函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template <typename DataType>
Node<DataType> *BinarySearchTree<DataType>::FindCore(Node<DataType> *inNode, DataType inElement)
{
	if (inNode == nullptr) {
		return nullptr;
	}
	if (inNode->data == inElement) {
		return inNode;
	}
	else if (inNode->data > inElement){
		return FindCore(inNode->left, inElement);
	}
	else {
		return FindCore(inNode->right, inElement);
	}
	return nullptr;
}
  • 递归查找某个元素
1
2
3
4
5
template <typename DataType>
Node<DataType> * BinarySearchTree<DataType>::Find(DataType inElement)
{
	return FindCore(root, inElement);
}
  • 非递归查找
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template <typename DataType>
Node<DataType> * BinarySearchTree<DataType>::FindNon(DataType inElement)
{
	Node<DataType> *cycleIter = root;
	while (cycleIter != nullptr) {
		if (cycleIter->data == inElement) {
			return cycleIter;
		}
		else if (cycleIter->data > inElement){
			cycleIter = cycleIter->left;
		}
		else {
			cycleIter = cycleIter->right;
		}
	}
	return 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
30
31
template <typename DataType>
Node<DataType> * BinarySearchTree<DataType>::DeleteElementCore(Node<DataType> *inNode, DataType inElement)
{
	if (inNode == nullptr) {
		return nullptr;
	}
	else if (inNode->data > inElement) {
		inNode->left = DeleteElementCore(inNode->left, inElement);
	}
	else if (inNode->data < inElement) {
		inNode->right = DeleteElementCore(inNode->right, inElement);
	}
	else {
		if (inNode->left != nullptr && inNode->right != nullptr) {
			Node<DataType> *tmp = FindMinCore(inNode->right);
			inNode->data = tmp->data;
			inNode->right = DeleteElementCore(inNode->right, inNode->data);
		}
		else {
			Node<DataType> *tmp = inNode;
			if (inNode->left == nullptr) {
				inNode = inNode->right;
			}
			else {
				inNode = inNode->left;
			}
			delete  tmp;
		}
	}
	return inNode;
}

  • 删除一个节点，删除节点需要十分小心，删除需要分为几种情况讨论：

    1. 第一种，叶节点，直接删除即可
    2. 第二种，只有左子节点，直接父节点重新定向到左子节点
    3. 第三种，只有右子节点，也是直接父节点重定向到右子节点
    4. 第四种，有两个子节点，由于该节点值大于左子树而小于右子树，因此可以用左子树的最大值或者右子树的最小值交换，然后删除交换点，改点情况是1~3种情况的一种，即需要删除两次
1
2
3
4
5
template <typename DataType>
void BinarySearchTree<DataType>::DeleteElement(DataType inElement)
{
	root = DeleteElementCore(root, inElement);
}
  • 递归查找最大元素核心函数
1
2
3
4
5
6
7
8
9
10
11
12
13
template <typename DataType>
Node<DataType> * BinarySearchTree<DataType>::FindMaxCore(Node<DataType> *inNode)
{
	if (inNode == nullptr) {
		return nullptr;
	}
	else if (inNode->right == nullptr) {
		return inNode;
	}
	else {
		return FindMaxCore(inNode->right);
	}
}
  • 递归查找最大元素
1
2
3
4
5
6
7
8
template <typename DataType>
Node<DataType> * BinarySearchTree<DataType>::FindMax()
{
	if (root == nullptr) {
		return nullptr;
	}
	return FindMaxCore(root);
}
  • 非递归查找最大元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
template <typename DataType>
Node<DataType> * BinarySearchTree<DataType>::FindMaxNon()
{
	if (root == nullptr) {
		return nullptr;
	}
	Node<DataType> *pre = root;
	Node<DataType> *cycleIter = pre->right;
	while (cycleIter != nullptr) {
		pre = cycleIter;
		cycleIter = pre->right;
	}
	return pre;
}
  • 递归查找最小元素核心函数
1
2
3
4
5
6
7
8
9
10
11
12
13
template <typename DataType>
Node<DataType> * BinarySearchTree<DataType>::FindMinCore(Node<DataType> *inNode)
{
	if (inNode == nullptr) {
		return nullptr;
	}
	else if (inNode->left == nullptr) {
		return inNode;
	}
	else {
		return FindMinCore(inNode->left);
	}
}
  • 递归查找最小元素
1
2
3
4
5
6
7
8
template <typename DataType>
Node<DataType> * BinarySearchTree<DataType>::FindMin()
{
	if (root == nullptr) {
		return nullptr;
	}
	return FindMinCore(root);
}
  • 非递归查找最小元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
template <typename DataType>
Node<DataType> * BinarySearchTree<DataType>::FindMinNon()
{
	if (root == nullptr) {
		return nullptr;
	}
	Node<DataType> *pre = root;
	Node<DataType> *cycleIter = pre->left;
	while (cycleIter != nullptr) {
		pre = cycleIter;
		cycleIter = pre->left;
	}
	return pre;
}
  • 非递归插入一个元素，返回位置
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
template <typename DataType>
Node<DataType> * BinarySearchTree<DataType>::InsertElementNon(DataType inElement)
{
	if (root == nullptr) {
		root = new Node<DataType>(inElement);
		return root;
	}
	Node<DataType> *cycleIter = root;
	while (1) {
		if (cycleIter->data == inElement) {
			return cycleIter;
		}
		else if (cycleIter->data > inElement) {
			if (cycleIter->left == nullptr) {
				break;
			}
			cycleIter = cycleIter->left;
		}
		else {
			if (cycleIter->right == nullptr) {
				break;
			}
			cycleIter = cycleIter->right;
		}
	}
	Node<DataType> *newNode = new Node<DataType>(inElement);
	if (cycleIter->data > inElement) {
		cycleIter->left = newNode;
	}
	else {
		cycleIter->right = newNode;
	}
	return newNode;
}
  • 析构函数
1
2
3
4
5
template <typename DataType>
BinarySearchTree<DataType>::~BinarySearchTree()
{
	MakeEmpty();
}