| /* |
| 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}; |
| |