New file |
0,0 → 1,255 |
/* |
Copyright (c) 2004-2006, The Dojo Foundation |
All Rights Reserved. |
|
Licensed under the Academic Free License version 2.1 or above OR the |
modified BSD license. For more information on Dojo licensing, see: |
|
http://dojotoolkit.org/community/licensing.shtml |
*/ |
|
dojo.provide("dojo.collections.BinaryTree"); |
dojo.require("dojo.collections.Collections"); |
dojo.require("dojo.experimental"); |
dojo.experimental("dojo.collections.BinaryTree"); |
dojo.collections.BinaryTree = function (data) { |
function node(data, rnode, lnode) { |
this.value = data || null; |
this.right = rnode || null; |
this.left = lnode || null; |
this.clone = function () { |
var c = new node(); |
if (this.value.value) { |
c.value = this.value.clone(); |
} else { |
c.value = this.value; |
} |
if (this.left) { |
c.left = this.left.clone(); |
} |
if (this.right) { |
c.right = this.right.clone(); |
} |
}; |
this.compare = function (n) { |
if (this.value > n.value) { |
return 1; |
} |
if (this.value < n.value) { |
return -1; |
} |
return 0; |
}; |
this.compareData = function (d) { |
if (this.value > d) { |
return 1; |
} |
if (this.value < d) { |
return -1; |
} |
return 0; |
}; |
} |
function inorderTraversalBuildup(current, a) { |
if (current) { |
inorderTraversalBuildup(current.left, a); |
a.add(current); |
inorderTraversalBuildup(current.right, a); |
} |
} |
function preorderTraversal(current, sep) { |
var s = ""; |
if (current) { |
s = current.value.toString() + sep; |
s += preorderTraversal(current.left, sep); |
s += preorderTraversal(current.right, sep); |
} |
return s; |
} |
function inorderTraversal(current, sep) { |
var s = ""; |
if (current) { |
s = inorderTraversal(current.left, sep); |
s += current.value.toString() + sep; |
s += inorderTraversal(current.right, sep); |
} |
return s; |
} |
function postorderTraversal(current, sep) { |
var s = ""; |
if (current) { |
s = postorderTraversal(current.left, sep); |
s += postorderTraversal(current.right, sep); |
s += current.value.toString() + sep; |
} |
return s; |
} |
function searchHelper(current, data) { |
if (!current) { |
return null; |
} |
var i = current.compareData(data); |
if (i == 0) { |
return current; |
} |
if (i > 0) { |
return searchHelper(current.left, data); |
} else { |
return searchHelper(current.right, data); |
} |
} |
this.add = function (data) { |
var n = new node(data); |
var i; |
var current = root; |
var parent = null; |
while (current) { |
i = current.compare(n); |
if (i == 0) { |
return; |
} |
parent = current; |
if (i > 0) { |
current = current.left; |
} else { |
current = current.right; |
} |
} |
this.count++; |
if (!parent) { |
root = n; |
} else { |
i = parent.compare(n); |
if (i > 0) { |
parent.left = n; |
} else { |
parent.right = n; |
} |
} |
}; |
this.clear = function () { |
root = null; |
this.count = 0; |
}; |
this.clone = function () { |
var c = new dojo.collections.BinaryTree(); |
c.root = root.clone(); |
c.count = this.count; |
return c; |
}; |
this.contains = function (data) { |
return this.search(data) != null; |
}; |
this.deleteData = function (data) { |
var current = root; |
var parent = null; |
var i = current.compareData(data); |
while (i != 0 && current != null) { |
if (i > 0) { |
parent = current; |
current = current.left; |
} else { |
if (i < 0) { |
parent = current; |
current = current.right; |
} |
} |
i = current.compareData(data); |
} |
if (!current) { |
return; |
} |
this.count--; |
if (!current.right) { |
if (!parent) { |
root = current.left; |
} else { |
i = parent.compare(current); |
if (i > 0) { |
parent.left = current.left; |
} else { |
if (i < 0) { |
parent.right = current.left; |
} |
} |
} |
} else { |
if (!current.right.left) { |
if (!parent) { |
root = current.right; |
} else { |
i = parent.compare(current); |
if (i > 0) { |
parent.left = current.right; |
} else { |
if (i < 0) { |
parent.right = current.right; |
} |
} |
} |
} else { |
var leftmost = current.right.left; |
var lmParent = current.right; |
while (leftmost.left != null) { |
lmParent = leftmost; |
leftmost = leftmost.left; |
} |
lmParent.left = leftmost.right; |
leftmost.left = current.left; |
leftmost.right = current.right; |
if (!parent) { |
root = leftmost; |
} else { |
i = parent.compare(current); |
if (i > 0) { |
parent.left = leftmost; |
} else { |
if (i < 0) { |
parent.right = leftmost; |
} |
} |
} |
} |
} |
}; |
this.getIterator = function () { |
var a = []; |
inorderTraversalBuildup(root, a); |
return new dojo.collections.Iterator(a); |
}; |
this.search = function (data) { |
return searchHelper(root, data); |
}; |
this.toString = function (order, sep) { |
if (!order) { |
var order = dojo.collections.BinaryTree.TraversalMethods.Inorder; |
} |
if (!sep) { |
var sep = " "; |
} |
var s = ""; |
switch (order) { |
case dojo.collections.BinaryTree.TraversalMethods.Preorder: |
s = preorderTraversal(root, sep); |
break; |
case dojo.collections.BinaryTree.TraversalMethods.Inorder: |
s = inorderTraversal(root, sep); |
break; |
case dojo.collections.BinaryTree.TraversalMethods.Postorder: |
s = postorderTraversal(root, sep); |
break; |
} |
if (s.length == 0) { |
return ""; |
} else { |
return s.substring(0, s.length - sep.length); |
} |
}; |
this.count = 0; |
var root = this.root = null; |
if (data) { |
this.add(data); |
} |
}; |
dojo.collections.BinaryTree.TraversalMethods = {Preorder:1, Inorder:2, Postorder:3}; |
|