1.二叉搜索树

1.1二叉搜索树概念

二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:

1.若它的左子树不为空，则左子树上所有节点的值都小于根节点的值

2.若它的右子树不为空，则右子树上所有节点的值都大于根节点的值

3.它的左右子树也分别为二叉搜索树

1.2 二叉搜索树操作 

int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13}; 

1. 二叉搜索树的查找  

a、从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。

b、最多查找高度次，走到到空，还没找到，这个值不存在。

<code>bool nfind(const T& x)

{

return _nfind(root, x);

}

bool _nfind(node* root, const T& x)

{

if (root)

{

if (root->data > x)

{

return _nfind(root->left, x);

}

else if (root->data < x)

{

return _nfind(root->right, x);

}

else

{

return true;

}

}

else

{

return false;

}

}

2. 二叉搜索树的插入  

a. 树为空，则直接新增节点，赋值给root指针

b. 树不空，按二叉搜索树性质查找插入位置，插入新节点

<code>bool Insert(const T& x)

{

return _Insert(root, x);

}

bool _Insert(node*& root, const T& x) //记得要加引用,规避了找父亲连接子节点的问题

{

if (root == nullptr)

{

root = new node(x);

return true;

}

else if (root->data < x)

{

return _Insert(root->right, x);

}

else if (root->data > x)

{

return _Insert(root->left, x);

}

else {

return false;

}

}

3. **二叉搜索树的删除  

 首先查找元素是否在二叉搜索树中，如果不存在，则返回, 否则要删除的结点可能分下面四种情 况：

a. 要删除的结点无孩子结点

b. 要删除的结点只有左孩子结点

c. 要删除的结点只有右孩子结点

d. 要删除的结点有左、右孩子结点

 看起来有待删除节点有4中情况，实际情况a可以与情况b或者c合并起来，因此真正的删除过程 如下：

情况b：删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点--直接删除

情况c：删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点--直接删除

情况d：在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被删除节点 中，再来处理该结点的删除问题--替换法删除//找左子树最大或右子树最小

1.3 二叉搜索树的实现 

<code>namespace zone

{

template<class T>

struct bstnode

{

bstnode(const T& x)

:left(nullptr)

, right(nullptr)

, data(x)

{}

bstnode<T>* left;

bstnode<T>* right;

T data;

};

template<class T>

class bst

{

typedef bstnode<T> node;

public:

bool Insert(const T& x)

{

return _Insert(root, x);

}

bool _Insert(node*& root, const T& x) //记得要加引用,规避了找父亲连接子节点的问题

{

if (root == nullptr)

{

root = new node(x);

return true;

}

else if (root->data < x)

{

return _Insert(root->right, x);

}

else if (root->data > x)

{

return _Insert(root->left, x);

}

else {

return false;

}

}

bool nfind(const T& x)

{

return _nfind(root, x);

}

bool _nfind(node* root, const T& x)

{

if (root)

{

if (root->data > x)

{

return _nfind(root->left, x);

}

else if (root->data < x)

{

return _nfind(root->right, x);

}

else

{

return true;

}

}

else

{

return false;

}

}

bool erase(const T& x)

{

return _erase(root, x);

}

bool _erase(node*& root, const T& x)

{

if (root)

{

if (root->data > x)

{

_erase(root->left, x);

}

else if (root->data < x)

{

_erase(root->right, x);

}

else //开始删除

{

if (root->left == nullptr) //左为空

{

node* ptr = root;

root = root->right;

delete ptr;

}

else if (root->right == nullptr) //右为空

{

node* ptr = root;

root = root->left;

delete ptr;

}

else //左右都不为空，找右子树最小的

{

/*node* it = root->right;

while (it->left)

{

it = it->left;

}

std:swap(root->data, it->data);

return _erase(root->right,x);*/ //从原应当删除的位置的右子树开始删除x！！！！！！！！！！！

node* it = root->left; //左右都不为空，找左子树最大的

while (it->right)

{

it = it->right;

}

std:swap(root->data, it->data);

return _erase(root->left, x); //从原应当删除的位置的左子树开始删除x！！！！！！！！！！！

}

}

}

else

{

return false;

}

}

bst()

{}

bst(const bst<T>& it) //拷贝构造 s1(s2)

{

creat(root, it.root);

}

bst<T>& operator = (bst<T>& it) //拷贝构造 s1=s2

{

swap(root, it.root);

return *this;

}

~bst()

{

destroy(this->root);

}

void destroy(node* root)

{

if (root == nullptr);

return;

destroy(root->left);

destroy(root->right);

delete root;

}

void creat(node*& root1, node* root2)

{

if (root1 == nullptr && root2 == nullptr)

{

root1 = nullptr;

}

else if (root1 == nullptr && root2 != nullptr)

{

node* newnode = new node(root2->data);

root1 = newnode;

creat(root1->left, root2->left);

creat(root1->right, root2->right);

}

}

void inorder() //!!!!!二叉搜索树中序遍历的结果是升序打印

{

_inorder(root);

}

void _inorder(node* root)

{

if (root == nullptr)

return;

_inorder(root->left);

cout << root->data << " ";

_inorder(root->right);

}

private:

node* root = nullptr;

};

}

