<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>二叉树算法</title>
<script type="text/javascript">
window.onload = function ) {
function Nodedata, left, right) {
this.data = data;
this.left = left;
this.right = right;
}
Node.prototype.show = function) {
return this.data;
}
//建立一个二叉树
function BST) {
this.root = null;
}
//二叉树的插入操作
BST.prototype.insert = functiondata) {
var n = new Nodedata, null, null);
ifthis.root === null) {
this.root = n;
}else {
var current = this.root;
var parent;
whiletrue) {
parent = current;
ifdata < current.data) {
current = current.left;
ifcurrent === null) {
parent.left = n;
break;
}
}else {
current = current.right;
ifcurrent === null) {
parent.right = n;
break;
}
}
}
}
}
//二叉树的历遍操作
BST.prototype.inOrder = functionnode) {
if!node === null)) {
this.inOrdernode.left);
console.lognode.show));
this.inOrdernode.right);
}
}//中序历遍
BST.prototype.preOrder = functionnode) {
if!node === null)) {
console.lognode.show));
this.inOrdernode.left);
this.inOrdernode.right);
}
}//先序历遍
BST.prototype.postOrder = functionnode) {
if!node === null)) {
this.inOrdernode.left);
this.inOrdernode.right);
console.lognode.show));
}
}//后序历遍
BST.prototype.getMin = function) {
var current = this.root;
while!current.left === null)) {
current = current.left;
}
return current.data;
}//获取最小值
BST.prototype.getMax = function) {
var current = this.root;
while!current.right === null)) {
current = current.right;
}
return current.data;
}//获取最大值
BST.prototype.find = functiondata) {
var current = this.root;
whilecurrent !== null) {
ifcurrent.data === data) {
return current.data;
}else ifdata < current.data) {
current = current.left;
}else {
current = current.right;
}
}
return null;
}//查找节点
BST.prototype.getSmallest = functionnode) {
if node.left == null) {
return node;
}
else {
return this.getSmallestnode.left);
}
}
//删除一个节点，需要传入一个root节点根节点)
BST.prototype.remove = functionnode, data) {
ifnode === null) {
return null;
}
ifdata == node.data) {
ifnode.left === null && node.right === null) {
return null;
}
ifnode.left === null) {
return node.right;
}
ifnode.right === null) {
return node.left;
}
var tempNode = this.getSmallestnode.right);
node.data = tempNode.data;
node.right = removenode.right, tempNode.data);
return node;
}else ifdata < node.data) {
node.left = this.removenode.left, data);
return node;
}else {
node.right = this.removenode.right, data);
return node;
}
}
var num = new BST);
num.insert23);
num.insert45);
num.insert16);
num.insert37);
num.insert3);
num.insert99);
num.insert22);
//console.lognum.root);
//num.inOrdernum.root);
//console.lognum.getMin));
//console.lognum.getMax));
num.inOrdernum.root);
console.lognum.removenum.root,37));
num.inOrdernum.root);
}
</script>
</head>
<body>
</body>
</html>
