<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8" />
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<title>封装二叉搜索树</title>
</head>
<body>
<script>
function BinarySearchTree() {
function Node(key) {
this.key = null;
this.left = null;
this.right - null;
}
this.root = null;
BinarySearchTree.prototype.insert = function (key) {
var newNode = new Node(key);
//判断节点是否有值
if (this.root == null) {
this.root = newNode;
} else {
this.insertNode(this.root, newNode);
}
};
BinarySearchTree.prototype.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);
}
}
};
//先序遍历
BinarySearchTree.prototype.preOrderTraversal = function (handler) {
this.preOrderTraversalNode(this.root, handler);
};
BinarySearchTree.prototype.preOrderTraversalNode = function (
node,
handler
) {
if (node != null) {
//处理经过的节点
handler(node.key);
this.preOrderTraversalNode(node.left, handler);
this.preOrderTraversalNode(node.right, handler);
}
};
//中序遍历
BinarySearchTree.prototype.middleOrderTraversal = function (handler) {
this.middleOrderTraversalNode(this.root, handler);
};
BinarySearchTree.prototype.middleOrderTraversalNode = function (
node,
handler
) {
if (node != null) {
//处理经过的节点
handler(node.key);
this.preOrderTraversalNode(node.left, handler);
handler(node.key)
this.preOrderTraversalNode(node.right, handler);
}
};
//中序遍历
BinarySearchTree.prototype.postOrderTraversal = function (handler) {
this.postOrderTraversalNode(this.root, handler);
};
BinarySearchTree.prototype.postOrderTraversalNode = function (
node,
handler
) {
if (node != null) {
//处理经过的节点
handler(node.key);
this.postOrderTraversalNode(node.left, handler);
this.postOrderTraversalNode(node.right, handler);
handler(node.key)
}
};
BinarySearchTree.prototype.max = function (){
var node=this.root
var key=null
while(node!=null){
key=node.key
node=node.right
}
return key
}
BinarySearchTree.prototype.min = function (){
var node=this.root
var key=null
while(node!=null){
key=node.key
node=node.left
}
return key
}
BinarySearchTree.prototype.search = function (){
var node=this.root
while(node!=key){
if(key<node.key){
node=node.left
}else if(key>node.key){
node=node.key
}else{
return true
}
}
return false
}
BinarySearchTree.prototype.remove = function (key){
//
var current=this.root
var parent=null
var 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
}
//
if(current.left==null&¤t.right==null){
if(current==this.root){
this.root=null
}else if(isLeftChild){
parent.left=null
}else{
parent.right=null
}
}
}
}
</script>
</body>
</html>