1.二叉搜索树
1.1概念
二叉搜索树又称 二叉排序树，它或是 一棵空树，又或是具有 以下性质的二叉树:若它的左子树不为空，则左子树上所有节点的值都小于根节点的值 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值 它的左右子树也分别为二叉搜索树
可以观察到，对这棵树进行
中序遍历的话，可以得到一串升序的数据
如果左子树放大的数据，右子树放小的数据，那么中序遍历就是降序了
1.2操作
1.2.1二叉搜索树的查找
1.2.2二叉搜索树的插入
一、树为空树，则直接新增节点，赋值给root指针 二、树不为空树，按二叉搜索树的性质查找插入位置，插入新节点1.2.3二叉搜索树的删除
首先要查找所删除的元素 是否在二叉搜索树中，如果不存在，则返回 如果存在，则要删除的结点可以分为 下面四种情况：一、要删除的结点无孩子结点综上，待删除结点有4种情况，但实际上，情况一可以与情况二或者三合并起来，因为叶子节点可以当作 左为空，也可以当作 右为空，所以真正的删除过程如下：二、要删除的结点只有左孩子结点
三、要删除的结点只有右孩子结点
四、要删除的结点有左、右孩子结点 这种情况是最难处理的，因为它不能直接托孤了，待删除的结点有两个孩子结点 此时最好使用 替换法，找一个可以轻松脱身的结点，与待删除结点交换，然后再删除节点
情况二：直接删除该结点，使被删除节点的 双亲结点指向被删除结点的左孩子结点 情况三：直接删除该结点，使被删除节点的 双亲结点指向被删除结点的右孩子结点 情况四：在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被删除结点中，再来处理该结点的删除问题，使用替换法删除结点
1.3实现
1.3.1树的结点
template<class K>
struct BSTreeNode
{
BSTreeNode<K>* _left;
BSTreeNode<K>* _right;
K _key;
BSTreeNode(const K& key)
:_left(nullptr)
,_right(nullptr)
,_key(key)
{}
};这里一般不使用T，而使用K，因为这个数据结构的值要参与数据比较，一般把这个值叫做关键字 key
1.3.2插入
//BinarySearchTree.h
#pragma once
#include<iostream>
using namespace std;
//这里不写命名空间是因为，所写的东西与库中的命名不冲突
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
{
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是一个局部变量
//cur走到空的位置就可以完成插入了
while (cur)
{
parent = cur;
if (key > cur->_key)//插入的值比cur指向的_key大
{
cur = cur->_right;
}
else if (key < cur->_key)
{
cur = cur->_left;
}
//默认情况下，搜索二叉数是不允许有重复值的
else
{
return false;
//所以如果插入的值在树中已经存在了
//就return false
}
}
cur = new Node(key);
//判断cur是连接 在parent的左边还是右边
if (key > parent->_key)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
return true;
}
private:
Node* _root = nullptr;
};1.3.2.1测试
//Test.cpp
#include"BinarySearchTree.h"
int main()
{
int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
BSTree<int> bt;
for (auto e : a)
{
bt.Insert(e);
}
return 0;
}1.3.3中序遍历
template<class K>
class BSTree
{
typedef BSTreeNode<K> Node;
public:
void InOrder(Node* root)//中序遍历
{
if (root == nullptr)
return;
InOrder(root->_left);
cout << root->_key << " ";
InOrder(root->_right);
}
private:
Node* _root = nullptr;
};1.3.3.1测试时的问题
int main()
{
int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
BSTree<int> bt;
for (auto e : a)
{
bt.Insert(e);
}
bt.InOrder();
//调用中序遍历要传递根结点，但这里不容易拿到
//二叉树的递归需要有参数
return 0;
}1.3.3.2解决方式一
写一个GetNode函数，把_root返回
1.3.3.3解决方式二
改写中序遍历的实现方式
C++中通常不使用方式一
template<class K>
class BSTree
{
typedef BSTreeNode<K> Node;
public:
void _InOrder(Node* root)//中序遍历
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}
//类外面拿不到根结点，但是类里面可以使用
void InOrder()
{
_InOrder(_root);
}
private:
Node* _root = nullptr;
};
//测试成功
int main()
{
int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
BSTree<int> bt;
for (auto e : a)
{
bt.Insert(e);
}
bt.InOrder();
return 0;
}C++中的递归通常都是这样去写的
1.3.4查找
template<class K>
class BSTree
{
typedef BSTreeNode<K> Node;
public:
bool Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (key > _root->_key)
{
cur = cur->_right;
}
else if (key < _root->_key)
{
cur = cur->_left;
}
else
{
return true;
}
}
return false;
}
private:
Node* _root = nullptr;
};
1.3.5删除
template<class K>
class BSTree
{
typedef BSTreeNode<K> Node;
public:
bool Erase(const K& key)
{
//首先找到待删除的结点，同时要找到它的父亲
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{//查找的过程
if (key > cur->_key)
{
parent = cur;
cur = cur->_right;
}
else if (key < cur->_key)
{
parent = cur;
cur = cur->_left;
}
//找到了待删除结点:cur
else
{
//开始删除
//1.情况三：左为空
if (cur->_left == nullptr)
{//先判断待删除节点是不是根节点
if (cur == _root)
{
_root = cur->_right;
}
else
{//判断父亲的哪个指针指向cur
if (parent->_left == cur)
{
parent->_left = cur->_right;
}
else
{
parent->_right = cur->_right;
}
}
}
//2.情况二：右为空
else if (cur->_right == nullptr)
{
if (cur == _root)
{
_root = cur->_left;
}
else
{//判断父亲的哪个指针指向cur
if (parent->_left == cur)
{
parent->_left = cur->_left;
}
else
{
parent->_right = cur->_left;
}
}
}
//3.情况四：左、右都不为空
else
{//默认找右树的最小节点来替换
//Node* parent = nullptr;
Node* parent = cur;
Node* subLeft = cur->_right;
while (subLeft->_left)
{
parent = subLeft;
subLeft = subLeft->_left;
}
swap(cur->_key, subLeft->_key);
//替换完之后，就要删除节点了
//注意：这里不能去复用函数来删除最左节点
//因为此时它已经不是二叉搜索树了，很可能根本就找不到最左节点
if (parent->_left == subLeft)
{
parent->_left = subLeft->_right;
}
else
{
parent->_right = subLeft->_right;
}
}
return true;
}//找到了待删除结点:cur
}//while结尾
//没有找到
return false;
}
private:
Node* _root = nullptr;
};
int main()
{
int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
BSTree<int> bt;
for (auto e : a)
{
bt.Insert(e);
}
bt.InOrder();
bt.Erase(14);
bt.InOrder();
bt.Erase(3);
bt.InOrder();
bt.Erase(8);
bt.InOrder();
for (auto e : a)
{
bt.Erase(e);
bt.InOrder();
}
return 0;
}1.3.5.1注意事项
一、
二、
我们已经实现了二叉搜索树的增、删、查，那么二叉搜索树的修改，也需要实现吗？
二叉搜索树是不能随意修改的，因为修改之后，就很难保证这棵树依旧是二叉搜索树了。
1.4递归实现二叉搜索树
二叉搜索树本身是一个递归结构，但当前的实现，我们使用的是循环。
实际上还可以写一个递归版本的二叉搜索树
1.4.1查找
template<class K>
class BSTree
{
typedef BSTreeNode<K> Node;
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);
}
else
{
return true;
}
}
private:
Node* _root = nullptr;
};
1.4.2插入
1.4.2.1方式一
template<class K>
class BSTree
{
typedef BSTreeNode<K> Node;
public:
bool InsertR(const K& key)
{
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
return _InsertR(_root, key,nullptr);
}
private:
bool _InsertR(Node* root,const K& key,Node* parent)
{
if (root == nullptr)
{
root = new Node(key);
if (key > parent->_key)
{
parent->_right = root;
}
else
{
parent->_left = root;
}
return true;
}
if (key > root->_key)
{
return _InsertR(root->_right, key,root);
}
else if (key < root->_key)
{
return _InsertR(root->_left, key,root);
}
else
{
return false;
}
}
private:
Node* _root = nullptr;
};
1.4.2.1方式二：巧妙地使用引用
template<class K>
class BSTree
{
typedef BSTreeNode<K> Node;
public:
bool InsertR(const K& key)
{
return _InsertR(_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);
}
else
{
return false;
}
}
private:
Node* _root = nullptr;
};
既然递归实现时，可以巧妙地使用引用来达成目的。
那么之前的循环实现的插入函数是不是也可以使用引用呢？
答案是不可以的。C++的引用不能改变指向，
比如起初是A的引用，那么之后就不能再变成B的引用、C的引用了，
int a = 0;
int& b = a;//给a取别名为b
int& c = a;
int& d = b;//给别名取别名
int x = 1;
b = x;//这里是赋值
//b已经是a的引用了，就不能再更改了递归时可以更改是因为，虽然都叫做root，但是每个栈帧中都是一个新的引用，不同作用域可以定义同名变量，每次都定义了一个新的引用，只是说前几次的引用没有起到作用，最后一次的引用才起到了作用。
1.4.3删除
template<class K>
class BSTree
{
typedef BSTreeNode<K> Node;
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 (key < root->_key)
{
return _EraseR(root->_left, key);
}
else
{//找到了节点，开始删除
if (root->_left == nullptr)
{
//使用引用传递参数，写起来就会很舒服
//不必再去判断是父亲的左还是右
Node* del = root;
root = root->_right;
delete del;
return true;
}
else if (root->_right == nullptr)
{
Node* del = root;
root = root->_left;
delete del;
return true;
}
else//左右都不为空
{
//这里还要去找替代节点
Node* subLeft = root->_right;
while (subLeft->_left)
{
subLeft = subLeft->_left;
}
swap(root->_key, subLeft->_key);
//转换成在子树中，去递归删除
//在子树中，删除的节点一定 不是 左右都不为空的节点
return _EraseR(root->_right,key);
}
}
}
private:
Node* _root = nullptr;
};
画出递归展开图，有助于理解
1.5完善搜索树的实现
1.5.1析构函数
template<class K>
class BSTree
{
typedef BSTreeNode<K> Node;
public:
//不可能说对析构函数递归
//因为递归一定有一个特点：递归一定要控制参数
//由参数的变化来控制这棵树
~BSTree()
{
Destroy(_root);
}
//不写析构释放，是会产生内存泄露的，但是不会报错
private:
void Destroy(Node*& root)//注意auto是不能作为参数的
{
if (root == nullptr)
{
return;
}
//后序遍历
Destroy(root->_left);
Destroy(root->_right);
delete root;
root = nullptr;
//直接置空是无用的，这里不影响实参
//之前的实现，通常使用二级指针
//但现在更好的办法是使用引用传参
}
private:
Node* _root = nullptr;
};Destroy函数的参数换成Node& root可以吗？
~BSTree()
{
Destroy(*_root);
}
//如果_root是空呢？所以这样实现纯纯是自找麻烦
void Destroy(Node& root)
{
}1.5.2拷贝构造
int main()
{
int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
BSTree<int> bt;
for (auto e : a)
{
bt.InsertR(e);
}
bt.InOrder();
BSTree<int> copy(bt);
//没有写拷贝构造，这里就是浅拷贝，会崩溃
copy.InOrder();
return 0;
}如何书写呢？
template<class K>
class BSTree
{
typedef BSTreeNode<K> Node;
public:
BSTree(const BSTree<K>& t)
{
//t._root = Copy(_root);
_root = Copy(t._root);
}
private:
Node* Copy(Node* root)
{
if (root == nullptr)
{
return nullptr;
}
//前序遍历
Node* newRoot = new Node(root->_key);
newRoot->_left = Copy(root->_left);
newRoot->_right = Copy(root->_right);
return newRoot;
}
private:
Node* _root = nullptr;
};