时间戳

首页 > 解决方案 > 二叉树搜索、遍历、插入和删除的一种算法

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

问题描述

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

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对我来说看起来很不错。但我想知道是否真的需要拥有insertand exists，同样需要拥有searchor delete。我知道（就像在这些实现中一样）它们的实现方式不同，但想知道您是否可以实现一个通用匹配函数，一举解决所有问题，同时在性能方面尽可能理想。

标签： javascriptalgorithmbinary-tree

解决方案

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

genericMethod(value, root, command)

这里command的参数将接收一个字符串，指定insertordelete或search。根据命令参数，您可以调整内部实现以支持所有操作。

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

现在在查看您的代码之后 - 有许多可以改进的地方，在我看来这会给您带来更好的体验，例如 -

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

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

推荐阅读