今天忙到很晚,所以今天就只弄了删除的部分,而且都只是只能删除一个,不能把相同的都删除;而且算法还不简单,改天改进:
// 负责找到最右边的孩子
findBestRight = (node) => {
if (!node.rightChild) {
return node;
}
return this.findBestRight(node.rightChild);
}
_remove = (node, e) => {
if (!node) {
return null;
}
if (node.val === e) {
// 如果相等,那么就有两种情况
// 第一种,只有一个孩子有节点或者两个都没有
if (!node.rightChild) {
return node.leftChild;
}
if (!node.leftChild) {
return node.rightChild;
}
// 第二种情况,找到左边的最右边的孩子放到删除节点的位置上
const newNode = this.findBestRight(node.leftChild)
// 继承原本节点有的右节点
newNode.rightChild = node.rightChild
return newNode
}
if (node.val > e) {
// 如果值小的,那么去左边
node.leftChild = this._remove(node.leftChild, e)
} else {
// 如果值大,那么就去右边
node.rightChild = this._remove(node.rightChild, e)
}
return node;
}
remove = (ele) => {
this.data = this._remove(this.data, ele)
}
算法实现比较简单,但我写的不是很简单,原本我想删除相同节点的,但我发现时间不够了,所以先实现删除单个的。删除节点的终点就是怎么确定谁放到被删除节点的位置。
看明白了就知道为啥我有一个函数叫
findBestRight
,这个就是为了找到左孩子的最右孩子节点。