二叉搜索樹(shù)是以一棵二叉樹(shù)來(lái)組織的。每個(gè)節(jié)點(diǎn)是一個(gè)對(duì)象，包含的屬性有l(wèi)eft，right，p和key，其中，left指向該節(jié)點(diǎn)的左孩子，right指向該節(jié)點(diǎn)的右孩子，p指向該節(jié)點(diǎn)的父節(jié)點(diǎn)，key是它的值

1、二叉搜索樹(shù)的概念

二叉搜索樹(shù)又稱二叉排序樹(shù)，它可以是一顆空樹(shù)，亦可以是一顆具有如下性質(zhì)的二叉樹(shù)：

①若根節(jié)點(diǎn)的左子樹(shù)不為空，則左子樹(shù)上的所有節(jié)點(diǎn)的值域都小于根節(jié)點(diǎn)的值

②若根節(jié)點(diǎn)的右子樹(shù)不為空，則右子樹(shù)上的所有節(jié)點(diǎn)的值域都大于根節(jié)點(diǎn)的值

③根節(jié)點(diǎn)的左右子樹(shù)分別也是一顆二叉搜索樹(shù)

例如下面的這棵二叉樹(shù)就是一棵二叉搜索樹(shù)：

注意：判定一棵二叉樹(shù)是否為二叉搜索樹(shù)一定要緊扣二叉搜索樹(shù)的概念~

2、二叉搜索樹(shù)的操作

聲明：該文章討論的是二叉搜索樹(shù)中節(jié)點(diǎn)值唯一的情況。

二叉搜索樹(shù)的查找

對(duì)于查找部分，充分利用二叉搜索樹(shù)的特性，即右子樹(shù)的value 大于根節(jié)點(diǎn)，左子樹(shù)的value小于根節(jié)點(diǎn)。

例如：查找下圖中的紅色方框中的節(jié)點(diǎn)

以6對(duì)應(yīng)的節(jié)點(diǎn)為列，查找過(guò)程主要經(jīng)歷如下幾個(gè)步驟：

①6與根節(jié)點(diǎn)5比較，6 > 5,因此到5的右子樹(shù)查找

①6與根節(jié)點(diǎn)7比較，6 < 7,因此到7的左子樹(shù)查找

①6與根節(jié)點(diǎn)6比較，6 == 6,此時(shí)查找成功！

總結(jié)基本步驟：

若根節(jié)點(diǎn)不為空：

如果根節(jié)點(diǎn)的key == 查找的key----->返回true

如果根節(jié)點(diǎn)的key > 查找的key----->轉(zhuǎn)到根節(jié)點(diǎn)的右子樹(shù)查找

如果根節(jié)點(diǎn)的key < 查找的key----->轉(zhuǎn)到根節(jié)點(diǎn)的左子樹(shù)查找

否則（根節(jié)點(diǎn)為空了），直接返回false，表示樹(shù)中不存在要查找的key

二叉搜索樹(shù)的插入

主要分兩大類的情況進(jìn)行討論：

1、樹(shù)為空，直接插入

如下圖所示：

2、樹(shù)不空

①按照二叉搜索樹(shù)的性質(zhì)查找插入的位置

②插入新的節(jié)點(diǎn)

e.g:在下面的二叉搜索樹(shù)中插入-1

第一步，查找插入位置：

注意：要標(biāo)記當(dāng)前訪問(wèn)的節(jié)點(diǎn)的雙親，否則，就算找到了插入位置，由于無(wú)法訪問(wèn)其雙親，也是無(wú)法進(jìn)行插入的。這里使用parent來(lái)標(biāo)記當(dāng)前訪問(wèn)節(jié)點(diǎn)的雙親節(jié)點(diǎn)。

具體過(guò)程如下圖：

第二步，插入新節(jié)點(diǎn)

判斷待插入節(jié)點(diǎn)(node)的值與parent標(biāo)記的節(jié)點(diǎn)值的大小關(guān)系

if(node->value < parent->value)//新節(jié)點(diǎn)作為parent的左孩子
{
	parent->left = node;
}
else//新節(jié)點(diǎn)作為parent的右孩子
{
	parent->right = node;
}

以上就是二叉搜索樹(shù)插入的兩大類情況及其處理方式

二叉搜索樹(shù)的刪除

刪除也是分為兩大步驟：

1、找到待刪除結(jié)點(diǎn)，并標(biāo)記其雙親

具體代碼片段如下：

Node* delNode = root;//標(biāo)記待刪除結(jié)點(diǎn)
Node* parent = nullptr;//標(biāo)記待刪除結(jié)點(diǎn)的雙親
while(delNode)
{
	if(delNode->value == value)
	{
		break;
	}
	else if(delNode->value > value)
	{
		parent = delNode;
		delNode = delNode->left;
	}
	else
	{
		parent = delNode;
		delNode = delNode->right;
	}
}

