1 二分搜索法

二分搜索法是一个很常用的搜索方法，但是它要求数组必须是一个有序的数组，不然二分搜索就失去了意义。二分搜索是说我们将整个数组分成左右两个部分，让中间的数据和targe进行比较，如果target > arr[mid]表示target在右半区域；如果target < arr[mid]，说明target在左半区域；如果target == arr[mid]说明找到了，返回mide就行。

 二分搜索法可以用递归方法和循环方法实现，它们的逻辑都是相同的：如果不在该区域，就根据mid调整左右边界的范围。

1.1 递归方法

递归方法必不可少的就是递归出口，当左边界left大于右边界right的时候，说明该数组中没有我们想要查找的元素，返回-1。否则的话就继续二分查找，直到找到了我们想要查找的元素。

template<typename T>
int __binarySearch(T arr[], const T value, const int left, const int right) {// 如果找不到就返回-1if (left > right)return -1;int mid = (left + right) / 2;if (value < arr[mid])// 向左半区域进行查找return __binarySearch(arr, value, left, mid - 1);else if (value > arr[mid])// 向右半区域进行查找return __binarySearch(arr, value, mid + 1, right);elsereturn mid;
}// 二分搜索法
template <typename T>
int binarySearch(T arr[], const T value, const int len) {return __binarySearch(arr, value, 0, len - 1);
}

1.2 循环方法

循环方法的循环就是左边界不大于右边界的索引，如果循环跳出，就说明没有找到该元素，返回-1。否则，在循环内部继续更新left或者right，对某区域再进行查找。

template<typename T>
int binarySearch1(T arr[], const T value, const int len) {int left = 0, right = len - 1;int mid;while (left <= right) {mid = left + (right - left) / 2;if (arr[mid] == value)return mid;else if (arr[mid] < value)left = mid + 1;else if (arr[mid] > value)right = mid - 1;}return -1;
}

这里面涉及一个小技巧，mid通常来说是这样计算的 mid = (left+right)/2。但是当left或者right过大而导致left+right数值溢出的情况发生的时候，mid的结果就不得而知了，因此为了避免这个bug，就使用mid = left +(right-left)/2的方法来计算得到mid的值。

在二分搜索中我们只能得到target是否在数组中，但是有时候我们期望即使target不在数组中，我们也能够得到离它较近的元素，比如不大于target的最大的元素（我们称之为floor()函数）和不小于targe的最小的元素（我们称之为ceil()函数）。这两个函数的逻辑和查找的逻辑基本上类型，只不过要对left>right的情况进行处理。

首先，我们要明确在数组中如果没有找到target的时候，left和right的最终的索引位置是怎样的。

我们其实可以发现，right所指向的数据其实就是不大于target的最大的元素，而left所指向的数据其实就是不小于36的最小的元素，换句话说right就是floor()想要返回的索引，而left就是ceil想要返回的索引。还需要注意一点就是，对于floor函数而言，当输入的元素小于数组首个元素的时候，right会变成-1，因此对于这种特殊情况，我们将其置为0；对于ceil函数而言，当输入的元素大于数组末尾元素的时候，left会变成len-1（len表示数组元素的个数），因此我们将left置为len-1。明白了上面的规律之后，我们就可以编写代码了：

1.3 floor()函数

// floor()函数,查找小于value元素的最大数的索引
template<typename T>
int floor(T arr[], const T value, const int len) {int index =  __floor(arr, value, 0, len - 1);return index < 0 ? 0 : index;
}template<typename T>
int __floor(T arr[], const T value, const int left, const int right) {if (left > right)return right;int mid = left + (right - left) / 2;if (value > arr[mid])return __floor(arr, value, mid + 1, right);else if (value < arr[mid])return __floor(arr, value, left, mid - 1);elsereturn mid;
}

1.4 ceil()函数

/*ceil函数*/
template<typename T>
int ceil(T arr[], const T target, const int len) {int index =  __ceil(arr, target, 0, len - 1);return index > len - 1 ? len - 1 : index;
}template<typename T>
int __ceil(T arr[], const T target, const int left, const int right) {if (left > right)return left;int mid = left + (right - left) / 2;if (target < arr[mid])return __ceil(arr, target, left, mid - 1);else if (target > arr[mid])return __ceil(arr, target, mid + 1, right);elsereturn mid;
}

 

