importComparatorfrom'../utils/Comparator.js';importHashTablefrom'../hash-table/HashTable.js';exportdefaultclassBinaryTreeNode{constructor(value=null){this.left=null;this.right=null;this.parent=null;this.value=value;this.nodeComparator=newComparator();this.meta=newHashTable();}/** * 左视高 * @return {number} */getleftHeight(){if(!this.left){return0;}returnthis.left.height+1;}/** * 右视高 * @return {number} */getrightHeight(){if(!this.right){return0;}returnthis.right.height+1;}/** * @return {number} */getheight(){returnMath.max(this.leftHeight,this.rightHeight);}/** * 平衡因子: 某个结点的左子树的高度减去右子树的高度得到的差值。 * in AVL Tree * @return {number} */getbalanceFactor(){returnthis.leftHeight-this.rightHeight;}/** * Get parent's sibling if it exists. * @return {BinaryTreeNode} */getuncle(){if(!this.parent){returnnull;}if(!this.parent.parent){returnnull;}if(this.nodeComparator.equal(this.parent.parent.left,this.parent)){returnthis.parent.parent.right;}if(this.nodeComparator.equal(this.parent.parent.right,this.parent)){returnthis.parent.parent.left;}}/** * @param {BinaryTreeNode} sourceNode * @param {BinaryTreeNode} targetNode */staticcopyNode(sourceNode,targetNode){targetNode.value=sourceNode.value;targetNode.setLeft(sourceNode.left);targetNode.setRight(sourceNode.right);}setLeft(node){// Reset parent for left node since it is going to be detached.if(this.left){this.left.parent=null;}// Attach new node to the left.this.left=node;// Make current node to be a parent for new left one.if(this.left){this.left.parent=this;}returnthis;}setRight(node){if(this.right){this.right.parent=null;}this.right=node;if(this.right){this.right.parent=this;}returnthis;}/** * @param {BinaryTreeNode} nodeToRemove * @return {boolean} */removeChild(nodeToRemove){if(this.left&&this.nodeComparator.equal(this.left,nodeToRemove)){this.left=null;nodeToRemove.parent=null;returntrue;}if(this.right&&this.nodeComparator.equal(this.right,nodeToRemove)){this.right=null;nodeToRemove.parent=null;returntrue;}returnfalse;}/** * @param {BinaryTreeNode} nodeToReplace * @param {BinaryTreeNode} replacementNode * @return {boolean} */replaceChild(nodeToReplace,replacementNode){if(!nodeToReplace||!replacementNode){returnfalse;}if(this.left&&this.nodeComparator.equal(this.left,nodeToReplace)){this.left=replacementNode;replacementNode.parent=this;nodeToReplace.parent=null;returntrue;}if(this.right&&this.nodeComparator.equal(this.right,nodeToReplace)){this.right=replacementNode;replacementNode.parent=this;nodeToReplace.parent=null;returntrue;}returnfalse;}/** * 中序遍历(inorder) * 即 left -> root -> right * @return {*[]} */traverseInOrder(){lettraverse=[];// 左if(this.left){traverse=traverse.concat(this.left.traverseInOrder());}// 中traverse.push(this.value);// 右if(this.right){traverse=traverse.concat(this.right.traverseInOrder());}returntraverse;}/** * 先序遍历(preorder) * 即 root -> left -> right * @return {*[]} */traversePreOrder(){}/** * 后序遍历(postorder) * 即 left -> right -> root * @return {*[]} */traversePostOrder(){}toString(){returnthis.traverseInOrder().toString();}}
importBinaryTreeNodefrom'../BinaryTreeNode.js';importComparatorfrom'../../utils/Comparator.js';exportdefaultclassBinarySearchTreeNodeextendsBinaryTreeNode{constructor(value=null,compareFunction=undefined){super(value);// This comparator is used to compare node values with each other.this.compareFunction=compareFunction;this.nodeValueComparator=newComparator(compareFunction);}/** * @param {*} value * @return {BinarySearchTreeNode} */insert(value){if(this.nodeValueComparator.equal(this.value,null)){// Insert root nodethis.value=value;returnthis;}if(this.nodeValueComparator.lessThan(value,this.value)){// Insert to the left.if(this.left){returnthis.left.insert(value);}constnewNode=newBinarySearchTreeNode(value,this.compareFunction);this.setLeft(newNode);returnnewNode;}if(this.nodeValueComparator.greaterThan(value,this.value)){// Insert to the right.if(this.right){returnthis.right.insert(value);}constnewNode=newBinarySearchTreeNode(value,this.compareFunction);this.setRight(newNode);returnnewNode;}}/** * @param {*} value * @return {BinarySearchTreeNode} */find(value){if(this.nodeValueComparator.equal(value,this.value)){returnthis;}if(this.nodeValueComparator.lessThan(value,this.value)&&this.left){returnthis.left.find(value);}if(this.nodeValueComparator.greaterThan(value,this.value)&&this.right){returnthis.right.find(value)}returnnull;}/** * @param {*} value * @return {boolean} */contains(value){return!!this.find(value);}/** * 1. 若为叶节点,即无孩子,其父指向它的指针设为 null; * 2. 若一个孩子,其父指向它的指针改指向其孩子; * 3. 若俩孩子,首先,要么找到其左子树的最大值,要么找到其右子树的最小值。 * 本文采用后者,后续步骤转到4; * 4. 将该节点值替换为最小值,`递归地删除`右子树中最小值节点。 * * @param {*} value * @return {boolean} */remove(value){constnodeToRemove=this.find(value);if(!nodeToRemove){thrownewError('找不到节点 In the tree');}const{parent}=nodeToRemove;if(!nodeToRemove.left&&!nodeToRemove.right){// 1. 无孩子:Node is leaf & has no childif(parent){parent.removeChild(nodeToRemove);}else{nodeToRemove.value=undefined;}returntrue;}elseif(!nodeToRemove.left||!nodeToRemove.right){// 2. 只有一个:孩子Node has only one childconstchildNode=nodeToRemove.left||nodeToRemove.right;if(parent){parent.replaceChild(nodeToRemove,childNode);}else{BinaryTreeNode.copyNode(childNode,nodeToRemove);// 根节点}}else{// 3. 有两个孩子:Node has two childrenconstnextBiggerNode=nodeToRemove.right.findMin();if(this.nodeComparator.equal(nextBiggerNode,nodeToRemove.right)){nodeToRemove.value=nodeToRemove.right.value;nodeToRemove.setRight(nodeToRemove.right.right);}else{// 这里递归this.remove(nextBiggerNode.value);nodeToRemove.value=nextBiggerNode.value;}}nodeToRemove.parent=null;returntrue;}/** * @return {BinarySearchTreeNode} */findMin(){if(!this.left){returnthis;}returnthis.left.findMin();}}
importBinarySearchTreeNodefrom'./BinarySearchTreeNode.js';/** * 二叉查找树(BST) * “A binary search tree is a binary tree in * which data with lesser values are stored in left nodes * and data with greater values are stored in right nodes.” */exportdefaultclassBinarySearchTree{constructor(nodeValueCompareFunction){this.root=newBinarySearchTreeNode(null,nodeValueCompareFunction);this.nodeValueComparator=this.root.nodeValueComparator;}insert(value){returnthis.root.insert(value);}remove(value){returnthis.root.remove(value);}toString(){returnthis.root.toString();}/** * Traverse by level * @param {BinarySearchTreeNode} node * @param {Function} visit * @return {*[]} */bfs(node,visit){constqueue=[];queue.push(node);while(queue.length){consthead=queue.shift();visit&&visit(head);if(head.left){queue.push(head.left);}if(head.right){queue.push(head.right);}}}print(){this.bfs(this.root,node=>{if(node.height>0){constnodeVal=`${node.value}(${node.meta.get('color')})`;constleftVal=node.left?`${node.left.value}(${node.left.meta.get('color')})`:'NIL';constrightVal=node.right?`${node.right.value}(${node.right.meta.get('color')})`:'NIL';console.log(`${nodeVal} -> ${leftVal} | ${rightVal}`);}});}}