若是空树，直接返回false
若不是空树，则分为以下几种情况
1.如果根节点data = 查找的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 = pDelete->_data; //删除替代节点 pparent->_pLeft = pDelete->_pRight; delete pDelete; } }