2 二叉搜索树

二叉搜索树可以用于“字典”类型的快速查询、删除和索引。相比于其他不用类型实现“字典”的方法，二叉树显得更快：

二叉搜索树并不一定是个完全二叉树，因此不能像最大堆那样使用一个数组来存储各个结点，二叉搜索树使用链式结构来构成一个树形结构。二叉搜索树的成员函数主要有以下几个：

其中，插入和删除是二叉搜索树的难点和重点，因为无论是插入还是删除难的不是插入在那里，而是如何维护与插入节点和删除节点有关的其他节点的关系。插入结点其实就找找到合适的空节点的位置，然后让用新的节点来取代空节点的位置；删除结点无非就是删除某个结点，然后让另找一个子节点取代删除节点的位置。它们都有共同的特定就是“替代”，如何使用代码实现替代的思想呢？我们先来看一下如果编写一个二叉搜索树的类，然后再介绍类的成员函数。

// 二叉搜索树
template<typename Key, typename Value>
class BinarySearchTree {
private:struct Node {Key key;Value value;Node *left;Node *right;// 构造函数Node(Key k, Value v) {key = k;value = k;left = right = nullptr;}};// 二叉搜索树的根节点Node *root;// 二叉树中结点的个数int count;public:// 构造函数和析构函数BinarySearchTree() {root = nullptr;count = 0;}~BinarySearchTree() {// 后序遍历依次释放左右子节点和根结点}
}

 其中有一点需要注意就是结构体有着自己的构造函数，因为当我们需要构建<key,value>键值对的结点的时候 ，我们可以直接借助构造体的构造函数完成，下面介绍插入节点相关知识的时候就用到了这个技巧。

2.1 插入节点

我们先来看一下插入节点的逻辑：我们输入key和value，然后向以root为根节点的子树中插入key和value所构成的结点。如果二叉树中不存在以key为键的结点，就将其插入在合适的位置；如果存在就将key所对应的节点的value进行更新。

上面的两幅图表示了插入结点的两种情况，难点其实就是上面那一幅图，如果在空节点处插入节点，而且还能让之前的节点指向该插入的节点。因为当我们可以处理该空节点的时候，我们其实只能处理该结点的内容的，无法处理父节点指向本节点这个操作了（过了这村就没这店了），而我们恰好就需要父节点指向这个新开辟的内存空间，怎么办呢？这边提供两个思路，使用指向指针的指针或者将本节点作为新的子树根节点返回，让原来的根节点接收这个返回值，从而进行更新。在这里我们使用第二种方法，因为这样更具有普适性，在删除节点的逻辑中也可以借用这种方法。因此，插入节点的代码就如下所示 ：

/*操作：向二叉树中插入数据*/
/*结果：输入一个键值对，二叉树中新增一个节点，count++*/
void insert(const Key key, const Value value) {// 插入函数涉及到结点的修改，因此返回修改子树的根节点作为新子树的根节点root = insert(root, key, value);
}

下面的代码是核心，insert()函数中返回该子树的新的根节点。

/*操作：向以node为根结点的子树中插入数据*/
/*结果：传入该子树的根节点node，以及要插入的键值对，count++，返回修改之后子树的根节点*/
Node *insert(Node *node, const Key key, const Value value) {if (nullptr == node) {// 向空节点出插入新节点count++;return new Node(key, value);}if (key < node->key)node->left = insert(node->left, key, value);else if (key > node->key)node->right = insert(node->right, key, value);else // key == node->key，修改key的valuenode->value = value;return node;
}

2.2 contain函数

contain函数用来判断二叉搜索树中是否包含以key为键的节点，如果存在返回ture；否则，返回false。contain函数的逻辑和insert函数的相似，只不过在对“节点为空”和“找到相同key节点”的处理上稍有不同：

/*操作：二叉搜索树中是否包含key的节点*/
/*结果：如果包含，返回true；否则，返回false*/
bool contain(const Key key) {return contain(root, key);
}

下面是核心代码： 

/*操作：判断以node为根节点的子树中是否包含key的节点*/
/*结果：返回bool类型数据。如果存在返回true，否则返回false*/
bool contain(Node *node, const Key key) {if (nullptr == node)return false;if (key < node->left)return contain(node->left, key);else if (key > node->right)return contain(node->right, key);else // key == node->keyreturn true;
}

2.3 search函数

search函数用来查找以key为键的节点的value值。这里需要着重考虑一下，search函数的返回值应该是什么？是value吗？万一该二叉搜索树中不存在key所对应的节点呢，这时候应该返回什么？search()可以返回Value*，你没看错，返回的可以是Value类型的指针，如果存在，我们只需要返回该节点value的地址就行；如果不存在，我们返回nullptr就行，这样就不会有返回值不匹配的情况出现：

/*操作：向二叉树中查找key所对应的value值*/
/*结果：返回Value*类型的数据。如果存在，就返回value的指针；否则，返回nullptr*/
Value *search(const Value value) {return search(root, value);
}

下面和核心代码：

/*操作：查找以node为根结点的子树中key所对应的value值*/
/*结果：返回Value*类型。如果存在返回Value的指针；否则，返回空指针*/
Value *search(Node *node, const Key key) {if (nullptr == node)return nullptr;if (key < node->key)return search(node->left);else if (key > node->key)return search(node->right);else // key == node->keyreturn &(node->key);
}

2.4 二叉搜索树的遍历

二叉树的遍历主要包括深度优先遍历和广度优先遍历，前者又分为前序遍历、中序遍历和后序遍历。广度优先遍历主要包括层序遍历。深度优先遍历的三种方式其实逻辑都是一样的，只不多输出节点的顺序上有所不同。

因此，我们将深度优先遍历的代码放在一起，因为这并不是这一小节的重点

下面的内容是主要的核心代码

	/*操作：对以node为根节点的子树进行前序遍历*//*结果：打印结点*/void preOrder(Node *node) {if (node != nullptr) {cout << node->key << " ";preOrder(node->left);preOrder(node->right);}}/*操作：对以node为根节点的子树进行中序遍历*//*结果：打印结点*/void inOrder(Node *node) {if (node != nullptr) {inOrder(node->left);cout << node->key << " ";inOrder(node->right);}}/*操作：对以node为根节点的子树进行后序遍历*//*结果：打印结点*/void postOrder(Node *node) {if (node != nullptr) {postOrder(node->left);postOrder(node->right);cout << node->key << " ";}}

层序遍历就需要我们动脑筋好好想想：如何让节点按照一层一层的顺序进行输出打印呢？比如下面这个子树，我们如何顺序打印30， 20， 50？

这边提供的一个思路就是，我们首先将30这个节点放到一个队列；然后将队列的首个节点取出来，并将该节点的左右节点压入队列中，直到整个队列为空，说明整个二叉搜素树就遍历完成。相关的过程如下图所示：

层序遍历的代码如下： 

/*操作：层序遍历*/
/*结果：打印结点。按照层序遍历，打印结点，要借助队列缓存左右节点*/
void levelOrder() {assert(count > 0);std::queue<Node*> myQueue;myQueue.push(root);Node *temp;while (!myQueue.empty()) {// 取出首个节点，打印key；然后将左右子节点压入队列中temp = myQueue.front();cout << temp->key << " ";myQueue.pop();if (temp->left != nullptr)myQueue.push(temp->left);if (temp->right != nullptr)myQueue.push(temp->right);}}

2.5 查找最大和最小的节点

在二叉搜素树中，哪里是最小的节点，哪里是最大的节点？根据二叉搜索树的定义来说，我们可以发现，在左子树中没有左节点的就是最小节点；同理，在右子树中没有右节点的就是最大节点。因此，我们可以根据这两个性质来找到相应的最大节点和最小结点。

/*操作：查找二叉树中最小结点的key*/
/*结果：返回Key类型。返回最小节点的key值*/
Key minimum() {assert(count > 0);Node *node = minimum(root);return node->key;
}/*操作：查找二叉树中最大结点的key*/
/*结果：返回Key类型。返回最大节点的key值*/
Key maximum() {assert(count > 0);Node *node = maximum(root);return node->key;
}

minimum()函数和maximum()函数用来返回最小的节点，这个知识点在后面删除节点的时候也用到了，很重要！！！

/*操作：对以node节点为根节点的子树寻找最小节点的key*/
/*结果：返回最小节点。没有左节点的节点就是最小节点*/
Node* minimum(Node *node) {if (node->left == nullptr)return node;return minimum(node->left);
}/*操作：对以node节点为根节点的子树寻找最大节点的key*/
/*结果：返回最大节点。没有右节点的节点就是最大节点*/
Node *maximum(Node *node) {if (node->right == nullptr)return node;return maximum(node->right);
}

2.6 删除最小节点和最大节点

删除节点的时候涉及到节点的维护，因此其处理的逻辑和insert()函数的相似，使用一个Node* function(Node *node)作为新旧根节点的更新和维护。删除最值节点也有两种情况：一种是“孤家寡人”型的节点，另一种是“拖家带口”型的节点。我们拿删除最大值节点为例，如下图所示：

 

对于最大节点来说，“孤家寡人”就是说最大节点没有左节点；“拖家带口”就是说最大结点有左子树。对于前者，我们只需要删除该节点，然后返回空指针即可；而对于“拖家带口”的最大节点，我们要删除该节点，然后返回左子树根节点即可。其实，这两种情况可以归为一类来处理我们都“删除该节点，返回左子树根节点”，因为对于“孤家寡人”它的左子树根节点就为空，这样我们在写代码的时候，其实就少进行了一种判断，而且看上去更精炼。对于删除最小节点的思路也是这样，相关代码如下：

/*操作：删除二叉搜索树中的最小结点*/
/*结果：无返回值。删除最小节点*/
void removeMin() {root = removeMin(root);
}/*操作：删除二叉树搜索中的最大节点*/
/*结果：无返回值。删除最大节点*/
void removeMax() {removeMax(root);
}

核心代码如下，其基本框架和寻找最小节点和最大节点的思路相同，这是因为我们必须先要找到，然后才能进行删除。

/*操作：删除以node为根节点的二叉搜索树的最小节点*/
/*结果：返回删除之后子树的根节点,count--*/
Node *removeMin(Node *node) {if (nullptr == node->left) {// 返回右节点,删除本节点Node *tempR = node->right;delete node;count--;return tempR;}node->left = removeMin(node->left);return node;
}/*操作：删除以node为根节点的二叉搜索树的最大节点*/
/*结果：返回删除之后子树的根节点,count--*/
Node *removeMax(Node *node) {if (nullptr == node->right) {// 返回该节点的左节点，并删除该节点，count--Node *tempL = node->left;delete node;count--;return tempL;}node->right = removeMax(node->right);return node;
}

2.7 删除节点

节点的删除的还是一样的，先要找到节点，然后再进行删除，因此其基本逻辑就和search函数的基本上类似了，不同的就是当我们对找到该节点的处理方法有所不同。当我们找到要删除的节点的时候，我们首先要判断节点所处的位置情况，看有没有左右子树，如果有子树，它是有左子树还是右子树还是左右子树都有？

情况0：如果没有找到key键值所对应的节点

         直接返回空指针

情况1：如果该节点没有子树

          那这是最理想的情况了，我们删除该节点，然后返回空节点就行

情况2：如果存在左节点或者右节点

对于只有一个子节点的节点来说，我们只需要将子树的根节点返回作为该子树的根节点返回即可。对于这种情况，我们可以和情况1进行合并：如果左子树不为空，我们就返回右子树的根节点；如果右子树不为空，我们就返回左子树的根节点。这样我们通过这两个简单的判断就可以囊括三种不同的情况，思想很巧妙。

情况3：左右子树都存在

对于这种情况就比较复杂了，其中的一种删除算法就是上面所提到的：当我们删除某个节点的时候，我们需要找到一个节点作为左右子树的根节点。根据二叉搜索树的性质，这个节点必须要大于左子树的所有节点并且小于右子树的所有节点，这个节点就属右子树的最小节点莫属了。因此，我们可以找到右子树的最小节点，然后将其作为该子树的根节点返回，然后再删除旧的根节点即可。基本步骤如下：

（1）找到右子树的最小节点，并创建和该节点同属性的新节点successor。创建新的节点是为了后面删除最小节点的时候不会影响这个找到的该节点，因此后面我们要用到这个最小的节点。

（2）删除右子树的最小节点，然后让successor的右节点指向删除之后的右子树的根节点（正好可以使用removeMin函数，它返回的就是删除以node为节点的最小节点并返回新子树的根节点），让successor的左节点指向旧根节点的左节点。通过这两步，我们就可以实现“狸猫换太子”，然后删除旧的根节点，并将新的根节点successor返回，进行根节点的更新。

这是Hibbard deletion算法的基本思想，它的代码如下：

/*操作：删除二叉树的key对应的结点*/
/*结果：无返回值。删除key所对应的节点*/
void removeNode(const Key key) {assert(count > 0);root = removeNode(root, key);
}

核心代码如下

/*操作：删除以node为根节点的子树的key对应的节点*/
/*结果：返回该子树的根节点*/
Node* removeNode(Node *node,const Key key) {if (nullptr == node)return nullptr;if (key < node->key) {node->left = removeNode(node->left, key);return node;}else if (key > node->key) {node->right = removeNode(node->right, key);return node;}else {// key == node->key	// 如果该节点的左节点为空，返回该节点的右节点作为该子树的根节点if (node->left == nullptr) {Node *tempR = node->right;delete node;count--;return tempR;}// 如果该节点的右节点为空，返回该节点的左节点作为该子树的根节点if (node->right == nullptr) {Node *tempL = node->left;delete node;count--;return tempL;}// 左右节点都存在时候，使用hibbard删除方法// 首先找到该节点右子树的最小节点Node *successor = new Node(minimum(node->right));// 然后，删除该节点右子树的最小节点successor->right = removeMin(node->right);// 最后，让最小节点连接该节点的左右子树，删除该节点successor->left = node->left;count++;delete node;count--;return successor;
}

其中，我们用到了根据一个节点创建新节点的构造函数

Node *successor = new Node(minimum(node->right));

因此，在节点结构体编写构造函数的时候，要加上这样几行代码，最终的结构体就是这样

struct Node {Key key;Value value;Node *left;Node *right;// 构造函数Node(Key k, Value v) {key = k;value = k;left = right = nullptr;}// 根据一个结点来创建新的节点Node(Node *node) {key = node->key;value = node->value;left = node->left;right = node->right;}
};

其中，我对hibbard deletion进行了改进，不知道有没有人这样用过，具体我没有调查。按照hibbard deletion删除节点的思想是找到右子树最小节点，然后再创建一个属性一样的新节点successor，然后再更更新左右节点，再删除旧的根节点。我想的就是，我们其实并不需要删除就的根节点，我们只要维护旧节点的key和value就行，然后再删除右子树的最小结点。

这样整个代码就变成了这样

/*操作：删除以node为根节点的子树的key对应的节点*/
/*结果：返回该子树的根节点*/
Node* removeNode(Node *node,const Key key) {if (nullptr == node)return nullptr;if (key < node->key) {node->left = removeNode(node->left, key);return node;}else if (key > node->key) {node->right = removeNode(node->right, key);return node;}else {// key == node->key	// 如果该节点的左节点为空，返回该节点的右节点作为该子树的根节点if (node->left == nullptr) {Node *tempR = node->right;delete node;count--;return tempR;}// 如果该节点的右节点为空，返回该节点的左节点作为该子树的根节点if (node->right == nullptr) {Node *tempL = node->left;delete node;count--;return tempL;}Node *successor = minimum(node->right);node->key = successor->key;node->value = successor->value;node->right = removeMin(node->right);return node;
}

个人觉得要比未改进之前的要容易操作，而且并不需要担心count的加一减一的情况。

 

3 附录

下面贴上整个二叉搜索树的代码

#pragma once
#ifndef _BINARY_SEARCH_TREE_
#define _BINARY_SEARCH_TREE_#include <queue>	
#include <cassert>// 二叉搜索树
template<typename Key, typename Value>
class BinarySearchTree {
private:struct Node {Key key;Value value;Node *left;Node *right;// 构造函数Node(Key k, Value v) {key = k;value = k;left = right = nullptr;}// 根据一个结点来创建新的节点Node(Node *node) {key = node->key;value = node->value;left = node->left;right = node->right;}};// 二叉搜索树的根节点Node *root;// 二叉树中结点的个数int count;public:// 构造函数和析构函数BinarySearchTree() {root = nullptr;count = 0;}~BinarySearchTree() {// 后序遍历依次释放左右子节点和根结点destory();}/*操作：判断二叉搜索树是否为空*//*结果：如果为空，返回true；否则，返回false*/bool isEmpty() {return 0 == count;}/*操作：返回二叉搜索树中结点的个数*//*结果：返回int类型数据，表示结点的个数*/int size() {return count;}/*操作：向二叉树中插入数据*//*结果：输入一个键值对，二叉树中新增一个节点，count++*/void insert(const Key key, const Value value) {// 插入函数涉及到结点的修改，因此返回修改子树的根节点作为新子树的根节点root = insert(root, key, value);}/*操作：二叉搜索树中是否包含key的节点*//*结果：如果包含，返回true；否则，返回false*/bool contain(const Key key) {return contain(root, key);}/*操作：向二叉树中查找key所对应的value值*//*结果：返回Value*类型的数据。如果存在，就返回value的指针；否则，返回nullptr*/Value *search(const Value value) {return search(root, value);}/*操作：前序遍历*//*结果：打印结点。按照前序遍历，根结点，左右结点的顺序打印节点key值*/void preOrder() {preOrder(root);}/*操作：中序遍历*//*结果：打印结点。按照前序遍历，根结点，左右结点的顺序打印节点key值*/void inOrder() {inOrder(root);}/*操作：后序遍历*//*结果：打印结点。按照前序遍历，根结点，左右结点的顺序打印节点key值*/void postOrder() {postOrder(root);}/*操作：层序遍历*//*结果：打印结点。按照层序遍历，打印结点，要借助队列缓存左右节点*/void levelOrder() {assert(count > 0);std::queue<Node*> myQueue;myQueue.push(root);Node *temp;while (!myQueue.empty()) {// 取出首个节点，打印key；然后将左右子节点压入队列中temp = myQueue.front();cout << temp->key << " ";myQueue.pop();if (temp->left != nullptr)myQueue.push(temp->left);if (temp->right != nullptr)myQueue.push(temp->right);}}/*操作：查找二叉树中最小结点的key*//*结果：返回Key类型。返回最小节点的key值*/Key minimum() {assert(count > 0);Node *node = minimum(root);return node->key;}/*操作：查找二叉树中最大结点的key*//*结果：返回Key类型。返回最大节点的key值*/Key maximum() {assert(count > 0);Node *node = maximum(root);return node->key;}/*操作：删除二叉搜索树中的最小结点*//*结果：无返回值。删除最小节点*/void removeMin() {root = removeMin(root);}/*操作：删除二叉树搜索中的最大节点*//*结果：无返回值。删除最大节点*/void removeMax() {removeMax(root);}/*操作：删除二叉树的key对应的结点*//*结果：无返回值。删除key所对应的节点*/void removeNode(const Key key) {assert(count > 0);root = removeNode(root, key);}private:// 后序遍历来释放节点void destory() {destory(root);}void destory(Node *node) {if (nullptr == node)return;destory(node->left);destory(node->right);// 释放节点delete node;count--;;}/*操作：向以node为根结点的子树中插入数据*//*结果：传入该子树的根节点node，以及要插入的键值对，count++，返回修改之后子树的根节点*/Node *insert(Node *node, const Key key, const Value value) {if (nullptr == node) {// 向空节点出插入新节点count++;return new Node(key, value);}if (key < node->key)node->left = insert(node->left, key, value);else if (key > node->key)node->right = insert(node->right, key, value);else // key == node->key，修改key的valuenode->value = value;return node;}/*操作：判断以node为根节点的子树中是否包含key的节点*//*结果：返回bool类型数据。如果存在返回true，否则返回false*/bool contain(Node *node, const Key key) {if (nullptr == node)return false;if (key < node->left)return contain(node->left, key);else if (key > node->right)return contain(node->right, key);else // key == node->keyreturn true;}/*操作：查找以node为根结点的子树中key所对应的value值*//*结果：返回Value*类型。如果存在返回Value的指针；否则，返回空指针*/Value *search(Node *node, const Key key) {if (nullptr == node)return nullptr;if (key < node->key)return search(node->left);else if (key > node->key)return search(node->right);else // key == node->keyreturn &(node->key);}/*操作：对以node为根节点的子树进行前序遍历*//*结果：打印结点*/void preOrder(Node *node) {if (node != nullptr) {cout << node->key << " ";preOrder(node->left);preOrder(node->right);}}/*操作：对以node为根节点的子树进行中序遍历*//*结果：打印结点*/void inOrder(Node *node) {if (node != nullptr) {inOrder(node->left);cout << node->key << " ";inOrder(node->right);}}/*操作：对以node为根节点的子树进行后序遍历*//*结果：打印结点*/void postOrder(Node *node) {if (node != nullptr) {postOrder(node->left);postOrder(node->right);cout << node->key << " ";}}/*操作：对以node节点为根节点的子树寻找最小节点的key*//*结果：返回最小节点。没有左节点的节点就是最小节点*/Node* minimum(Node *node) {if (node->left == nullptr)return node;return minimum(node->left);}/*操作：对以node节点为根节点的子树寻找最大节点的key*//*结果：返回最大节点。没有右节点的节点就是最大节点*/Node *maximum(Node *node) {if (node->right == nullptr)return node;return maximum(node->right);}/*操作：删除以node为根节点的二叉搜索树的最小节点*//*结果：返回删除之后子树的根节点,count--*/Node *removeMin(Node *node) {if (nullptr == node->left) {// 返回右节点,删除本节点Node *tempR = node->right;delete node;count--;return tempR;}node->left = removeMin(node->left);return node;}/*操作：删除以node为根节点的二叉搜索树的最大节点*//*结果：返回删除之后子树的根节点,count--*/Node *removeMax(Node *node) {if (nullptr == node->right) {// 返回该节点的左节点，并删除该节点，count--Node *tempL = node->left;delete node;count--;return tempL;}node->right = removeMax(node->right);return node;}/*操作：删除以node为根节点的子树的key对应的节点*//*结果：返回该子树的根节点*/Node* removeNode(Node *node,const Key key) {if (nullptr == node)return nullptr;if (key < node->key) {node->left = removeNode(node->left, key);return node;}else if (key > node->key) {node->right = removeNode(node->right, key);return node;}else {// key == node->key	// 如果该节点的左节点为空，返回该节点的右节点作为该子树的根节点if (node->left == nullptr) {Node *tempR = node->right;delete node;count--;return tempR;}// 如果该节点的右节点为空，返回该节点的左节点作为该子树的根节点if (node->right == nullptr) {Node *tempL = node->left;delete node;count--;return tempL;}// 左右节点都存在时候，使用hibbard删除方法// 首先找到该节点右子树的最小节点//Node *successor = new Node(minimum(node->right));然后，删除该节点右子树的最小节点//successor->right = removeMin(node->right);最后，让最小节点连接该节点的左右子树，删除该节点//successor->left = node->left;//count++;//delete node;//count--;//return successor;Node *successor = minimum(node->right);node->key = successor->key;node->value = successor->value;node->right = removeMin(node->right);return node;}}
};#endif // !_BINARY_SEARCH_TREE_

下面是我测试时候用到的测试代码： 

#include <iostream>	
#include "binarySearchTree.h"using namespace std;
int main() {BinarySearchTree<int, int> tree = BinarySearchTree<int, int>();// 向二叉树搜索树中中添加键值对for (int i = 0;i < 20;i++)tree.insert(rand() % 100, rand() % 100);// 中序遍历二叉搜素数tree.inOrder();cout << endl;// 层序遍历打印二叉搜索树节点keytree.levelOrder();cout << endl;cout << "count = " << tree.size() << endl;// 打印二叉搜索树中的最小节点和最大节点cout << "min node key = " << tree.minimum() << endl;cout << "max node key = " << tree.maximum() << endl;// 删除二叉树搜索树的最小节点和最大节点tree.removeMin();tree.removeMax();tree.inOrder();cout << endl;cout << "count = " << tree.size() << endl;// 删除某个结点tree.removeNode(91);tree.inOrder();cout << endl;
}

相应的运行结果如下