因为我们之前在学习数据结构的时候使用的是C语言，但是并不是所有的数据结构都适合使用C语言学习，如今我们了解了C++的基础语法，具备了学习这些稍微难一点的数据结构的前提，所以我们再次回顾数据结构，使用C++这一更加先进的武器，来解决更加复杂的问题
二叉搜索树
二叉搜索树概念
二叉搜索树又称二叉排序树，它或者是一棵空树 ，或者是具有以下性质的二叉树 :若它的左子树不为空，则左子树上所有节点的值都小于根节点的值若它的右子树不为空，则右子树上所有节点的值都大于根节点的值它的左右子树也分别为二叉搜索树
int a [] = {5,3,4,1,7,8,2,6,0,9};
?二叉搜索树操作
二叉搜索树的查找
代码实现：
bool Find(const K& key)//传入key值
{
Node* cur = root;//初始化cur指针
while (cur)//循环cur
{
if (cur->_key < key)//当节点上的key较小
{
cur = cur->_right;//向右查找
}
else if (cur->_key > key)//当节点上的值较大
{
cur = cur->_left;//向左查找
}
else
{
return true;//当相等时则找到
}
}
return false;//当循环出树时未找到
}?二叉搜索树的插入
插入的具体过程如下：
a. 树为空，则直接插入
?b. 树不空，按二叉搜索树性质查找插入位置，插入新节点
bool Insert(const K& key)//二叉树的插入
{
if (_root == nullptr)//当根为空，将要插入的节点赋给根
{
_root = new Node(key);
return true;//返回插入成功
}
Node* parent = nullptr;//初始化父节点
Node* cur = _root;//初始化cur结点
while (cur)//开始循环cur，当cur走到末尾为空时停止
{
if (cur->_key < key)//当cur的_key小于要插入的key时
{
parent = cur;//双指针开始向右迭代移动
cur = cur->_right;
}
else if (cur->_key > key)//当cur的_key大于要插入的key
{
parent = cur;//双指针开始向左移动
cur = cur->_left;
}
else
{
return false;//否则返回失败
}
}
//当我们找到要插入的位置，将cur置于此位置时
cur = new Node(key);//将要插入的节点赋给cur
//下面的操作是为了将cur与原来的树连接起来，因为我们cur此时为空，不知道要在parent哪边，所以进行比较
if (parent->_key < key)//如果父节点的_key值小于插入的值
{
parent->_right = cur;//置于父亲的右子树
}
else
{
parent->_left = cur;//置于父亲的左子树
}
return true;//返回找到
}?二叉树的插入，我们先通过一个cur指针与树上的节点比较大小，小的话向左走，大的话向右走，直到走到待插入的位置，而后将结点赋给cur，利用双指针再将其连接到二叉树上即可
二叉搜索树的删除
首先查找元素是否在二叉搜索树中，如果不存在，则返回, 否则要删除的结点可能分下面四种情况：
a. 要删除的结点无孩子结点
这种删除的话就直接用指针找到2并且删除即可?
b. 要删除的结点只有左孩子结点
c. 要删除的结点只有右孩子结点
?
这两种其实可以合在一起，都是仅有一个子结点进行删除，思路就是将待删节点的子节点与待删节点的父节点相连 ，比如删除我们的1和8
d. 要删除的结点有左、右孩子结点
看起来有待删除节点有4中情况，实际情况a可以与情况b或者c合并起来，因此真正的删除过程如下：
情况b：删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点
情况c：删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点
情况d：在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被删除节点中，
再来处理该结点的删除问题
?在我们需要删除一个拥有两个子节点的结点时，我们不能直接进行删除，需要找到一个叶子节点去替换它，然后删除，所以我们需要找到左子树的最大节点或者右子树的最右结点，只有这两个是可以替换它的
bool Erase(const K& key)//二叉树的删除
{
Node* parent = nullptr;//初始化父节点
Node* cur = _root;//初始化cur
while (cur)//循环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)//防止删除的为最上面无法找到parent
{
_root = cur->_left;
}
else
{
if (parent->_right == cur)//如果cur在parent的右子树上也就是\结构
parent->_right = cur->_right;//直接相连cur的右子树与其父节点
else//< 结构
parent->_left = cur->_right;
}
delete cur;//释放删除cur
}
// 2、右为空
else if (cur->_right == nullptr)
{
if (cur == _root)//防止删除的为最上面无法找到parent
{
_root = cur->_left;
}
else
{
if (parent->_left == cur)// /结构
parent->_left = cur->_left;
else// >结构
parent->_right = cur->_left;
}
delete cur;
}
// 3、左右都不为空
else
{
Node* rightMinParent = cur;//初始化遍历节点的父节点
Node* rightMin = cur->_right;//初始化遍历结点，向右走
while (rightMin->_left)//当节点的左子树不为空
{
rightMinParent = rightMin;//向左走
rightMin = rightMin->_left;
}
cur->_key = rightMin->_key;//将最小的结点赋给目标节点
//转换成删除rightMin（rightMin是左为空，父亲指向它的右）
if (rightMin == rightMinParent->_left)
rightMinParent->_left = rightMin->_right;//将最小节点的右子树赋给父节点
else
rightMinParent->_right = rightMin->_right;
delete rightMin;//释放已经换过的最小节点
}
return true;//返回删除成功
}
}
return false;//没找到节点则返回失败
}对于删除的关键就是要掌握删除时的3种情况，从而分别分析删除
二叉搜索树的基本实现
#pragma once
template<class K>
struct BSTreeNode // 二叉搜索树
{
BSTreeNode<K>* _left;
BSTreeNode<K>* _right;
K _key;
BSTreeNode(const K& key)//初始化列表初始化
:_left(nullptr)
, _right(nullptr)
, _key(key)
{}
};
template<class K>
class BSTree // Binary Search Tree
{
typedef BSTreeNode<K> Node;
public:
bool Insert(const K& key)//二叉树的插入
{
if (_root == nullptr)//当根为空，将要插入的节点赋给根
{
_root = new Node(key);
return true;//返回插入成功
}
Node* parent = nullptr;//初始化父节点
Node* cur = _root;//初始化cur结点
while (cur)//开始循环cur，当cur走到末尾为空时停止
{
if (cur->_key < key)//当cur的_key小于要插入的key时
{
parent = cur;//双指针开始向右迭代移动
cur = cur->_right;
}
else if (cur->_key > key)//当cur的_key大于要插入的key
{
parent = cur;//双指针开始向左移动
cur = cur->_left;
}
else
{
return false;//否则返回失败
}
}
//当我们找到要插入的位置，将cur置于此位置时
cur = new Node(key);//将要插入的节点赋给cur
//下面的操作是为了将cur与原来的树连接起来，因为我们cur此时为空，不知道要在parent哪边，所以进行比较
if (parent->_key < key)//如果父节点的_key值小于插入的值
{
parent->_right = cur;//置于父亲的右子树
}
else
{
parent->_left = cur;//置于父亲的左子树
}
return true;//返回找到
}
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;
}
bool Erase(const K& key)//二叉树的删除
{
Node* parent = nullptr;//初始化父节点
Node* cur = _root;//初始化cur
while (cur)//循环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)//防止删除的为最上面无法找到parent
{
_root = cur->_left;
}
else
{
if (parent->_right == cur)//如果cur在parent的右子树上也就是\结构
parent->_right = cur->_right;//直接相连cur的右子树与其父节点
else//< 结构
parent->_left = cur->_right;
}
delete cur;//释放删除cur
}
// 2、右为空
else if (cur->_right == nullptr)
{
if (cur == _root)//防止删除的为最上面无法找到parent
{
_root = cur->_left;
}
else
{
if (parent->_left == cur)// /结构
parent->_left = cur->_left;
else// >结构
parent->_right = cur->_left;
}
delete cur;
}
// 3、左右都不为空
else
{
Node* rightMinParent = cur;//初始化遍历节点的父节点
Node* rightMin = cur->_right;//初始化遍历结点，向右走
while (rightMin->_left)//当节点的左子树不为空
{
rightMinParent = rightMin;//向左走
rightMin = rightMin->_left;
}
cur->_key = rightMin->_key;//将最小的结点赋给目标节点
//转换成删除rightMin（rightMin是左为空，父亲指向它的右）
if (rightMin == rightMinParent->_left)
rightMinParent->_left = rightMin->_right;//将最小节点的右子树赋给父节点
else
rightMinParent->_right = rightMin->_right;
delete rightMin;//释放已经换过的最小节点
}
return true;//返回删除成功
}
}
return false;//没找到节点则返回失败
}
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}二叉搜索树的应用
1. K 模型： K 模型即只有 key 作为关键码，结构中只需要存储 Key 即可，关键码即为需要搜索到的值 。比如： 给一个单词 word ，判断该单词是否拼写正确 ，具体方式如下：以单词集合中的每个单词作为 key ，构建一棵二叉搜索树在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。
其实我们的k模型就是我们一般的二叉树模型，去查找k是否在二叉树中
2. KV 模型：每一个关键码 key ，都有与之对应的值 Value ，即 <Key, Value> 的键值对 。该种方式在现实生活中非常常见：比如英汉词典就是英文与中文的对应关系 ，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文<word, chinese> 就构成一种键值对；再比如 统计单词次数 ，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是 <word, count> 就构成一种键值对 。比如：实现一个简单的英汉词典 dict ，可以通过英文找到与其对应的中文，具体实现方式如： <单词，中文含义 > 为键值对构造二叉搜索树，注意：二叉搜索树需要比较，键值对比较时只比较 Key查询英文单词时，只需给出英文单词，就可快速找到与其对应的 key
#pragma once
template<class K,class V>
struct BSTreeNode // 二叉搜索树
{
BSTreeNode<K>* _left;
BSTreeNode<K>* _right;
K _key;
V _value;
BSTreeNode(const K& key)//初始化列表初始化
:_left(nullptr)
, _right(nullptr)
, _key(key)
, _value(value)
{}
};
template<class K,class V>
class BSTree // Binary Search Tree
{
typedef BSTreeNode<K, V> Node;
public:
bool Insert(const K& key,const V& value)//二叉树的插入
{
if (_root == nullptr)//当根为空，将要插入的节点赋给根
{
_root = new Node(key);
return true;//返回插入成功
}
Node* parent = nullptr;//初始化父节点
Node* cur = _root;//初始化cur结点
while (cur)//开始循环cur，当cur走到末尾为空时停止
{
if (cur->_key < key)//当cur的_key小于要插入的key时
{
parent = cur;//双指针开始向右迭代移动
cur = cur->_right;
}
else if (cur->_key > key)//当cur的_key大于要插入的key
{
parent = cur;//双指针开始向左移动
cur = cur->_left;
}
else
{
return false;//否则返回失败
}
}
//当我们找到要插入的位置，将cur置于此位置时
cur = new Node(key, value);//将要插入的节点赋给cur
//下面的操作是为了将cur与原来的树连接起来，因为我们cur此时为空，不知道要在parent哪边，所以进行比较
if (parent->_key < key)//如果父节点的_key值小于插入的值
{
parent->_right = cur;//置于父亲的右子树
}
else
{
parent->_left = cur;//置于父亲的左子树
}
return true;//返回找到
}
Node* 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 cur;
}
}
return nullptr;
}
bool Erase(const K& key)//二叉树的删除
{
Node* parent = nullptr;//初始化父节点
Node* cur = _root;//初始化cur
while (cur)//循环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)//防止删除的为最上面无法找到parent
{
_root = cur->_left;
}
else
{
if (parent->_right == cur)//如果cur在parent的右子树上也就是\结构
parent->_right = cur->_right;//直接相连cur的右子树与其父节点
else//< 结构
parent->_left = cur->_right;
}
delete cur;//释放删除cur
}
// 2、右为空
else if (cur->_right == nullptr)
{
if (cur == _root)//防止删除的为最上面无法找到parent
{
_root = cur->_left;
}
else
{
if (parent->_left == cur)// /结构
parent->_left = cur->_left;
else// >结构
parent->_right = cur->_left;
}
delete cur;
}
// 3、左右都不为空
else
{
Node* rightMinParent = cur;//初始化遍历节点的父节点
Node* rightMin = cur->_right;//初始化遍历结点，向右走
while (rightMin->_left)//当节点的左子树不为空
{
rightMinParent = rightMin;//向左走
rightMin = rightMin->_left;
}
cur->_key = rightMin->_key;//将最小的结点赋给目标节点
//转换成删除rightMin（rightMin是左为空，父亲指向它的右）
if (rightMin == rightMinParent->_left)
rightMinParent->_left = rightMin->_right;//将最小节点的右子树赋给父节点
else
rightMinParent->_right = rightMin->_right;
delete rightMin;//释放已经换过的最小节点
}
return true;//返回删除成功
}
}
return false;//没找到节点则返回失败
}
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_key << " " << root->_value << " ";
_InOrder(root->_right);
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
private:
Node* _root = nullptr;
};
void TestBSTree1()//查单词
{
BSTree<string, string>dict;
dict.Insert("sort", "排序");
dict.Insert("string", "字符串");
dict.Insert("tree", "树");
dict.Insert("insert", "插入");
string str;
while (cin >> str)
{
BSTreeNode<string, string>*ret = dict.Find(str);
if (ret)
{
cout << ret->_value << endl;
}
else
{
cout << "无此单词" << endl;
}
}
}
void TestBSTree2()//数数
{
string strs[] = { "苹果","苹果","香蕉","香蕉","苹果","香蕉","苹果""橘子","苹果","橘子","苹果","苹果","香蕉" }
BSTree<string, int>countTree;
for (auto str : strArr)
{
BTSreeNode<string, int>* ret = countTree.Find(str);
if (ret == nullptr)
{
countTree.Insert(str, 1);
}
else
{
ret->_value++;
}
}
}上面两个例子就是我们的K -Valu模型的例子，总的来说还是很常用的
二叉搜索树的性能分析
插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。对有 n 个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：
如上图我们可以知道，二叉搜索树搜索的效率是根据树的结构而决定的，如果树是顺序插入时，效率就不那么高了
最优情况下，二叉搜索树为完全二叉树，其平均比较次数为：logN
最差情况下，二叉搜索树退化为单支树，其平均比较次数为：N/2
?二叉树的非递归遍历
我们在之前的学习中，对于二叉树的许多操作都是基于递归而实现的，但事实上递归的效率却没有想得那么高，所以我们还需要来了解二叉树的非递归遍历
前序遍历
我们先来完成一下我们熟知的递归前序遍历
void _preorderTraversal(TreeNode* root; vector<int>& v)//子函数
{
if (root == NULL)
return;
v.push_back(root->val);
_preorderTraversal(root->left, v);
_preorderTraversal(root->right, v);
}
vector<int> preorderTraversal(TreeNode* root)
{
vector<int>ret;
_preorderTraversal(root, ret);
return ret;
}迭代
我们的二叉树遍历方式其实思想上还是去利用递归的方式，只是递归的步骤我们进行了模拟，我们利用栈去模拟递归地访问顺序
?我们这样一棵树的前序遍历顺序为：1 2 4 5 3 6 7 顺序为根 左 右
?这其实就是我们的访问路径，我们可以看到，我们在在访问时，对于同一个节点可能有多次的经过，但是只会有一次的访问，所以我们需要利用栈这个数据结构来进行操作
1.我们先访问，后入栈
我们的cur初始在根节点，在首次接触到一个新节点时进行访问，并且入栈，我们先按照前序遍历的方式，根-左-右，先对这个树根访问，而后向左移动，有节点就入栈，不断向左移动，直到访问到NULL，此时我们的cur就到了栈顶结点的左子树上，而且此时我们就剩下栈中结点的右子树未访问，剩下的我们只需要取结点，访问右子树就可以了
2.访问栈顶元素的右子树，同理重复上述步骤，将右子树再分为左路结点与右子树来访问，那么此时是如何操作的呢？首先，我们取出栈顶元素，将cur指向栈顶结点的右子树，因为这里4的右子树为空，所以默认为访问过，所以我们再次重复，取出2，cur指向其右子树
?3.此时又被分为了左路节点与右树，所以我们将5入栈，向左访问，未NULL,向右访问，也为NULL，发现不管是左树还是右数都没有节点需要入栈了，重复了访问4的过程，所以我们将5出栈，cur指向栈顶的右子树
?4.此时我们的左树都访问完毕了，将cur指向了栈顶的右子树，栈顶元素出栈，再次重复上述过程，访问+入栈，并向左移动，所以我们将3，6依次入栈，并且将cur指向了6的左子树
?再次重复之前的步骤，6左子树为空，认为访问过，转到右子树，也为空，认为访问过，出栈，cur指向栈顶元素的右子树，3出栈，右子树不为空，7入栈，再次向左向右访问，为空认为访问过
此时7的左右树访问完成，出栈，栈空，完成遍历
?注意：是当我们将cur指向栈顶的右子树时栈顶元素出栈
代码实现：
vector<int>preorderTraversal(TreeNode* root)
{
vector<int> ret;//定义vector接收
stack<TreeNode*> st;//定义栈
TreeNode* cur = root;//初始化cur指针
while (cur || !st.empty())//当cur不为空且栈中也不为空时
//这个大循环是当有节点未被访问则会先去探索左结点，再去探索右树
{
while (cur)//当cur不为空
//这个循环的作用是，我们一路向左走，碰到节点就访问+入栈，直到为空
{
ret.push_back(cur->val);//cur指向的值入vector(访问)
st.push(cur);//入栈
cur = cur->left;//访问左子树，向左走
}
//取栈中左路节点的右子树
TreeNode* top = st.top();//取栈顶的元素赋给top指针
st.pop();//出栈
cur = top->right;//cur指向其右子树
}
return ret;
}其实我们看到，代码并不是很复杂，但是我们的分析过程却是比较详细的，最核心的就是将二叉树分为两部分，左路节点与右子树，访问右子树时将右子树再看作左路节点+右子树即可
中序遍历
我们的中序遍历其实也与前序遍历类似，用的是同一种方法，都是用栈去模拟递归过程，那么我们再来看看中序遍历是如何来实现的吧，在这里我们就不用递归的方式来进行演示了
我们依旧在用画图的方式来进行分析
初始时后依旧是cur在根节点
?1.我们进行遍历，同前序遍历一样，先将cur向左走，遇到节点，入栈，直到走到4的左子节点，为空
?2当我们访问完4的左子节点时，开始访问4，出栈，访问4的右树，为空，访问完成，此时2的左子节点访问完毕，访问2，出栈，cur指向2的右子树，入栈，并重复访问4的过程
3.我们访问完成5的左子节点之后，出栈，访问5，指针指向5的右子节点，右子节点为空，此时1的左子树的所有节点也完成了访问，所以，访问1，出栈，并将cur指向栈顶元素(1)的右子树上
?4.此时我们就可以又像访问之前左子树的方式去访问右子树，向左走，入栈，再向左走，为空访问完成，出栈，向右走，为空，访问完成，此时3的左子树访问完毕，访问3，出栈，cur指向7，入栈，再向左走，为空，访问完成，出栈，指向7的右子节点，为空，完成遍历
?下面我们对其进行代码实现
vector<int>inorderTraversal(TreeNode* root)
{
vector<int>ret;//定义vector接收
stack<TreeNode*>st;//定义栈
TreeNode* cur = root;//初始化cur指针
while (cur || !st.empty())//当cur不为空且栈不为空时
{
while (cur)//循环cur
{
st.push(cur);//入栈
cur = cur->left;//向左走
}
TreeNode* top = st.top();//将栈顶元素赋给top指针
st.pop();//出栈
ret.push_back(top->val);//访问栈顶元素
cur = top->right;//cur指向右子树
}
return ret;
}中序遍历与前序遍历的关键其实是访问顺序的差别，中序遍历是在访问完左子树之后访问根，前序遍历是直接访问根
后序遍历
后序遍历在我们三种遍历方式中是最复杂的一种，原因是其出栈之前需要访问完其所有的子节点，而又因为栈中只能出栈顶的缘故，所以我们对后序遍历进行了额外处理，让我们一起来了解下后序遍历吧
初始化
?1.同我们的前序与中序一样，先向左走，遇到节点入栈
?2.此时我们访问4的左子节点，访问完成，访问4的右子节点，为空
3.出栈，cur指向2的右子树，入栈，同样像刚才遍历访问一样访问5
?4.访问完成5了之后，出栈，并将5赋给lastNode，因为2的右子树为lastNode，说明2的右子树已经访问过了，?然后开始访问2
?5.访问完2后，出栈，此时1的左子树访问完毕，cur指向1的右子树，右子树3入栈?
6.此时像之前访问左子树一样访问右子树，先左移，入栈，访问左子树，因为右为空，访问右子树，而后访问6，出栈，置为lastNode，cur置为7，开始访问7的左子树，右为空，访问右子树，此时访问7，并将7置为lastNode，因为3的右子树为lastNode，代表其右子树已经访问过，此时再访问3，出栈，并将其置为lastNode，这时1的右子树也为lastNode，访问1，出栈，完成遍历
vector<int>postTraversal(TreeNode* root)
{
vector<int>ret;//定义vector接收
stack<TreeNode*>st;//定义栈
TreeNode* lastNode = NULL;//初始化上一个访问的节点
TreeNode* cur = root;//初始化cur指针
while (cur || !st.empty())//当cur不为空且栈不为空时
{
while (cur)//循环cur
{
st.push(cur);//入栈
cur = cur->left;//向左走
}
TreeNode* top = st.top();//将栈顶元素赋给top指针
if (top->right == NULL||lastNode==top->right)//当top的右子节点为空或者右子节点上一个访问过了
{
ret.push_back(top->val);//访问top
lastNode = top;//将top赋给lastNode
st.pop();//出栈
}
else
{
cur = top->right;//向右走
}
}
return ret;
}后序遍历的关键其实就是去判断其右子树是否访问过，访问过了再进行访问，需要加个限定条件