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