二叉搜素树的查找：
若是空树，直接返回false
若不是空树，则分为以下几种情况
1.如果根节点data = https://www.it610.com/article/查找的data， 返回true
2.如果根节点data > 查找的data，在其左子树查找
3.如果根节点data < 查找的data,在其右子树查找
文章图片
PNode find(const T& data)
{
if(nullptr == _pRoot)
return nullptr;
PNode pcur = _pRoot;
while(pcur)
{
if(data < pcur->_data)
pcur = pcur->_pLeft;
else if(data > pcur->_data)
pcur = pcur->_pRight;
else
return pcur;
}
}二叉搜索树的插入
若为空树，则直接插入，返回true
若树不空，按照二叉搜索树的性质找到插入的位置，插入新的节点
若元素已经存在则插入失败，返回false ,插入成功，返回true
bool insert(const T& data)
{
//树空直接插入
if(nullptr ==_pRoot)
{
//构造一个节点插入
_pRoot = new Node(data);
return true;
}//按照二叉树搜索树的性质查找data在树中的插入位置
PNode pcur = _pRoot;
//pparent记录pcur的双亲，最终将新节点插在ppatent的左右孩子的位置
PNode pparent = nullptr;
while(pcur)
{
pparent = pcur;
if(data < pcur->_data)
pcur = pcur->_pLeft;
else if(data > pcur->_data)
pcur = pcur->_pRight;
// 元素已经存在树中了
else
return false;
}//插入元素
pcur = new Node(data);
if(data < pparent->_data)
pparent->_pLeft = pcur;
else
pparent->_pRight = pcur;
return true;
}
文章图片
二叉搜索树的删除
二叉搜索数的删除在它的基本操作中属于较为复杂的，因为在删除树中的元素时，会有四种情况进行分析：
删除的节点有以下这四种情况：
a.叶子节点（没有左右孩子）
b.节点只有左孩子
c.节点只有右孩子
d.节点的左右孩子都存在
pcur表示删除的节点， parent表示pcur双亲
情况a: 删除叶子节点，可以直接删除
情况b:删除只有左孩子的节点，使被删除节点的双亲指向被被删除节点的左孩子
情况c.删除只有右孩子的节点，使被删除节点的双亲指向被被删除节点的右孩子
情况d.删除左右孩子都存在的节点，不可以直接删除，
1.找其左子树中的最大节点，即左子树中最右侧的节点，或者在其右子树中最小的节点，即右子树中最小的节点
2.替代节点找到后，将替代节点中的值交给待删除节点，转换成删除替代节点
bool insert(const T& data)
{
//树空直接插入
if(nullptr ==_pRoot)
{
//构造一个节点插入
_pRoot = new Node(data);
return true;
}//按照二叉树搜索树的性质查找data在树中的插入位置
PNode pcur = _pRoot;
//pparent记录pcur的双亲，最终将新节点插在ppatent的左右孩子的位置
PNode pparent = nullptr;
while(pcur)
{
pparent = pcur;
if(data < pcur->_data)
pcur = pcur->_pLeft;
else if(data > pcur->_data)
pcur = pcur->_pRight;
// 元素已经存在树中了
else
return false;
}//插入元素
pcur = new Node(data);
if(data < pparent->_data)
pparent->_pLeft = pcur;
else
pparent->_pRight = pcur;
return true;
}
bool erase(const T& data)
{
//如果空树，删除失败
if(nullptr == _pRoot)
return false;
//查找data在树中的位置
PNode pcur = _pRoot;
PNode pparent = nullptr;
while(pcur)
{
if(data < pcur->_data)
pparent = pcur;
pcur = pcur->_pLeft;
else if(data > pcur->_data)
pparent = pcur;
pcur = pcur->_pRight;
//找到值为data节点
else
break;
}
//循环结束后，pcur可能标记的不是data,可能为空，那么data不在树中，则无法删除
if(nullptr == pcur)
return false;
//分以下情况进行删除
if(nullptr == pcur->_pRight)
{
//当前节点只有左孩子或者左孩子为空 ---可以直接删除
if(nullptr == pparent)
{
//cur是跟节点
_pRoot = pcur->_pLeft;
}
else
{
pparent->_pLeft = pcur->_pLeft;
delete pcur;
}
}
else if(nullptr == pcur->_pLeft) // 一定又有右孩子
{
//当前节点只有右孩子 -- 可以直接删除
if(nullptr == pparent)
{
//cur是根节点
_pRoot = pcur->_pRight;
}
else
{
// cur的双亲一定存在
if(pcur == pparent->_pLeft)
pparent->_pLeft = pcur->_pRight;
else
pparent->_pRight = pcur->_pLeft;
}
}
//节点的左右孩子都存在，不能直接删除
else
{
// 1.找其左子树中的最大节点，即左子树中最右侧的节点，或者在其右子树中最小的节点，即右子树中最小的节点
// 2.替代节点找到后，将替代节点中的值交给待删除节点，转换成删除替代节点
PNode pDelete = pcur->_pRight;
//在删除节点的右子树中找最小的的节点，也就是最左侧节点
pparent = pcur;
while(pDelete->_pLeft)
{
pparent = pDelete;
pDelete = pDelete->_pLeft;
}
// 找到pcur右子树最小节点
// 交换data
pcur->_data = https://www.it610.com/article/pDelete->_data;
//删除替代节点pparent->_pLeft = pDelete->_pRight;
delete pDelete;
}
}【二叉搜索树的操作（重点了解删除操作）】
