① 二叉树定义
② 二叉排序树
③ 二叉平衡树

## ② 二叉排序树

(1) 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值
(2) 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值
(3) 它的左、右子树也分别为二叉查找树
Javascript实现

function BinarySearchTree(keys){
//Node构造函数
let Node = function (key){
this.key = key
this.left = null
this.right = null
}
let root = null
let insertNode = (node,newNode)=>{
if(newNode.key < node.key){
if(node.left === null){
node.left = newNode
}else {
insertNode(node.left,newNode)
}
}else {
if (node.right === null) {
node.right = newNode
}else {
insertNode(node.right,newNode)
}
}
}
this.insert = (key)=>{
let newNode = new Node(key)
if (root === null) {
root = newNode
}else {
insertNode(root,newNode)
}
}
keys.forEach((key)=>{
this.insert(key)
})
return root
}
const keys = [8,3,10,1,6,14,4,7,13]
BinarySearchTree(keys)

chrome中打印如下：

let inOrderTraverseFunction =(node,cb)=>{
if(node!==null){
inOrderTraverseFunction(node.left,cb)
cb(node.key)
inOrderTraverseFunction(node.right,cb)
}
}
let callback =(key)=>{
console.log(key)
}
//BST的中序遍历
inOrderTraverseFunction(BinarySearchTree(keys),callback)

chrome中打印如下：

let preOrderTraverseFunction =(node,cb)=>{
if(node!==null){
cb(node.key)
preOrderTraverseFunction(node.left,cb)
preOrderTraverseFunction(node.right,cb)
}
}
//BST前序遍历
preOrderTraverseFunction(BinarySearchTree(keys),callback)

chrome打印如下

let postOrderTraverseFunction =(node,cb)=>{
if(node!==null){
postOrderTraverseFunction(node.left,cb)
postOrderTraverseFunction(node.right,cb)
cb(node.key)
}
}
//BST后序遍历
postOrderTraverseFunction(BinarySearchTree(keys),callback)

chrome打印如下

let minNode =(node)=>{
if(node){
while (node&&node.left !== null){
node = node.left
}
return node.key
}
return null
}
//查找BST最小值
console.log('the min node is '+minNode(BinarySearchTree(keys)))

chrome打印如下

let maxNode =(node)=>{
if(node){
while (node&&node.right !== null){
node = node.right
}
return node.key
}
return null
}
//查找BST最大值
console.log('the max node is '+maxNode(BinarySearchTree(keys)))

chrome打印如下

let searchNode = (node,key)=>{
if(node === null){
return false
}
if(key<node.key){
return searchNode(node.left,key)
}else if (key>node.key) {
return searchNode(node.right,key)
}else{
return true
}
}
//BST查找某个值

chrome打印如下:

let removeNode = (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
}
}
}
//BST删除某个叶子节点
console.log(removeNode(BinarySearchTree(keys),1),BinarySearchTree(keys))

chrome打印如下:

let removeNode = (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
}
if(node.left === null){
node = node.right
return node
}else if (node.right === null) {
node = node.left
return node
}
}
}
//BST删除某个度为1的子节点
console.log(removeNode(BinarySearchTree(keys),10),BinarySearchTree(keys))

chrome打印如下:

let findMinNode = (node) =>{
if(node){
while(node&& node.left !== null){
node = node.left
}
return node
}
return null
}
let removeNode = (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
}
if(node.left === null){
node = node.right
return node
}else if (node.right === null) {
node = node.left
return node
}
let minNode = findMinNode(node.right)
node.key = minNode.key
node.right = removeNode(node.right,minNode.key)
return node
}
}
//BST删除某个度为2的子节点
console.log(removeNode(BinarySearchTree(keys),3),BinarySearchTree(keys))

chrome打印如下: