封装：
class Node{
constructor(key,value){
this.key = key;
this.value = value;
this.left = null;
this.right = null;
}
}
class BinarySearchTree{
constructor(){
this.root = null;
}
}
// 插入新节点
insert(key,value){
let newNode = new Node(key,value);
// 判断是否为空树
if(this.root == null){
this.root = newNode;
}else{
BinarySearchTree.insertNode(this.root,newNode);
}
}
static insertNode(node,newNode){
if(newNode.key < node.key){
if(node.left == null){
node.left = newNode;
}else{
this.insertNode(node.left,newNode);
}
}else{
if(node.right == null){
node.right = newNode;
}else{
this.insertNode(node.right,newNode);
}
}
}
// 最小值
min(){
let node = this.root;
if(node == null){
return null;
}
while(node.left !== null){
node = node.left;
}
return {
key:node.key,
value:node.value
}
}
// 最大值
max(){
let node = this.root;
if(node == null){
return null;
}
while(node.right !== null){
node = node.right;
}
return {
key:node.key,
value:node.value
}
}
// 查找
search(key){
return BinarySearchTree.searchNode(this.root,key);
}
static searchNode(node,key){
if(node == null){
return null;
}
if(node.key < key){
return this.searchNode(node.right,key);
}else if(node.key > key){
return this.searchNode(node.left,key);
}else{
return node.value;
}
}
// 更新
update(key,newValue){
return BinarySearchTree.updateNode(this.root,key,newValue);
}
static updateNode(node,key,newValue){
if(node == null){
return false;
}
if(node.key < key){
return this.updateNode(node.right,key,newValue);
}else if(node.key > key){
return this.updateNode(node.left,key,newValue);
}else{
node.value = newValue;
return true;
}
}
// 递归
preOrderTraverse() {
let res = [];
let preOrder = (node)=>{
if (node !== null) {
res.push(node.key);;
preOrder(node.left);
preOrder(node.right);
}
};
preOrder(this.root);
return res;
}
// 非递归，用栈
preOrderTraverse() {
let res = [];
let stack = [this.root];
while(stack.length){
let node = stack.pop();
res.push(node.key);
//这里先放右边再放左边是因为取出来的顺序相反
node.right && stack.push(node.right);
node.left && stack.push(node.left);
}
return res;
}
// 递归
inOrderTraverse() {
let res = [];
let inOrder = (node)=>{
if (node !== null) {
inOrder(node.left);
res.push(node.key);
inOrder(node.right);
}
};
inOrder(this.root);
return res;
}
// 非递归，用栈
inOrderTraverse() {
let stack = [];
let res = [];
let node = this.root;
while(true){
while(node != null){
stack.push(node);
node = node.left;
}
//终止条件：栈为空
if(stack.length == 0){
break;
}
var temp = stack.pop();
res.push(temp.key);
node = temp.right;
}
return res;
}
// 递归
postOrderTraverse() {
let res = [];
let postOrder = (node)=>{
if (node !== null) {
postOrder(node.left);
postOrder(node.right);
res.push(node.key);
}
};
postOrder(this.root);
return res;
}
// 非递归，用栈
postOrderTraverse() {
let res=[];
let stack = [this.root];
while(stack.length){
let node = stack.pop();
res.push(node.key);
node.left && stack.push(node.left);
node.right && stack.push(node.right);
}
return res.reverse();
}
//递归
levelTraverse(){
let res = [];
let stack = [this.root];
let count = 0;
let bfs = ()=>{
let node = stack[count];
if(node){
res.push(node.key);
node.left && stack.push(node.left);
node.right && stack.push(node.right);
count++;
bfs();
}
}
bfs();
return res;
}
// 非递归，使用队列
levelTraverse(){
let res = [];
let queue = [];
queue.push(this.root);
while(queue.length) {
let node = queue.shift();
res.push(node.key);
node.left && queue.push(node.left);
node.right && queue.push(node.right);
}
return res;
}
remove(key){
let current = this.root;
let parent = null;
let isLeftChild = true;
while(current.key !== key){
parent = current;
if(key < current.key){
isLeftChild = true;
current = current.left;
}else{
isLeftChild = false;
current = current.right;
}
if(current == null){
return false;
}
}
// 1.当前节点是叶子节点（子节点为0）
if(current.left == null && current.right == null){
// 树只有根
if(current == this.root){
this.root = null;
}else if(isLeftChild){
parent.left = null;
}else{
parent.right = null;
}
}
// 2.当前节点只有左节点或右节点
else if(current.right == null){
if(current == this.root){
this.root = current.left;
}else if(isLeftChild){
parent.left = current.left;
}else{
parent.right = current.right;
}
}
else if(current.left == null){
if(current == this.root){
this.root = current.right;
}else if(isLeftChild){
parent.left = current.left;
}else{
parent.right = current.right;
}
}
// 当前节点有2个子节点
// 删除节点后，用前驱或者后继替代当前节点
// 前驱：左子树最大值，当前节点小一点的节点
// 后继：右子树最小值，当前节点大一点的节点
else{
let successor = BinarySearchTree.findSuccessor(current);
if(current == this.root){
this.root = successor;
}else if(isLeftChild){
parent.left = successor;
}else{
parent.right = successor;
}
successor.left = current.left;
}
return true;
}
static findSuccessor(node){
let removeNode = node;
let removeNodeParent = node;
let current = node.right;
while(current !== null){
removeNodeParent = removeNode;
removeNode = current;
current = current.left;
}
if(removeNode !== node.right){
removeNodeParent.left = removeNode.right;
removeNode.left = node.right;
}
return removeNode;
}
