C++ 二叉树

1. 二叉搜索树

1.1 二叉搜索树概念

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

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

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

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

1.2 二叉搜索树操作

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

1.二叉搜索树的查找

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

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

2.二叉搜索树的插入

插入的具体过程如下：

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

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

3.二叉搜索树的删除

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

a、要删除的节点无孩子节点

b、要删除的节点只有左孩子节点

c、要删除的节点只有右孩子节点

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

看起来有待删除节点有四种情况，实际情况a可以与b、c结合起来，因此真正的删除过程如下：

*有一个孩子或者无孩子的节点被删除，则让被删除节点的双亲指向被删除节点的孩子或者空——直接删除

*有两个孩子的节点被删除，则在它的右子树中寻找最小的节点，用它的值填补到删除节点中，再来处理该节点的删除问题（符合二叉搜索树，左节点<根<右节点）——替换法删除

1.3 二叉搜索树的实现

树的节点

树

完整代码：

template <class T>
struct BSTNode
{T _key;BSTNode<T>* _left;BSTNode<T>* _right;BSTNode(const T& key):_left(nullptr), _right(nullptr), _key(key){}
};template <class T>
class BSTree
{typedef BSTNode<T> Node;public:BSTree() = default;BSTree(const BSTree<T>& t){_root = Copy(t._root);}~BSTree(){Destory(_root);_root = nullptr;}bool insert(const T& key){if (_root == nullptr){_root = new Node(key);return true;}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;}}cur = new Node(key);if (parent->_key < key){parent->_right = cur;}else{parent->_left = cur;}return true;}Node* Find(const T& key){Node* cur = _root;while (cur){if (cur->_key < key)cur = cur->_right;else if (cur->_key > key)cur = cur->_left;elsereturn cur;}return nullptr;}void InOrder(){_InOrder(_root);cout << endl;}bool Erase(const T& 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{// 删除// 0-1个孩子的情况if (cur->_left == nullptr){if (parent == nullptr){_root = cur->_right;}else{if (parent->_left == cur)parent->_left = cur->_right;elseparent->_right = cur->_right;}delete cur;return true;}else if (cur->_right == nullptr){if (parent == nullptr){_root = cur->_left;}else{if (parent->_left == cur)parent->_left = cur->_left;elseparent->_right = cur->_left;}delete cur;return true;}else{// 2个孩子的情况// 右子树的最小节点作为替代节点Node* rightMinP = cur;Node* rightMin = cur->_right;while (rightMin->_left){rightMinP = rightMin;rightMin = rightMin->_left;}cur->_key = rightMin->_key;if (rightMinP->_left == rightMin)rightMinP->_left = rightMin->_right;elserightMinP->_right = rightMin->_right;delete rightMin;return true;}}}return false;}private:void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_key << " " << endl;_InOrder(root->_right);}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;}void Destory(Node* root){if (root == nullptr){return;}Destory(root->_left);Destory(root->_right);delete root;}Node* _root = nullptr;
};

 1.4 二叉搜索树的应用

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

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

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

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

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

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

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

改造成kv结构的二叉搜索树的代码（与前面的逻辑基本上是一样的，无非就是多了一个值value）

完整代码：

using namespace std;template <class T,class V>
struct BSTNode
{T _key;V _value;BSTNode<T,V>* _left;BSTNode<T,V>* _right;BSTNode(const T& key,const V& value):_left(nullptr),_right(nullptr),_key(key),_value(value){}
};template <class T,class V>
class BSTree
{typedef BSTNode<T,V> Node;public:BSTree() = default;BSTree(const BSTree<T, V>& t){_root = Copy(t._root);}~BSTree(){Destory(_root);_root = nullptr;}bool insert(const T& key,const V& value){if (_root == nullptr){_root = new Node(key,value);return true;}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;}}cur = new Node(key,value);if (parent->_key < key){parent->_right = cur;}else{parent->_left = cur;}return true;}Node* Find(const T& key){Node* cur = _root;while (cur){if (cur->_key < key)cur = cur->_right;else if (cur->_key > key)cur = cur->_left;elsereturn cur;}return nullptr;}void InOrder(){_InOrder(_root);cout << endl;}bool Erase(const T& 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{// 删除// 0-1个孩子的情况if (cur->_left == nullptr){if (parent == nullptr){_root = cur->_right;}else{if (parent->_left == cur)parent->_left = cur->_right;elseparent->_right = cur->_right;}delete cur;return true;}else if (cur->_right == nullptr){if (parent == nullptr){_root = cur->_left;}else{if (parent->_left == cur)parent->_left = cur->_left;elseparent->_right = cur->_left;}delete cur;return true;}else{// 2个孩子的情况// 右子树的最小节点作为替代节点Node* rightMinP = cur;Node* rightMin = cur->_right;while (rightMin->_left){rightMinP = rightMin;rightMin = rightMin->_left;}cur->_key = rightMin->_key;if (rightMinP->_left == rightMin)rightMinP->_left = rightMin->_right;elserightMinP->_right = rightMin->_right;delete rightMin;return true;}}}return false;}private:void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_key << " " << root->_value << endl;_InOrder(root->_right);}Node* Copy(Node* root){if (root == nullptr)return nullptr;Node* newroot = new Node(root->_key, root->_value);newroot->_left = Copy(root->_left);newroot->_right = Copy(root->_right);return newroot;}void Destory(Node* root){if (root == nullptr){return;}Destory(root->_left);Destory(root->_right);delete root;}Node* _root=nullptr;
};

1.5 二叉搜索树的性能分析

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

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

但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：

 

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

最差情况下，二叉搜索树退化为单支树(或者类似单支)，其平均比较次数为：$\frac{N}{2}$

问题：如果退化成单支树，二叉搜索树的性能就失去了。那能否进行改进，不论按照什么次序插入关键码，二叉搜索树的性能都能达到最优？那么AVL树和红黑树就可以上场了，但是这边就不继续讲述AVL和红黑树了。

好了，今天就到这了，我们下次见~

有问题欢迎指正批评！！！