//封装二叉搜索树
function Bintree() {
//节点
function Node(key) {
this.key = key;
this.left = null;
this.right = null;
}
//根节点
this.root = null;
//插入节点
Bintree.prototype.insert = function(key) {
//1.创建新节点
let newNode = new Node(key);
//2.判断是否有根节点
if (this.root == null) {
//2.1让新节点作为根节点
this.root = newNode;
} else {
//2.2调用节点比较插入的函数
this.insertNode(this.root, newNode);
}
}
//内部插入节点算法的函数
this.insertNode = function(node, newNode) {
//1.向右查找(新节点的key值大于当前节点的key值)
if (newNode.key >= node.key) {
//1.1判断当前节点是否存在右孩子节点
if (node.right == null) {
//1.2不存在就直接赋值
node.right = newNode;
} else {
//1.3右孩子节点存在的话就递归调用该函数，将其作为当前节点和新节点继续比较
this.insertNode(node.right, newNode);
}
} else {
//2.向左查找(新节点的key值小于当前节点的key值)
//2.1判断当前节点是否存在左孩子节点
if (node.left == null) {
//2.2不存在就直接赋值
node.left = newNode;
} else {
//2.3左孩子节点存在的话就递归调用该函数，将其作为当前节点和新节点继续比较
this.insertNode(node.left, newNode);
}
}
}
//先序遍历(根 左 右)
Bintree.prototype.preorderTraversal = function(handler) {
this.preorderTraversalNode(this.root, handler)
}
this.preorderTraversalNode = function(node, handler) {
if (node !== null) {
//1.处理经过的节点
handler(node.key)
//2.处理经过节点的左孩子节点
this.preorderTraversalNode(node.left, handler)
//3.处理经过节点的右孩子节点
this.preorderTraversalNode(node.right, handler)
}
}
//中序遍历(左 根 右)
Bintree.prototype.inorderTraversal = function(handler) {
this.inorderTraversalNode(this.root, handler)
}
this.inorderTraversalNode = function(node, handler) {
if (node !== null) {
//1.处理经过节点的左孩子节点
this.inorderTraversalNode(node.left, handler)
//2.处理经过的节点
handler(node.key)
//3.处理经过节点的右孩子节点
this.inorderTraversalNode(node.right, handler)
}
}
//后序遍历(左 右 根)
Bintree.prototype.postorderTraversal = function(handler) {
this.postorderTraversalNode(this.root, handler)
}
this.postorderTraversalNode = function(node, handler) {
if (node !== null) {
//1.处理经过节点的左孩子节点
this.postorderTraversalNode(node.left, handler)
//2.处理经过节点的右孩子节点
this.postorderTraversalNode(node.right, handler)
//3.处理经过的节点
handler(node.key)
}
}
//查找最值
Bintree.prototype.max = function() {
let node = this.root;
let key = null;
while (node !== null) {
key = node.key;
node = node.right;
}
return key;
}
Bintree.prototype.min = function() {
let node = this.root;
let key = null;
while (node !== null) {
key = node.key;
node = node.left;
}
return key;
}
//搜索一个key是否存在
Bintree.prototype.search = function(key) {
let node = this.root;
while (node != null) {
if (key < node.key) {
node = node.left;
} else if (key > node.key) {
node = node.right;
} else {
return true;
}
}
return false;
}
//删除节点
Bintree.prototype.remove = function(key) {
let current = this.root; //要移动的当前节点(去找到要删除的节点)
let parent = null; //当前节点的父节点
let isLeftChild = null; //判断当前节点是左孩子还是右孩子
//1.找到要删除的节点，没有找到就false
while (current.key !== key) {
//1.1向左移动
if (key < current.key) {
parent = current;
current = current.left;
isLeftChild = true;
} else {
//1.2向右移动
parent = current;
current = current.right;
isLeftChild = false;
}
//1.3没有找到要删除的节点
if (current == null) return false;
}
//2.根据对应情况删除节点
//2.1删除的节点没有子节点
if (current.left == null && current.right == null) {
//2.1.1删除的节点是根节点
if (current == this.root) {
this.root = null;
//2.1.2是叶子节点
} else if (isLeftChild) {
parent.left = null;
} else {
parent.right = null;
}
}
//2.2删除的节点只有一个子节点
//2.2.1删除的节点只有左子节点
else if (current.right == null) {
//2.2.1.1删除的节点是根节点
if (current == this.root) {
this.root = current.left;
//2.2.1.2判断删除的节点是父节点的左孩子还是右孩子
} else if (isLeftChild) {
parent.left = current.left;
} else {
parent.right = current.left;
}
//2.2.2删除的节点只有右子节点
} else if (current.left == null) {
if (current == this.root) {
this.root = current.right;
} else if (isLeftChild) {
parent.left = current.right;
} else {
parent.right = current.right;
}
}
//2.3删除的节点有两个子节点
else {
//2.3.1获取后继节点
let successor = this.getSuccessor(current);
//2.3.2如果是根节点
if (this.root == current) {
this.root = successor;
} else if (isLeftChild) {
parent.left = successor;
} else {
parent.right = successor;
}
//因为找的是后继，删除节点的左子树一定都是后继节点的左子树
successor.left = current.left;
}
}
//找后继(删除节点的右子树中最小的节点)的方法
this.getSuccessor = function(delNode) {
let successorParent = delNode; //后继节点的父节点
let successor = delNode; //后继节点
let current = delNode.right; //移动指针
while (current !== null) {
successorParent = successor;
successor = current;
current = current.left;
}
if (successor !== delNode.right) {
successorParent.left = successor.right;
successor.right = delNode.right;
}
return successor;
}
}
// 测试代码
var bst = new Bintree()
// 插入数据
bst.insert(11)
bst.insert(7)
bst.insert(15)
bst.insert(5)
bst.insert(3)
bst.insert(9)
bst.insert(8)
bst.insert(10)
bst.insert(13)
bst.insert(12)
bst.insert(14)
bst.insert(20)
bst.insert(18)
bst.insert(25)
//测试先序遍历
let resultStr = ""
//调用preorderTraversal传入整理输出key的函数
bst.preorderTraversal(function(key) {
resultStr += key + ' '
})
console.log(resultStr);
//测试中序遍历
resultStr = ''
bst.inorderTraversal(function(key) {
resultStr += key + ' '
})
console.log(resultStr);
//测试后序遍历
resultStr = ''
bst.postorderTraversal(function(key) {
resultStr += key + ' '
})
console.log(resultStr);
//测试获取最大值
console.log(bst.max());
//测试搜索key
console.log(bst.search(18));
console.log(bst.search(77));
//测试删除
bst.remove(9)
bst.remove(7)
bst.remove(15)
resultStr = ''
bst.postorderTraversal(function(key) {
resultStr += key + ' '
})
console.log(resultStr);
京公网安备 11010502036488号