基于我的另一篇文章《算法与数据结构基础4：C++二叉树实现及遍历方法大全》 ，二叉树的结构用的这篇文章里的。

二查找叉树的删除可以细分为三种情况：
1 被删除的是叶子节点，直接删除；
2 被删除只有一个子节点，指针下移；
3 有两个子节点，为了不破坏树的结构，需要找出一个节点来替换当前节点。
  根据二叉树的特点，当前节点大于所有左子树，小于所有右子树，
  可以用左子树中最大的节点，或者右子树最小的节点来替换当前节点，然后删除替换节点。


  // BSTree.h

#include <cstdio>
#include <iostream>
#include <stack>
#include <queue>

using namespace std;

// binary search tree，中文翻译为二叉搜索树、二叉查找树或者二叉排序树。简称为BST
class BSTree
{
	struct Node{
		Node(int x = 0):data(x), lchild(NULL), rchild(NULL){}
		struct Node* lchild;
		struct Node* rchild;
		int data;
	};

public:
	// **************************************************************************
	// 类的四大函数：构造函数、拷贝构造函数、重载赋值运算符、析构函数
	// **************************************************************************
	BSTree();
	~BSTree();

	// **************************************************************************
	// 增删改查
	// **************************************************************************
	void Insert(int x);
	void Remove(int x);

	// 返回二叉树的个数
	unsigned short Size();
	unsigned short Deep();
	unsigned short Leaf();

	bool IsEmpty();

	// 遍历
	void PreorderTraversal();	// 先序遍历
	void InorderTraversal();	// 中序遍历
	void PostorderTraversal();	// 后序遍历
	void DepthFirstSearch();	// 深度优先遍历
	void BreadthFirstSearch();	// 广度优先遍历

private:
	void Remove(int x, Node** pNode);

	// 递归计算二叉树个数
	unsigned short CountSize(Node* n);
	unsigned short CountDeep(Node* n);
	unsigned short CountLeaf(Node* n);

	// 递归遍历
	void PreorderTraversal(Node* n);
	void InorderTraversal(Node* n);
	void PostorderTraversal(Node* n);
	void DepthFirstSearch(Node* n);
	void BreadthFirstSearch(Node* n);

	void Free(Node* node);
private:
	Node* m_root;
};

// **************************************************************************
// 私有方法
// **************************************************************************
/* 
//1 请问下面这份代码有什么问题？
void BSTree::Remove(int x, Node* node)
{
	if (!node) {
		return;
	}
	if (x < node->data) {
		Remove(x, node->lchild);
	}
	else if (x > node->data){
		Remove(x, node->rchild);
	}
	else if (node->lchild && node->rchild) {
		Node* min = node->rchild;
		while(min->lchild){
			min = min->lchild;
		}
		node->data = http://www.mamicode.com/min->data;>


  // main.cpp
// test for BSTree
#include "BSTree.h"
#include <cstdlib>
#include <iostream>

using namespace std;

int main()
{
	BSTree tree;
	int arr[6] = {5, 4, 8, 1, 7, 10};
	for (int i = 0; i < 6; ++i){
		tree.Insert(arr[i]);
	}
	
	tree.PreorderTraversal();
	tree.InorderTraversal();
	tree.PostorderTraversal();
	tree.DepthFirstSearch();
	tree.BreadthFirstSearch();

	tree.Remove(4);
	tree.PreorderTraversal();

	tree.Remove(1);
	tree.PreorderTraversal();

	tree.Remove(10);
	tree.PreorderTraversal();

	cout << "size:" << tree.Size() << endl;
	cout << "deep:" << tree.Deep() << endl;
	cout << "leaf:" << tree.Leaf() << endl;

	system("pause");
	return 0;
}



  // 树的结构
  


  // 运行结果截图

算法与数据结构基础11：C++实现——二拆搜索树节点删除