c++二叉树

二叉树进阶

1.二叉搜索树(binary search tree)

​ 二叉搜索树天然就适合查找，对于满二叉树或者完全二叉树，最多搜索lgn次(就像是有序数组二分查找，每次搜索都会减少范围)，极端情况简化成单链表就要走n次，即要走高度次，时间复杂度是O(N)。所以需要用时间复杂度为O(lgn)的AVL树(平衡二叉树)或者RB树(红黑树)解决。

​ 按中序遍历，得到的结果就是有序的，升序；后序删除方便很多，不用保留前面的值；拷贝不可以调用插入，否则结构会发生巨大的变化，而是使用前序来赋值 。

​ 相较于普通的二叉树，增删查改就有了意义，而有序数组二分查找是不可以的，挪动数据效率很低。

​ 二叉搜索树不允许有重复，key一般要唯一。

1.1概念

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

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

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

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

2.二叉搜索树非递归模拟实现

#pragma once
#include <cassert>
namespace BinarySearchTree
{template <class K>struct BSTreeNode{BSTreeNode(const K &key = 0) : left_(nullptr), right_(nullptr), key_(key) {}BSTreeNode<K> *left_;BSTreeNode<K> *right_;K key_;};template <class K>class BSTree{// 内嵌类型typedef BSTreeNode<K> node;public:// 默认成员函数BSTree() : root_(nullptr){}~BSTree() {}public:// 普通成员函数bool insert(const K &key);void inorder(){_inorder(root_);}void _inorder(node *root);bool find(const K &key);bool erase(const K &key);private:// 成员变量node *root_;};template <class K>bool BSTree<K>::insert(const K &key){if (root_ == nullptr){root_ = new node(key);return true;}node *cur = root_;node *parent = root_;while (cur){if (cur->key_ == key){return false;}else if (key > cur->key_){parent = cur;cur = cur->right_;}else{parent = cur;cur = cur->left_;}}cur = new node(key);if (key > parent->key_){parent->right_ = cur;}else{parent->left_ = cur;}return true;}template <class K>void BSTree<K>::_inorder(BSTree<K>::node *root){if (root == nullptr){return;}_inorder(root->left_);cout << root->key_ << " ";_inorder(root->right_);}template <class K>bool BSTree<K>::find(const K &key){if (root_ == nullptr){return false;}node *cur = root_;while (cur){if (key == cur->key_){return true;}else if (key > cur->key_){cur = cur->right_;}else{cur = cur->left_;}}return false;}template <class K>bool BSTree<K>::erase(const K &key){node *cur = root_;node *parent = cur;while (cur){if (key == cur->key_){// 找到了,托孤要考虑删root；// 没有孩子，托孤nullptr// 有一个孩子，托孤if (cur->left_ == nullptr){if (cur == root_){parent = cur->right_;}else{if (key_ > parent->key_){parent->right_ = cur->right_;}else{parent->left_ = cur->right_;}}}else if (cur->right_ == nullptr){if (cur == root_){parent = cur->left_;}else{if (key_ > parent->key_){parent->right_ = cur->left_;}else{parent->left_ = cur->left_;}}}else // 有两个孩子，要取左子树最右或者右子树最左{node *leftmax = cur->left_; // 可能cur->left为leftmaxnode *pleftmax = cur;while (leftmax->right_){pleftmax = leftmax;leftmax = leftmax->right_;}std::swap(cur->key_, leftmax->key_);if (pleftmax->left_ == leftmax){pleftmax->left_ = leftmax->left_;}else{pleftmax->right_ = leftmax->left_;}cur = leftmax;}delete cur;return true;}else if (key > cur->key_){parent = cur;cur = cur->right_;}else{parent = cur;cur = cur->left_;}}return false;}}

3.二叉搜索树优点

​ 1.查找效率高；

​ 2.可以顺便实现排序，升序；

​ 3.插入删除效率都不错；

4.二叉搜索树递归实现

#pragma once
#include <cassert>
namespace BinarySearchTree
{template <class K>struct BSTreeNode{BSTreeNode(const K &key = 0) : left_(nullptr), right_(nullptr), key_(key) {}BSTreeNode<K> *left_;BSTreeNode<K> *right_;K key_;};template <class K>class BSTree{// 内嵌类型typedef BSTreeNode<K> node;public:// 默认成员函数BSTree() : root_(nullptr){}BSTree(const BSTree<K> &t){root_ = copy(t.root_);}BSTree<K> &operator=(BSTree<K> t){swap(*this, t);return *this;}~BSTree(){destroy(root_);}public:// 普通成员函数void swap(BSTree<K> &t);bool insert(const K &key){return _insert(root_, key);}void inorder(){_inorder(root_);cout << endl;}bool find(const K &key){return _find(root_, key);}bool erase(const K &key){return _erase(root_, key);}private:// 私有成员node *copy(node *root);void destroy(node *&root);bool _insert(node *&root, const K &key);bool _find(node *root, const K &key);void _inorder(node *root);bool _erase(node *&root, const K &key);node *root_;};template <class K>bool BSTree<K>::_insert(node *&root, const K &key){if (root == nullptr){root = new node(key);return true;}if (key > root->key_){return _insert(root->right_, key);}else if (key < root->key_){return _insert(root->left_, key);}else{return false;}}template <class K>void BSTree<K>::_inorder(node *root){if (root == nullptr){cout << "nullptr"<< " ";return;}_inorder(root->left_);cout << root->key_ << " ";_inorder(root->right_);}template <class K>bool BSTree<K>::_find(node *root, const K &key){if (root == nullptr){return false;}if (key > root->key_){return _find(root->right_, key);}else if (key < root->key_){return _find(root->left_, key);}else{return true;}}template <class K>bool BSTree<K>::_erase(node *&root, const K &key){if (root == nullptr){return false;}if (key > root->key_){return _erase(root->right_, key);}else if (key < root->key_){return _erase(root->left_, key);}else{node *del = root;if (root->left_ == nullptr){root = root->right_;}else if (root->right_ == nullptr){root = root->left_;}else{node *leftmax = root->left_;while (leftmax->right_){leftmax = leftmax->right_;}std::swap(leftmax->key_, root->key_);return _erase(root->left_, key);}delete del;return true;}}template <class K>void BSTree<K>::destroy(node *&root){if (root == nullptr){return;}destroy(root->left_);destroy(root->right_);delete root;root = nullptr;}template <class K>typename BSTree<K>::node *BSTree<K>::copy(node *root){if (root == nullptr){return nullptr;}node *newnode = new node(root->key_);newnode->left_ = copy(root->left_);newnode->right_ = copy(root->right_);return newnode;}template <class K>void BSTree<K>::swap(BSTree<K> &t){std::swap(root_, t.root_);}
}

5.二叉搜索树的应用场景

5.1key的搜索模型(在不在的场景)

​ 门禁系统、车辆输入系统、查找单词是否拼写错误，将词库放到一颗搜索树之中，然后find。

5.1key/value的搜索模型(通过一个值找另外一个值)

​ 手机号找快递信息、停车场(按时计费)、身份证检票查找车票信息，不用制造车票并往车票里写入信息；

namespace key_value
{template <class K, class V>struct BSTreeNode{BSTreeNode(const K &key = K(), const V &value = V()) : left_(nullptr), right_(nullptr), key_(key), value_(value) {}BSTreeNode<K, V> *left_;BSTreeNode<K, V> *right_;K key_;V value_;};template <class K, class V>class BSTree{// 内嵌类型public:typedef BSTreeNode<K, V> node;public:// 默认成员函数BSTree() : root_(nullptr){}~BSTree(){}public:// 普通成员函数bool insert(const K &key, const V &value){return _insert(root_, key, value);}void inorder(){_inorder(root_);cout << endl;}node *find(const K &key){return _find(root_, key);}bool erase(const K &key){return _erase(root_, key);}private:// 私有成员bool _insert(node *&root, const K &key, const V &value);node *_find(node *root, const K &key);void _inorder(node *root);bool _erase(node *&root, const K &key);node *root_;};template <class K, class V>bool BSTree<K, V>::_insert(node *&root, const K &key, const V &value){if (root == nullptr){root = new node(key, value);return true;}if (key > root->key_){return _insert(root->right_, key, value);}else if (key < root->key_){return _insert(root->left_, key, value);}else{return false;}}template <class K, class V>void BSTree<K, V>::_inorder(node *root){if (root == nullptr){return;}_inorder(root->left_);cout << root->key_ << " : " << root->value_ << "  ";_inorder(root->right_);}template <class K, class V>typename BSTree<K, V>::node *BSTree<K, V>::_find(node *root, const K &key){if (root == nullptr){return nullptr;}if (key > root->key_){return _find(root->right_, key);}else if (key < root->key_){return _find(root->left_, key);}else{return root;}}template <class K, class V>bool BSTree<K, V>::_erase(node *&root, const K &key){if (root == nullptr){return false;}if (key > root->key_){return _erase(root->right_, key);}else if (key < root->key_){return _erase(root->left_, key);}else{node *del = root;if (root->left_ == nullptr){root = root->right_;}else if (root->right_ == nullptr){root = root->left_;}else{node *leftmax = root->left_;while (leftmax->right_){leftmax = leftmax->right_;}std::swap(leftmax->key_, root->key_);return _erase(root->left_, key);}delete del;return true;}}
}