我目前正在研究二叉搜索树的 odin 项目。我正在尝试使 deleteNode 工作,并且正在努力删除一个节点(如果它是叶节点)。这是我的代码:class Node { constru...
我目前正在研究二叉搜索树的 odin 项目。我正在尝试使 deleteNode 工作,并且正在努力删除一个节点(如果它是叶节点)。
这是我的代码:
class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
class BinarySearchTree {
constructor() {
this.root = null;
}
buildTree(array) {
//accepts an array of integers and sort them into binary search tree;
//loop through the given array, creating a node for each item. insert nodes into the array in a binarySearchTree manner.
array.forEach((item) => {
this.insert(item);
});
}
insert(value) {
//accepts an integer value and sort it into the tree;
let newNode = new Node(value);
if (this.root === null) {
this.root = newNode;
return this;
}
let current = this.root;
while (true) {
if (value === current.value) return undefined;
if (value < current.value) {
if (current.left === null) {
current.left = newNode;
return this;
}
current = current.left;
} else if (value > current.value) {
if (current.right === null) {
current.right = newNode;
return this;
}
current = current.right;
}
}
}
deleteNode(value) {
let current = this.root;
let prev;
if (!current) {
console.log("hello");
return undefined;
}
while (current) {
if (current.value > value) {
prev = current;
current = current.left;
} else if (current.value < value) {
prev = current;
current = current.right;
} else {
//node found.
//case 1: node is leaf node, no left and right children
if (!current.left && !current.right) {
if (prev.value > current.value) {
prev.left = null;
} else {
prev.right = null;
}
console.log("leaf node deleted", current);
return this;
}
//case 2: node has either left or right child
//case 3: node has both left and right children
}
}
}
find(value) {
//accepts an integer value and search for it in the tree. IF found ,return the node with the value;
if (this.root === null) {
return undefined;
}
let current = this.root;
while (current) {
if (current.value === value) {
return current;
} else if (current.value > value) {
current = current.left;
} else {
current = current.right;
}
}
return false;
}
levelOrder(callback) {
//BFS
const queue = [];
const data = [];
let node = this.root;
queue.push(this.root);
while (queue.length) {
node = queue.shift();
data.push(node.value);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
return data;
}
inOrder(callback) {
//inOrderDFS
if (this.root === null) {
return undefined;
}
const data = [];
let current = this.root;
const traverse = (node) => {
if (node.left) {
traverse(node.left);
}
data.push(node.value);
if (node.right) {
traverse(node.right);
}
};
traverse(current);
return data;
}
preOrder(callback) {
//preOrderDFS
if (this.root === null) {
return undefined;
}
const data = [];
let current = this.root;
const traverse = (node) => {
data.push(node.value);
if (node.left) traverse(node.left);
if (node.right) traverse(node.right);
};
traverse(current);
return data;
}
postOrder(callback) {
//postOrderDFS
if (this.root === null) {
return undefined;
}
const data = [];
let current = this.root;
const traverse = (node) => {
if (node.left) traverse(node.left);
if (node.right) traverse(node.right);
data.push(node.value);
};
traverse(current);
return data;
}
}
const odinTree = new BinarySearchTree();
const array = [10, 20, 12, 15, 11, 50, 35, 21, 5, 2, 9, 3];
odinTree.buildTree(array);
以下是 deleteNode 的代码:
deleteNode(value) {
let current = this.root;
let prev;
if (!current) {
console.log("hello");
return undefined;
}
while (current) {
if (current.value > value) {
prev = current;
current = current.left;
} else if (current.value < value) {
prev = current;
current = current.right;
} else {
//node found.
//case 1: node is leaf node, no left and right children
if (!current.left && !current.right) {
if (prev.value > current.value) {
prev.left = null;
} else {
prev.right = null;
}
console.log("leaf node deleted", current);
return this;
}
//case 2: node has either left or right child
//case 3: node has both left and right children
}
}
}
我尝试在控制台上运行代码,它确实有效。但是,我尝试刷新页面并按下键盘上的 up 键来运行相同的代码以删除相同的叶节点,结果卡住了。
我很确定我的代码没问题,因为我尝试在几个叶节点上输入 tree.deleteNode,它们都成功了。只有当我尝试按 keyup 运行 deleteNode 时,页面才会卡住。
任何意见都将受到赞赏,谢谢!
const odinTree = new BinarySearchTree(); const array = [10, 20, 12, 15, 11, 50, 35, 21, 5, 2, 9, 3]; odinTree.buildTree(array); 然后我手动输入:odinTree.deleteNode(21),这是一个叶节点,它起作用了。接下来,我按下 keyup,这样我就不必再次输入整个内容,我将 21 更改为 35(现在是叶节点),然后它就卡住了。更奇怪的是,如果我手动输入 odinTree.deleteNode(21),然后手动输入 odinTree.deleteNode(35),它就起作用了,我可以继续处理其他叶子。只有当我按下 keyup 运行相同的操作时,chrome 选项卡才会卡住