|
Struts example source code file (BinaryTree.js)
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}; Other Struts examples (source code examples)Here is a short list of links related to this Struts BinaryTree.js source code file: |
... this post is sponsored by my books ... | |
#1 New Release! |
FP Best Seller |
Copyright 1998-2021 Alvin Alexander, alvinalexander.com
All Rights Reserved.
A percentage of advertising revenue from
pages under the /java/jwarehouse
URI on this website is
paid back to open source projects.