Struts example source code file (BinaryTree.js)

This example Struts source code file (BinaryTree.js) is included in the DevDaily.com "Java Source Code Warehouse" project. The intent of this project is to help you "Learn Java by Example" ^TM.

Java - Struts tags/keywords

inorder:2, inorder:2, postorder:3, postorder:3, preorder:1, preorder:1

The Struts BinaryTree.js source code

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