// 封装二叉搜索树
function binarySerchTree() {
// 定义属性
this.root = null
// 封装内部类
function node(key) {
this.key = key
this.left = null
this.right = null
}
// 插入操作
this.insert = function (key) {
const newNode = new node(key)
if (this.root === null) {
this.root = newNode
} else {
this.insertNode(this.root, newNode)
}
}
// 内部递归 递归需要把已存在的节点node和新节点newNode 和进行比较 所以需要两个参数
this.insertNode = function (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)
}
}
}
// 先序遍历
// 思路：一共需要两个递归函数，通过两个递归函数的出栈回退 完成所有遍历
// 1、先访问根节点，根节点如果为空，直接返回null
// 2、根节点不为空，先访问根节点的左子树，利用递归函数遍历左节点，直到把所有的左节点遍历完；
// 3、然后再利用递归函数遍历右节点，通过遍历完成后的一次次回退遍历完整个二叉树
this.preOrderTraversal = function () {
this.preOrderTraversalNode(this.root)
}
this.resArr = []
// 先序遍历的递归封装
this.preOrderTraversalNode = function (node) {
if (!node) return null
// 把经历的节点放到数组中
this.resArr.push(node.key)
// 继续处理经过节点的子节点
this.preOrderTraversalNode(node.left)
// 一旦遍历到最后左子节点为空了 返回了一个null 马上进行前一个函数的回调，继续往下走。
//判断经过节点的右子节点是否为空，不为空继续遍历右节点
this.preOrderTraversalNode(node.right)
}
// 中序遍历 从根节点的左子树的最左节点开始遍历， 依次遍历左子节点，左子节点的根节点，右子节点， 依次回退 依次遍历，最后访问右子树的最右节点
// 后序遍历 先遍历左子节点，在遍历右子节点，在遍历两个子节点的根节点， 依次回退 依次遍历， 最后访问根节点
// 获取二叉树的最小值/最小值 道理相同
// 思路：1、中序遍历数组的第一个值和最后一个值
// 2、
this.min = function () {
let node = this.root
if (!node) return null
let key = null
while (node) {
key = node.key
node = node.left
}
return key
}
// 搜索二叉树中特定的值，是否存在
this.serch = function (key) {
return this.serchNode(this.root, key)
}
this.serchNode = function (node, key) {
if (!node) return false
// 往左一个个遍历 直到查找到newNode.key =某个key为止
if (key < node.key) {
node = node.left
return this.serchNode(node, key) //1、上下文的return的作用是如果没找到就继续执行递归函数 直到返回true或者node为null为止
} else if (key > node.key) { //2、为什么这么做？ 因为key的大小要不就大于 要不就小于 要不就等于 ， 如果小于就只遍历左子树，直到为null都没有就返回false，不进行下面操作了
node = node.right
return this.serchNode(node, key)
} else {
return true
}
}
// 1、先遍历查找到要删除的节点，遍历到找到为止;
// 2、三种情况
this.remove = function (key) {
let current = this.root
// 到时候删除节点需要一个被删除节点的父节点
let parent = null
// 删除节点的时候需要判断他是被删除节点的左子节点还是右子节点
let isLeftChild = true
while (current.key === key) {
// 判断是往哪边找
if (key < current.key) {
isLeftChild = true
current = current.left //此时current的值是在不断变化的 直到相等为止
} else {
isLeftChild = false
current = current.right
}
if (current === null) return false //如果遍历完之后都没有找到，就返回null
}
// 找到目标节点current 进行删除操作
// 情况1 删除节点是有叶子节点
if (current.left === null && current.right === null) {
// 删除节点是否是根节点且是叶子节点
if (current === this.root) {
this.root = null
return true
}
isLeftChild ? parent.left = null : parent.right = null
}
// 情况2 删除节点有一个子节点。爷儿孙，删除儿，让爷连孙。 首先判断是儿子current是爷爷parent的左子节点 还是右子节点 再判断孙子节点是儿子节点的哪个子节点
else if (isLeftChild) {
// 根的情况
if (current === this.root) {
this.root = current.left
} else if (!current.right) {
parent.left = current.left
} else {
parent.right = current.left
}
} else if (!isLeftChild) {
if (current === this.root) {
this.root = current.right
} else if (!current.left) {
parent.left = current.right
} else {
parent.right = current.right
}
}
// 情况3 删除节点有两个子节点
}
}
总结：
1、先序遍历，左递归函数在出栈时，会继续执行右递归函数来判断该节点的右子节点是否为空；要确保两个子节点都为空再进行处理以及出栈
2、中序遍历从最左子节点开始处理，中途返回根节点，再遍历右子树
3、后序遍历是从最左子节点开始，再遍历该节点的右自己点，再遍历自己。左右自的顺序 ，依次处理 最后返回根节点
4、在二叉搜索树种查找特定的值，利用递归，进行左右左右的重复比较(node的值在不断变化，每次比较的时候都可能走到不同的条件中去，保证全部遍历)，直到找到为止；如果遍历完成node=null时还没找到，就返回false
5、二叉搜索树的删除，需要定义三个属性(isLeftchild)方便查询爷、儿、孙的左右子节点关系，关系到爷的左还是右连儿的左还是右
