当然，删除操作也不止这一种解决思路，还有一种合并删除的思路——从被删除节点的两颗子树中合并为一颗，然后将这颗树连接到被删除节点的父节点处。
也同样分3种情况处理：
被删除的节点为叶子节点，直接删除即可；
被删除的节点只有左子树或者右子树，直接将其左子树或右子树上移即可；
被删除的节点有左子树和右子树，同样有两种方法：
将被删除节点的整颗右子树合并到左子树的最大值节点后面形成一个新的子树（找到左子树中最大值节点，使它成为右子树的父节点），将新的子树连接到被删除节点的父节点。
将被删除节点的整颗左子树合并到右子树的最小值节点后面形成一个新的子树（找到右子树中最小值节点，使它成为左子树的父节点），将新的子树连接到被删除节点的父节点。
template<class T> void BST<T>::deleteByMerging(BSTNode<T>*& node) { BSTNode<T> *tmp = node; if (node != 0) { // 只有右子树或左子树的情况 if (!node->right) // node has no right child: its left node = node->left; // child (if any) is attached to its parent; else if (node->left == 0) // node has no left child: its right node = node->right; // child is attached to its parent; else { // be ready for merging subtrees; // 将被删除节点的整颗右子树合并到被删除节点的左子树的最大节点处 tmp = node->left; // 1. move left while (tmp->right != 0)// 2. and then right as far as possible; tmp = tmp->right; tmp->right = // 3. establish the link between the node->right; // the rightmost node of the left // subtree and the right subtree; tmp = node; // 4. node = node->left; // 5. 新的子树代替原有被删除节点的位置，链接到被删除节点的父节点 } delete tmp; // 6. } } 对比复制删除与合并删除这两种思路，复制删除操作不会增加树的高度，而合并删除则可能会增加树的高度。 遍历操作遍历操作方法有深度优先和广度优先两大类，其中深度优先遍历中又有前序、中序、后序等遍历方法。
广度优先遍历 //广度优先遍历（从上到下，从左到右，一层一层的向下访问） template<class T> void BST<T>::breadthFirst() { Queue<Node<T>*> m_queue; //要理解这里为什么要用队列，这个队列的作用是把下一层的数据放到本层数据的后面 Node<T>* p = root; if (p != NULL) { m_queue.enqueue(p); while (!m_queue.empty()) { p = m_queue.dequeue(); visit(p); if (p->left != NULL) m_queue.enqueue(p->left); if (p->right != NULL) m_queue.enqueue(p->right); } } } 深度优先遍历前序遍历——节点->左子树->右子树；
中序遍历——左子树->节点->右子树；这里补充一条：二叉查找树的中序遍历，即是二叉查找树节点从小到大的排序结果；
后序遍历——左子树->右子树->节点；
//中序遍历，递归实现 template<class T> void BST<T>::inorder(Node<T> *p) { if (p != NULL) { inorder(p->left); visit(p); inorder(p->right); } } //前序遍历，递归实现 template<class T> void BST<T>::preorder(Node<T> *p) { if (p != NULL) { visit(p); preorder(p->left); preorder(p->right); } } //后续遍历，递归实现 template<class T> void BST<T>::postorder(Node<T>* p) { if (p != NULL) { postorder(p->left); postorder(p->right); visit(p); } }递归实现是非常容易理解的，下面是非递归实现。
//前序遍历，非递归实现 template<class T> void BST<T>::iterativePreorder() { Stack<Node<T>*> m_stack; Node<T>* p = root; if (p != NULL) { m_stack.push(p);//从跟节点开始压 while (!m_stack.empty()) { p = m_stack.pop(); visit(p); if (p->right != NULL)//先压右子节点再压左子节点，因为要左侧先出 m_stack.push(p->right); if (p->left != NULL) // left child pushed after right m_stack.push(p->left); } } } //后序遍历，非递归实现 template<class T> void BST<T>::iterativePostorder() { Stack<Node<T>*> m_stack; Node<T>* p = root, *q = root; while (p != NULL) { for (; p->left != NULL; p = p->left) m_stack.push(p); while (NULL == p->right || q == p->right) { visit(p); q = p; if (m_stack.empty()) return; p = m_stack.pop(); } m_stack.push(p); p = p->right; } } //中序遍历，非递归实现 template<class T> void BST<T>::iterativeInorder() { Stack<Node<T>*> m_stack; Node<T>* p = root; while (p != NULL) { while (p != NULL) { // stack the right child (if any) if (p->right) // and the node itself when going m_stack.push(p->right); // to the left; m_stack.push(p); p = p->left; } p = m_stack.pop(); // pop a node with no left child while (!m_stack.empty() && p->right == NULL) { // visit it and all nodes visit(p); // with no right child; p = m_stack.pop(); } visit(p); // visit also the first node with if (!m_stack.empty()) // a right child (if any); p = m_stack.pop(); else p = NULL; } } 查找最大值与最小值根据二叉查找树的性质：
对于树中的每个节点X，它的左子树中所有项的值都要小于X中的项；
对于树中的每个节点Y，它的右子树中所有项的值都要大于Y中的项。
我们可以从root节点开始：
一直沿着左节点往下找，直到子节点等于NULL为止，这样就可以找到最小值了；
一直沿着右节点往下找，直到子节点等于NULL为止，这样就可以找到最大值了。