2.实际应用 

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

比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：

1.以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树

2.在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。

2. KV模型：每一个关键码key，都有与之对应的值Value，即的键值对。该种方 式在现实生活中非常常见： 

1.比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英 文单词与其对应的中文就构成一种键值对；

2.再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出 现次数就是就构成一种键值对。

这里以字典为例：

bst.h:

namespace dictionary

{

template<class T,class K>

struct bstnode

{

bstnode(const T& x, const K& y)

:left(nullptr)

, right(nullptr)

, data(x)

, t(y)

{}

bstnode<T,K>* left;

bstnode<T,K>* right;

T data;

K t;

};

template<class T,class K>

class bst

{

typedef bstnode<T,K> node;

public:

bool Insert(const T& x, const K& y)

{

return _Insert(root,x,y);

}

bool _Insert(node*& root, const T& x, const K& y) //记得要加引用,规避了找父亲连接子节点的问题

{

if (root == nullptr)

{

root = new node(x,y);

return true;

}

else if (root->data < x)

{

return _Insert(root->right,x,y);

}

else if (root->data > x)

{

return _Insert(root->left,x,y);

}

else {

return false;

}

}

node* nfind(const T& x)

{

return _nfind(root, x);

}

node* _nfind(node* root, const T& x)

{

if (root)

{

if (root->data > x)

{

return _nfind(root->left, x);

}

else if (root->data < x)

{

return _nfind(root->right, x);

}

else

{

return root;

}

}

else

{

return nullptr;

}

}

bst()

{}

~bst()

{

destroy(this->root);

}

void destroy(node* root)

{

if (root == nullptr);

return;

destroy(root->left);

destroy(root->right);

delete root;

}

private:

node* root = nullptr;

};

}

test.c:

​

#include<iostream>

using namespace std;

#include"bst.h"

int main()

{

dictionary::bst<string, string>dic;

dic.Insert("sort", "排序");

dic.Insert("tree", "树");

dic.Insert("left", "左");

dic.Insert("right", "右");

dic.Insert("root", "根");

string str;

while (cin >> str)

{

dictionary::bstnode<string, string>* set;

set=dic.nfind(str);

if (set)

cout << set->t << " ";

else

cout << "无此单词" << endl;

}

}

​

字典中插入了：

("sort", "排序");

("tree", "树");

("left", "左");

("right", "右");

("root", "根");

3.性能分析

插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。

对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二 叉搜索树的深度的函数，即结点越深，则比较次数越多。

最优情况下，为完全二叉树(或者接近完全二叉树)其平均比较次数为：O（log_2 N  ）

最差情况下，二叉搜索树退化为单支树(或者类似单支)，其平均比较次数为：O（N）

二叉搜索树的性能都能达到最优？后续学习的AVL树和红黑树就可以上 场了。