上述代碼執(zhí)行完畢后，delNode有兩種情況，delNode == nullptr || delNode!=nullptr

下面我們就這兩種情況展開(kāi)討論：

2、刪除該節(jié)點(diǎn)

Ⅰ、nullptr == delNode

說(shuō)明在二叉搜索樹(shù)中不存在要?jiǎng)h除的結(jié)點(diǎn)。直接return false；

Ⅱ、delNode != nullptr;

在二叉搜索樹(shù)中找到了刪除結(jié)點(diǎn)，開(kāi)始刪除。

刪除時(shí)，對(duì)于待刪除結(jié)點(diǎn)要根據(jù)其孩子節(jié)點(diǎn)分情況討論：

①待刪除結(jié)點(diǎn)是葉子結(jié)點(diǎn)

②待刪除結(jié)點(diǎn)只有左孩子

③待刪除結(jié)點(diǎn)只有有孩子

④待刪除結(jié)點(diǎn)左右孩子均存在

下面，我們就這4中情況展開(kāi)討論：

情況一：待刪除結(jié)點(diǎn)時(shí)葉子節(jié)點(diǎn)

可以直接刪除，具體如下圖：

情況二：待刪除結(jié)點(diǎn)只有左孩子

在此前提下，有兩類情形

1、delNode的雙親存在

2、delNode的雙親不存在

下面就這兩種情況展開(kāi)討論：

1、delNode的雙親存在

刪除過(guò)程見(jiàn)下圖：

2、delNode的雙親不存在

與上述僅存在葉子節(jié)點(diǎn)時(shí)存在的問(wèn)題一樣，需要在delete待刪除結(jié)點(diǎn)之前，判斷delNode與parent的位置關(guān)系，進(jìn)而確定是更新parent的left指針域還是right指針域

結(jié)合上述兩種情況，初步確定僅有左孩子的刪除代碼片段如下：

if(nullptr == parent)
{
	root = delNode->left;
}
else
{
	if(delNode == parent->left)
	{
		parent->left = delNode->left;
	}
	else
	{
		parent->right = delNode->left;
	}
}
delete delNode;

我們結(jié)合刪除節(jié)點(diǎn)是葉子節(jié)點(diǎn) && 刪除節(jié)點(diǎn)僅有左子樹(shù)兩種情況來(lái)看，發(fā)現(xiàn)這兩種情況可以進(jìn)行合并。合并后的代碼如下圖：

情況三：待刪除結(jié)點(diǎn)只有右孩子

該情況與只有左孩子的分析過(guò)程一樣，存在兩類情形，分別是

1、delNode的雙親存在

2、delNode的雙親不存在

這里不再進(jìn)行分析，直接給出代碼：

情況四：待刪除結(jié)點(diǎn)左右孩子均存在

明確：該情況無(wú)法直接刪除，需要在其子樹(shù)中尋找替代結(jié)點(diǎn) 具體刪除步驟如下：

1、找替代節(jié)點(diǎn)：在delNode的右子樹(shù)（左子樹(shù)）找最左側(cè)（最右側(cè)）的結(jié)點(diǎn)并保存其雙親

2、將替代節(jié)點(diǎn)中的值域賦值給待刪除結(jié)點(diǎn)

3、將替代節(jié)點(diǎn)刪除掉

①如果替代節(jié)點(diǎn)找的是delNode右子樹(shù)的最左側(cè)結(jié)點(diǎn)，那么待刪除的替代節(jié)點(diǎn)一定不會(huì)有左子樹(shù)，可能會(huì)有右子樹(shù)

②如果替代節(jié)點(diǎn)找的是delNode左子樹(shù)的最右側(cè)結(jié)點(diǎn)，那么待刪除的替代節(jié)點(diǎn)一定不會(huì)有右子樹(shù)，可能會(huì)有左子樹(shù) 注意：一般情況下采用delNode右子樹(shù)的最左側(cè)結(jié)點(diǎn)作為替代節(jié)點(diǎn)

具體過(guò)程見(jiàn)下圖：

ok,下面給出實(shí)現(xiàn)的代碼：

3、二叉搜索樹(shù)的實(shí)現(xiàn)

數(shù)據(jù)結(jié)構(gòu)：

template<class T>
struct BSTNode//每一個(gè)結(jié)點(diǎn)的結(jié)構(gòu)
{
	BSTNode<T>* _left;//左指針域
	BSTNode<T>* _right;//右指針域
	T _value;//值域

	BSTNode(const T& value = T())
		:_left(nullptr)
		, _right(nullptr)
		, _value(value)
	{}
};

采用模板的方式實(shí)現(xiàn)，具體代碼見(jiàn) BinarySearchTree