C++类 二叉排序树删除节点

BinaryTreeNode: 节点类
BinaryTree：二叉排序树类

//删除一个节点自身
template<typename T>
BinaryTreeNode<T>* BinaryTreeNode<T>::RemoveSelf() {//分三种情况//第一种情况：要删除的是叶子节点,改变父节点的指向，删除该节点if (nullptr == pLeft && nullptr == pRight){//判断当前节点是父节点的左节点还是右节点if (pParent->pLeft == this){pParent->pLeft = nullptr;cout << "是左节点" << endl;}else{pParent->pRight = nullptr;}delete this;//释放当前节点的内存return nullptr;//返回删除后的当前位置的新节点}//第二种情况：要删除的节点有一个节点，可再细分为只有左节点或者右节点//只有左节点没有右节点else if (nullptr == pRight){BinaryTreeNode<T>* pNode = pLeft;//判断当前节点是父节点的左节点还是右节点if (pParent->pLeft == this){pParent->pLeft = pLeft;}else{pParent->pRight = pLeft;}pLeft->pParent = pParent;delete this;//释放当前节点的内存return pNode;//返回删除后的当前位置的新节点，即当前节点的左节点}//只有右节点没有左节点else if (nullptr == pLeft){BinaryTreeNode<T>* pNode = pRight;//判断当前节点是父节点的左节点还是右节点if (pParent->pLeft == this){pParent->pLeft = pRight;}else{pParent->pRight = pRight;}pRight->pParent = pParent;delete this;//释放当前节点的内存return pNode;//返回删除后的当前位置的新节点，即当前节点的右节点}//第三种情况：要删除的节点既有左节点，又有右节点，找到一个后继节点的值，赋给要删除的节点值，然后删除这个后继节点//找到一个后继节点值比要删除的节点大，但是最接近要删除的节点，即为要删除的节点的右子树中的最小值，//或要删除的节点的左子树中的最大值，这样才可保证替换要删除的节点的值，还能满足左小右大。else{	//1.查找右子树中数据最小的节点BinaryTreeNode<T>* pMin = this->finMinDataNode();//2.将最小数据覆盖要删除节点的数据this->val = pMin->val;//3.递归删除最小数据节点pMin->RemoveSelf();return this; //返回删除后的当前位置的新节点，因为当前节点只是值被替换，所以还是当前节点}//注：第三种情况将找到的这个后继节点的值赋给要删除的节点值后 ，此时应该要删除这个后继节点，//如果不使用递归，则是以下两种情况//1.如果没有右节点，问题变成整个问题的第一种情况，因为后继节点是个叶子节点，直接删除//2.如果有右节点，问题变成整个问题的第二种情况
}template<typename T> //查找当前结点的右子树的最小数据结点 
BinaryTreeNode<T>* BinaryTreeNode<T>::finMinDataNode()
{BinaryTreeNode<T> * pMin = this->pRight;while (pMin->pLeft != nullptr){pMin = pMin->pLeft;//一直往左边找}return pMin;
}template<typename T>//根据节点值查找节点
BinaryTreeNode<T>* BinaryTreeNode<T>::findNode(const T& val)
{BinaryTreeNode<T>* pNode = this;//当前结点while (pNode != nullptr){//判断val与pNode的数据进行比较if (val < pNode->val){pNode = pNode->pLeft;}else if (val > pNode->val){pNode = pNode->pRight;}else{return pNode;}}return pNode;
}

template<typename T>
void BinaryTree<T>::Remove(const T& val)
{if (pRoot != nullptr){if (pRoot->val != val){BinaryTreeNode<T>* pNode = pRoot->findNode(val);//查找结点pNode->RemoveSelf();//移除结点}else//要删除的是根结点{pRoot = pRoot->RemoveSelf();}}
}