Javascript中的二进制搜索树类

这是BinarySearchTree类的完整实现-

示例

class BinarySearchTree {
   constructor() {
      //将根元素初始化为null。
      this.root = null;
   }
   insertIter(data) {
      let node = new this.Node(data);

   //检查树是否为空
   if (this.root === null) {
      //插入为第一个元素
      this.root = node;
      return;
   }
   let currNode = this.root;
   while (true) {
   if (data < currNode.data) {
      //到达叶节点后，在此处设置值
      if (currNode.left === null) {
         currNode.left = node;
            break;
         } else {
            currNode = currNode.left;
         }
      } else {
         //到达叶节点后，在此处设置值
         if (currNode.right === null) {
            currNode.right = node;
            break;
         } else {
            currNode = currNode.right;
         }
      }
   }
}
insertRec(data) {
   let node = new this.Node(data);

   //检查树是否为空
   if (this.root === null) {
      //插入为第一个元素
      this.root = node;
   } else {
      insertRecHelper(this.root, node);
   }
}
searchIter(data) {
   let currNode = this.root;

   while (currNode !== null) {
      if (currNode.data === data) {

      //找到了元素！
      return true;
   } else if (data < currNode.data) {

      //向左移动，因为数据小于父级
      currNode = currNode.left;
   } else {

      //向右移动，因为数据大于父级
      currNode = currNode.right;
   }
}
return false;
}
searchRec(data) {
   return searchRecHelper(data, this.root);
}
getMinVal() {
   if (this.root === null) {
   throw "空树！";
}
let currNode = this.root;

while (currNode.left !== null) {
      currNode = currNode.left;
   }
return currNode.data;
}
getMaxVal() {
   if (this.root === null) {
      throw "空树！";
   }
   let currNode = this.root;

   while (currNode.right !== null) {
      currNode = currNode.right;
   }
   return currNode.data;
}
deleteNode(key) {
   return !(deleteNodeHelper(this.root, key) === false);
}
inOrder() {
   inOrderHelper(this.root);
}
preOrder() {
   preOrderHelper(this.root);
}
postOrder() {
   postOrderHelper(this.root);
}
}

BinarySearchTree.prototype.Node = class {
   constructor(data, left = null, right = null) {
      this.data = data;
      this.left = left;
      this.right = right;
   }
};

//帮助方法
function preOrderHelper(root) {
   if (root !== null) {
      console.log(root.data);
      preOrderHelper(root.left);
      preOrderHelper(root.right);
   }
}
function inOrderHelper(root) {
   if (root !== null) {
      inOrderHelper(root.left);
      console.log(root.data);
      inOrderHelper(root.right);
   }
}

function postOrderHelper(root) {
   if (root !== null) {
      postOrderHelper(root.left);
      postOrderHelper(root.right);
   console.log(root.data);
   }
}

function insertRecHelper(root, node) {
   if (node.data < root.data) {

      //到达叶节点后，在此处设置值
      if (root.left === null) {
         root.left = node;
      } else {
         insertRecHelper(root.left, node);
      }
   } else {
      //到达叶节点后，在此处设置值
      if (root.right === null) {
         root.right = node;
      } else {
         insertRecHelper(root.right, node);
      }
   }
}

function searchRecHelper(data, root) {
   if (root === null) {
      //到达叶子但没有找到它。
      return false;
   }
   if (data < root.data) {
      return searchRecHelper(data, root.left);
} else if (data > root.data) {
      return searchRecHelper(data, root.right);
   }
   //这意味着找到的元素返回true；否则，返回true。
}

/**
* Takes root and key and recursively searches for the key.
* If it finds the key, there could be 3 cases:
*
* 1. This node is a leaf node. *
* Example: Removing F
* A
* / \
* B C
* / / \
* D E F
*
* To remove it, we can simply remove its parent's connection to it.
*
* A
* / \
* B C
* / /
* D E
*
* 2. This node is in between the tree somewhere with one child.
*
* Example: Removing B
* A
* / \
* B C
* / / \
* D E F
*
* To remove it, we can simply make the child node replace the parent node in the above connection
* A
* / \
* D C
* / \
* E F
*
* 3. This node has both children. This is a tricky case.
*
* Example: Removing C *
* A
* / \
* B C
* / / \
* D E F
* / / \
* G H I
*
* In this case, we need to find either a successor or a predecessor of the node and replace this node with
* that. For example, If we go with the successor, its successor will be the element just greater than it,
* ie, the min element in the right subtree. So after deletion, the tree would look like:
*
* A
* / \
* B H
* / / \
* D E F
* / \
* G I
*
* To remove this element, we need to find the parent of the successor, break their link, make successor's left
* and right point to current node's left and right. The easier way is to just replace the data from node to be
* deleted with successor and delete the sucessor.
*/

function deleteNodeHelper(root, key) {
if (root === null) {
//空树返回false；
}

if (key < root.data) {
root.left = deleteNodeHelper(root.left, key);
return root;
} else if (key > root.data) {
root.right = deleteNodeHelper(root.right, key);
return root;
} else {
//没有孩子
//情况1-叶子节点
if (root.left === null && root.right === null) {
root = null;
return root;
}

//独生子女案件
if (root.left === null) return root.right;
if (root.right === null) return root.left;

//两个孩子，所以需要找到继任者
let currNode = root.right;

while (currNode.left !== null) {
currNode = currNode.left;
} root.data = currNode.data;

//从右子树中删除该值。
root.right = deleteNodeHelper(root.right, currNode.data);
return root;
}
}