1 二叉搜索树
function BinarySearchTree(){
// 初始化节点
var Node = function(key){
this.key = key
this.left = null
this.right = null
}
// 初始化root
let root = null
this.insert = function (key) {
let newNode = new Node(key)
if(root === null){
root = newNode
} else {
// 如果root有值，则试着插入他的子节点
insertNode(root, newNode)
}
}
function insertNode(f,s) {
if (s.key<f.key) {
if (!f.left) {
f.left = s
} else {
insertNode(f.left, s)
}
}else{
if (!f.right) {
f.right = s
} else {
insertNode(f.right, s)
}
}
}
this.getRoot = function(){
console.log(root)
}
}
var tree = new BinarySearchTree()
tree.insert(11)
tree.insert(7)
tree.insert(15)
tree.insert(5)
tree.insert(3)
tree.insert(9)
tree.insert(8)
tree.insert(10)
tree.insert(13)
tree.insert(12)
tree.insert(14)
tree.insert(20)
tree.insert(18)
tree.insert(25)
tree.getRoot()
2 遍历
2.1 中序遍历
概念:是一种以上行顺序访问BST所有节点的遍历方式，也就是以从最小到最大的顺序访问所有节点。
function printNode(value) {
console.log(value)
}
---BST内部---
this.inOrderTraverse = function (callback) {
inOrderTraverseNode(root,callback)
}
inOrderTraverseNode = function (node, callback) {
if (node !== null) {
console.log('top', node.key)
inOrderTraverseNode(node.left, callback)//
callback(node.key) //
inOrderTraverseNode(node.right, callback)//
console.log('bottom', node.key)
}
}
1,第一步:
会一直向左寻找 11 7 5 3
找到node.key === 3后递归结束,执行当前函数的剩余代码
3没有right当前函数执行结束
2,第二步
执行5剩余的代码
输出5
node.key === 5
function BinarySearchTree(){
// 节点
var Node = function(key){
this.key = key
this.left = null
this.right = null
}
let root = null
this.insert = function (key) {
let newNode = new Node(key)
if(root === null){
root = newNode
} else {
insertNode(root, newNode)
}
}
this.inOrderTraverse = function (callback) {
inOrderTraverseNode(root,callback)
}
inOrderTraverseNode = function (node, callback) {
if (node !== null) {
console.log('top', node.key)
inOrderTraverseNode(node.left, callback)// 会一直向左寻找 11 7 5 3
callback(node.key) // 找到3后递归结束,执行当前函数的剩余代码
inOrderTraverseNode(node.right, callback)// 3没有没有right当前函数执行结束
console.log('bottom', node.key)
}
}
function insertNode(f,s) {
if (s.key<f.key) {
if (!f.left) {
f.left = s
} else {
insertNode(f.left, s)
}
}else{
if (!f.right) {
f.right = s
} else {
insertNode(f.right, s)
}
}
}
this.getRoot = function(){
console.log(root)
}
}
// 中序遍历
function printNode(value) {
console.log(value)
}
var tree = new BinarySearchTree()
tree.insert(11)
tree.insert(7)
tree.insert(15)
tree.insert(5)
tree.insert(3)
tree.insert(9)
tree.insert(8)
tree.insert(10)
tree.insert(13)
tree.insert(12)
tree.insert(14)
tree.insert(20)
tree.insert(18)
tree.insert(25)
tree.insert(6)
tree.inOrderTraverse(printNode)
2.1先序遍历
概念：先访问节点本身，然后再会访问左侧子节点，最后是右侧节点。
preOrderTraverseNode = function (node, callback) {
if (node !== null) {
callback(node.key)
preOrderTraverseNode(node.left, callback)
preOrderTraverseNode(node.right, callback)
}
}
2.3 后序遍历
概念：先访问节点的后代节点，再访问节点。
应用：计算目录和子目录所有文件所占空间的大小
postOrderTraverseNode = function (node, callback) {
if (node !== null) {
postTraverseNode(node.left, callback)
postOrderTraverseNode(node.right, callback)
callback(node.key)
}
}
第一步:
从root ===11开始
一直执行post(node.left)直到执行到node.key ===3 print：3
在5的环境下，向下执行代码，print: 6
print 5，退出5的环境
第二步
node.left.key ===5
执行node.right.key===9
print的顺序与第一步类似
print: 8 10 9
第三步
print 7
第四步
类似于第二步
print: 12 14 13 18 25 20 15
所以总的是
3 6 5 8 10 9 12 14 13 18 25 20 15 11
3 搜索树中的值
3.1搜索最大值
// 最小值
this.min = function(){
return minNode(root)
}
function minNode(node){
if(node){
while(node.left!==null){
node = node.left
}
return node.key
}
return null
}
3.2搜索最小值
// 最大值
this.max = function(){
return maxNode(root)
}
function maxNode(node){
if(node){
while(node.right!==null){
node = node.right
}
return node.key
}
return null
}
3.3搜索特定值
// 和has 方法类似
this.search = function(key){
return searchNode(root,key)
}
function searchNode(node,key){
if (node === null) {
return false
}
if (node.key>key) {
return searchNode(node.left,key)
} else if(node.key<key) {
return searchNode(node.right,key)
} else {
return true
}
}
console.log(tree.search(100))
分析：
1 root.key ===11 , key ===100
searchNode(node.right.key=15,100)
100与node.key的关系只会是三种大于，小于或者等于
node.key<100 右边找 return search(node.right)// 不管存在不存先赋值了再说，如果node.right === null则搜索结束，不为null可能进行与之前一样的判断，一直找到最后一个node.left或者right实际是不存在的。
node.key>100 左边找 return search(node.left)//左边的也是类似
以上两种都不是则node.key ===100
console.log(tree.search(1))
console.log(tree.search(9))
4 移除某个节点
this.remove = function(key){
root = removeNode(root,key)
}
var removeNode = function(node,key){
if(node === null){
return null
}
if(key<node.key){
node.left = removeNode(node.left,key)
return node
}else if(key>node.key){
node.right = removeNode(node.right,key)
return node
}else{
// 第一种情况 一个叶节点
if(node.left === null&& node.right === null){
node = null
return node
// 第二种情况 一个只有一个子节点的节点
}else if(node.left === null){
node = node.right
return node
}else if(node.right === null){
node = node.left
return node
}
// 第三种情况 一个有两个子节点的节点
var aux = (function findMinNode(node){
while(node&&node.left!==null){
node = node.left
}
return node
})(node.right)
node.key = aux.key
node.right = removeNode(node.right,aux.right)
return node
}
}
分析：
情况1:tree.remove(3)
root = removeNode(root,3)
进入key<node.key的条件里面
node.left = removeNode(,3)
