binarytree.js

来自「Hippo CMS是一个以信息为中心的开源内容管理系统。Hippo CMS目标是」· JavaScript 代码 · 共 258 行

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