gpt4 book ai didi

javascript - 一种用于二叉树搜索、遍历、插入和删除的算法

转载 作者:塔克拉玛干 更新时间:2023-11-03 06:38:30 25 4
gpt4 key购买 nike

我看到像 this 这样的二叉树实现:

var insert = function(value, root) {
if (!root) {
// Create a new root.
root = { val: value };
}
else {
var current = root;
while (current) {
if (value < current.val) {
if (!current.left) {
// Insert left child.
current.left = { val: value };
break;
}
else {
current = current.left;
}
}
else if (value > current.val) {
if (!current.right) {
// Insert right child.
current.right = { val: value };
break;
}
else {
current = current.right;
}
}
else {
// This value already exists. Ignore it.
break;
}
}
}

return root;
}

var exists = function(value, root) {
var result = false;

var current = root;
while (current) {
if (value < current.val) {
current = current.left;
}
else if (value > current.val) {
current = current.right;
}
else {
result = true;
break;
}
}

return result;
}

var traversePre = function(head, callback) {
// Preorder traversal.
if (head) {
if (callback) {
callback(head.val);
}

traversePre(head.left, callback);
traversePre(head.right, callback);
}
}

var traversePost = function(head, callback) {
// Postorder traversal.
if (head) {
traversePost(head.left, callback);
traversePost(head.right, callback);

if (callback) {
callback(head.val);
}
}
}

var traverseIn = function(head, callback) {
// Inorder traversal.
if (head) {
traverseIn(head.left, callback);

if (callback) {
callback(head.val);
}

traverseIn(head.right, callback);
}
}

var traverseInIterative = function(head, callback) {
// Inorder traversal (iterative style).
var current = head;
var history = [];

// Move down to the left-most smallest value, saving all nodes on the way.
while (current) {
history.push(current);
current = current.left;
}

current = history.pop();
while (current) {
if (callback) {
callback(current.val);
}

// Move to the right, and then go down to the left-most smallest value again.
current = current.right;
while (current) {
history.push(current);
current = current.left;
}

current = history.pop();
}
}

var root = insert(10);
insert(5, root);
insert(6, root);
insert(3, root);
insert(20, root);

特别是,traverseInIterative 对我来说看起来很不错。但我想知道是否真的需要 insertexists,同样需要 searchdelete。我知道(就像在这些实现中一样)它们的实现方式不同,但想知道您是否可以实现一个通用匹配函数来一次性解决所有问题,同时在性能方面达到理想状态。

最佳答案

设计一个通用方法来完成所有操作的一种方法是 -

genericMethod(value, root, command)

此处的command 参数将接收一个字符串,指定insertdeletesearch。根据命令参数,您可以调整内部实现以支持所有操作。

现在让我们来谈谈性能和设计方面的问题。我不认为有这样的方法是理想的。使用这样的通用方法会给您带来比您想象的更多的问题。

现在,在检查了您的代码后 - 有许多可以改进的地方,我认为这会给您带来更好的体验,例如 -

  • 对于插入/删除——你需要检查值是否已经存在。所以只需调用 exists() 方法,而不是在这些方法中编写相同的代码。

这种类型的通用行为确保您不会一次又一次地编写相同的代码以及 SRP(单一职责原则),因此您的代码被完美地划分并且更易于阅读。

关于javascript - 一种用于二叉树搜索、遍历、插入和删除的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/54683862/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com