JavaScript二叉排序树的插入、查找、删除

傷城~ 2022-05-22 10:58 152阅读 0赞

<!DOCTYPE html>
    <html>
      <head>
        <title>Hello World</title>
      </head>
    
      <body>
    
    
        <script type="text/javascript">
          function BinaryTree() {
              function Node(key) {
                  this.key = key;
                  this.left = null;
                  this.right = null;
              }
    
              var root = null;
    
              //具体的实现
              var insertNode = function (node, newNode) {
                  if (newNode.key < node.key) {
                      if (node.left === null) {
                          node.left = newNode;
                      } else {
                          insertNode(node.left, newNode);
                      }
                  } else {
                      if (node.right === null) {
                          node.right = newNode;
                      } else {
                          insertNode(node.right, newNode);
                      }
                  }
              };
    
              var inOrderTraverseNode = function (node, callback) {
                  if (node !== null) {
                      inOrderTraverseNode(node.left, callback);
                      callback(node.key);
                      inOrderTraverseNode(node.right, callback);
                  }
              };
    
              var preOrderTraverseNode = function (node, callback) {
                  if (node !== null) {
                      callback(node.key);
                      preOrderTraverseNode(node.left, callback);
                      preOrderTraverseNode(node.right, callback);
                  }
              };
    
              var postOrderTraverseNode = function (node, callback) {
                  if (node !== null) {
                      postOrderTraverseNode(node.left, callback);
                      postOrderTraverseNode(node.right, callback);
                      callback(node.key);
                  }
              };
    
              var minNode = function (node) {
                  if (node) {
                      while (node.left) {
                          node = node.left;
                      }
                      return node.key;
                  }
                  return null;
              };
    
              var maxNode = function (node) {
                  if (node) {
                      while (node.right) {
                          node = node.right;
                      }
                      return node.key;
                  }
                  return null;
              };
    
              var searchNode = function (node, key) {
                  if (node) {
                      if (key < node.key) {
                          return searchNode(node.left, key);
                      } else if (key > node.key) {
                          return searchNode(node.right, key);
                      } else {
                          return true;
                      }
                  } else {
                      return false;
                  }
              };
    
              var findMinNode = function (node) {
                  if (node) {
                      while (node.left) {
                          node = node.left;
                      }
                      return node;
                  }
    
                  return null;
              };
    
              var removeNode = function (node, key) {
                  if (node) {
                      if (key < node.key) {
                          node.left = removeNode(node.left, key);
                          return node;
                      } else if (key > node.key) {
                          node.right = removeNode(node.right, key);
                          return node;
                      } else { //如果相等
                          if (node.left === null && node.right === null) {
                              node = null;
                              return node;
                          }
                          if (node.left === null) {//只有右子树
                              node = node.right;
                              return node;
                          } else if (node.right === null) {//只有左子树
                              node = node.left;
                              return node;
                          }
                          var tmp = findMinNode(node.right);
                          node.key = tmp.key;
                          node.right = removeNode(node.right, tmp.key);
                          return node;
                      }
                  }
                  return null;
              };
    
              //这是对外的接口
              this.inOrderTraverse = function (callback) {
                  inOrderTraverseNode(root, callback);
              };
    
              this.preOrderTraverse = function (callback) {
                  preOrderTraverseNode(root, callback);
              };
    
              this.postOrderTraverse = function (callback) {
                  postOrderTraverseNode(root, callback);
              };
    
              this.insert = function (key) {
                  var newNode = new Node(key);
                  if (root === null) {
                      root = newNode;
                  } else {
                      insertNode(root, newNode);
                  }
              };
              
              this.min = function () {
                  return minNode(root);
              };
    
              this.max = function () {
                  return maxNode(root);
              };
              
              this.search = function (key) {
                  return searchNode(root, key);
              };
    
              this.remove = function (key) {
                  root = removeNode(root, key);
              };
          }
    
          var nodes = [8, 3, 10, 1, 6, 14, 4, 7, 13];
          var binaryTree = new BinaryTree();
    
          nodes.forEach(function (key) {
              binaryTree.insert(key);
          });
          
          var callback = function (key) {
              console.log(key);
          };
    
          binaryTree.remove(8);
          binaryTree.inOrderTraverse(callback);
        </script>
      </body>
    
    </html>