目录

1.二叉搜索树

1.1二叉搜索树概念

1.2二叉搜索树模板

1.2.1二叉树的结点

1.2.2二叉树类模板

1.3二叉搜索树操作的实现

1.3.1二叉搜索树的插入

1.3.2中序遍历 

1.3.3 二叉搜索树的查找

1.3.4二叉搜索树的删除

1.4二叉搜索树操作的递归实现 

1.4.1递归实现插入操作

1.4.2递归实现查找 

1.4.3递归实现删除操作 

2.二叉搜索树应用分析

2.1 K模型

2.2 KV模型

3.二叉搜索树性能分析

3.1最优情况

3.2最差情况

1.二叉搜索树

1.1二叉搜索树概念

二叉搜索树：它或者是一棵空树，或者是具有下列性质的二叉树。

• 若它的左子树不空，则左子树上所有结点的值均小于它根结点的值；
• 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

二叉搜索树也称二叉查找数(可以用于查找)或者二叉排序树(中序遍历出的结果是有序的)。

二叉树的中序遍历: 首先遍历左子树，然后访问根结点，最后遍历右子树。

1.2二叉搜索树模板

1.2.1二叉树的结点

template 
struct BTNode
{BTNode* left;//指向左子结点BTNode* right;//指向右子结点K _key;
};

为什么使用struct，而不使用class？

class定义的类中的成员默认是私有的，在类外是不能访问的；

struct定义的类中的成员默认是共有的，在类外可以访问；访问权限问题。

1.2.2二叉树类模板

template 
class BSTree
{typedef BSNode Node;//对类模板结点进行重命名
public://放对外调用接口-对二叉树进行操作
private:Node* _root = nullptr;//Node指针，缺省值为nullptr
};

1.3二叉搜索树操作的实现

1.3.1二叉搜索树的插入

先来看一下二叉搜索树的声明：

bool Insert(const K& key);

现在来解释一下为什么插入返回的是一个布尔类型：二叉搜索树中的数据是不能重复的，相同的数据无法插入，返回false；

不相同的数据插入成功，返回true。 

画图看一下插入过程：

二叉搜索树插入的具体实现：

bool Insert(const K& key)
{if (_root == nullptr)//二叉搜索树为空{_root = new Node(key);return true;}//不为空Node* cur = _root;Node* parent = nullptr;while (cur){if (key > cur->_key){parent = cur;cur = cur->right;}else if (key < cur->_key){parent = cur;cur = cur->left;}else//插入的值和结点的值相同return false;}cur = new Node(key);//找到插入的位置和插入位置的parentif (key > parent->_key)parent->right = cur;if (key < parent->_key)parent->left = cur;return true;
}

注意：在使用new来为Node对象开辟空间时，会调用Node的构造函数，所以在BTNode中要显示写出一个有参构造。

BTNode(const K& key):left(nullptr), right(nullptr), _key(key)
{}

1.3.2中序遍历 

使用中序遍历(Inorder)访问二叉搜索树中的元素：

void _Inorder(Node* root)
{if (root == nullptr)return;_Inorder(root->left);cout << root->_key << " ";_Inorder(root->right);
}

这样写会有一个问题：成员函数_Inorder的参数root在类外如何去传？有两种解决方案。

1. 对外公开一个接口GetRoot()
2. 在类内完成调用 

如何在类内完成调用？在定义一个公开的Inorder去调用_Inorder。

public:void Inorder(){_Inorder(_root);}
private:void _Inorder(Node* root){if (root == nullptr)return;_Inorder(root->left);cout << root->_key << " ";_Inorder(root->right);}

结合插入和中序遍历的接口，下面进行一下测试：

void TestBSTree1()
{int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13, 3, 1 };BSTree t;for (auto& e : a){t.Insert(e);}t.Inorder();
}

 在主函数中调用TestBSTree1()，看能不能得到我们想要的结果：

 

 使用中序遍历打印出的结果是升序的，而且重复的数据也是无法插入的，直接反映了二叉搜索树的两个特征：升序+去重。

1.3.3 二叉搜索树的查找

查找和插入的遍历是相似的，不过当遍历的指针为空时，代表没有找到，找到的话会直接返回。

bool Find(const K& key)
{Node* cur = _root;while (cur){if (key > cur->_key){cur = cur->right;}else if (key < cur->_key){cur = cur->left;}else//找到了return true;}return false;
}

void TestBSTree1()
{int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13, 3, 1 };BSTree t;for (auto& e : a){t.Insert(e);}t.Inorder();cout << t.Find(10) << endl;cout << t.Find(100) << endl;
}

 

直接使用cout进行打印时：结果为true  ->  1；结果为false ->  0。

1.3.4二叉搜索树的删除

二叉搜索树的删除有点复杂，需要考虑多种场景和解决办法。

二叉搜索树删除的返回值还是一个布尔类型：删除成功返回true，删除的值不存在返回false。

二叉树的删除首先需要确定这个值是否存在，如果存在再进行删除，如果不存在直接返回fasle。

bool Erase(const K& key)
{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;//没找到，返回false
}

找到之后进行删除又可以分为三种情况：

1.被删除结点有右结点，没有左结点

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.被删除结点有左结点，没有右结点(没有子结点的情况走1.2的其中一个)

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.被删除结点既有左结点，又有右结点

替换法：找到左子树的最大值或者右子树的最小值和删除的值进行交换，然后再把要删除值的结点删除。

需要注意的是：删除的的max或者min结点可能还有子结点，还要进一步进行判断。

Node* minParent = cur;
Node* min = cur->_right;
while (min->_left)
{minParent = min;min = min->_left;
}swap(cur->_key, min->_key);
if (minParent->_left == min)
minParent->_left = min->_right;
else
minParent->_right = min->_right;delete min;
min = nullptr;
return true;

 完整代码实现：

bool Erase(const K& key)
{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{if (cur->_left == nullptr){if (cur == _root)_root = cur->_right;else{if (cur == parent->_left)parent->_left = cur->_right;elseparent->_right = cur->_right;}delete cur;cur = nullptr;}else if (cur->_right == nullptr){if (_root == cur)_root = cur->_left;else{if (cur == parent->_left)parent->_left = cur->_left;elseparent->_right = cur->_left;}delete cur;cur = nullptr;}else{// 替换法删除 -- Node* minParent = cur;Node* min = cur->_right;while (min->_left){minParent = min;min = min->_left;}swap(cur->_key, min->_key);if (minParent->_left == min)minParent->_left = min->_right;elseminParent->_right = min->_right;delete min;min = nullptr;return true;}}return true;}return false;
}

测试一下是否正确：

void TestBSTree1()
{int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13, 3, 1 };BSTree t;for (auto& e : a){t.Insert(e);}t.Inorder();t.Erase(3);t.Inorder();t.Erase(8);t.Inorder();for (auto& e : a){t.Erase(e);}t.Inorder();
}

 

 通过运行结果可以看到：一个一个删除数据没有问题，而且全部删除也是没有问题的。

1.4二叉搜索树操作的递归实现 

递归的时候同样需要传入根节点，而且根节点并不能给缺省值，所以需要在类内实现一个公有的接口来调用类内的Node* _root。

1.4.1递归实现插入操作

public:bool FindR(const K& key){return _FindR(_root, key);}
private:bool _InsertR(Node*& root, const K& key){if (root == nullptr){//插入root = new Node(key);return true;}if (key > root->_key){return _InsertR(root->right, key);}else if (key < root->_key){return _InsertR(root->left, key);}elsereturn false;}

1.4.2递归实现查找 

public:bool FindR(const K& key){return _FindR(_root, key);}
private:bool _FindR(Node* root, const K& key){if (root == nullptr)return false;if (key > root->_key)return _FindR(root->right, key);else if (key < root->_key)return _FindR(root->left, key);elsereturn true;}

1.4.3递归实现删除操作 

public:bool EraseR(const K& key){return _EraseR(_root, key);}
private:bool _EraseR(Node*& root, const K& key){if (root == nullptr)return false;if (key > root->_key)return _EraseR(root->right, key);else if (root->_key > key)return _EraseR(root->left, key);else{//找到之后的删除操作Node* del = root;if (root->left == nullptr){root = root->right;}else if (root->right == nullptr){root = root->left;}else{// 找右树的最左节点替换删除Node* min = root->right;while (min->left){min = min->left;}swap(root->_key, min->_key);return _EraseR(root->right, key);}delete del;return true;}}

2.二叉搜索树应用分析

2.1 K模型

K模型：K模型即只有key作为关键码，结构中只需存储key即可，关键码即为需要搜索到的值。

举个栗子：给一个单词word，判断该单词是否拼写正确，具体的操作方式如下：

1. 以词库中所有单词集合中的每个单词作为key，构建一颗二叉搜索树
2. 在二叉搜索树中检索该单词是否存在，存在就是拼写正确，不存在就是拼写错误

2.2 KV模型

KV模型：每一个关键码key，都有与之对应的值value，也就是的键值对。

举栗：英汉词典(英文和中文的对应关系)

• 通过英文可以快速的找到对应的中文 
• 统计单词出现的次数，通过键值对的对应关系来找到count

3.二叉搜索树性能分析

插入和删除操作都必须先查找，而查找在不同的情况下效率是不同的，最多查找高度次。(不同情况下高度不同)

3.1最优情况

二叉搜索树为完全二叉树(或者接近完全二叉树)，次数为：longN。

3.2最差情况

二叉搜索树为单支树，次数为：N。

二叉搜索树的内容到这里就完结了，最后在这里祝大家10 24程序节快乐，希望我们的程序写的越来越好，编程能力越来越强。