Java/Collections Data Structure/Tree — различия между версиями
Admin (обсуждение | вклад) м (1 версия) |
|
(нет различий)
|
Текущая версия на 10:25, 1 июня 2010
Содержание
- 1 A tree structure that maps inheritance hierarchies of classes
- 2 Binary Tree
- 3 Data structure that mantains data in a ordered binary tree; each node is greater (smaller) or equal than its 2 sub-nodes, for all the hierarchy.
- 4 Tree Node for the for a general tree of Objects
- 5 Your own tree with generic user object
A tree structure that maps inheritance hierarchies of classes
<source lang="java">
/*
* The contents of this file are subject to the Sapient Public License * Version 1.0 (the "License"); you may not use this file except in compliance * with the License. You may obtain a copy of the License at * http://carbon.sf.net/License.html. * * Software distributed under the License is distributed on an "AS IS" basis, * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License for * the specific language governing rights and limitations under the License. * * The Original Code is The Carbon Component Framework. * * The Initial Developer of the Original Code is Sapient Corporation * * Copyright (C) 2003 Sapient Corporation. All Rights Reserved. */
import java.util.ArrayList; import java.util.Collections; import java.util.HashMap; import java.util.List; import java.util.Map;
/**
*This class creates a tree structure that maps inheritance hierarchies of * classes. A developer can place any number of classes into this object and * retrieve the closest super class or the class itself.
* * * Copyright 2001 Sapient * @since EJFW 2.7 * @author Greg Hinkle, January 2001 * @version $Revision: 1.4 $($Author: dvoet $ / $Date: 2003/05/05 21:21:23 $) */
public class ClassTree {
protected ClassTreeNode bottom;
/** * Constructs a ClassTree that represents all classes and interfaces that * are generalizations of the provided class. This ends up with a tree * structure of the inheritance hierarchy for that provided class all the * way up to java.lang.Object. * @param specificClass The class to build the tree for. */ public ClassTree(Class specificClass) { this.bottom = ClassTreeNode.buildNode(specificClass); } public ClassTreeNode getBottom() { return this.bottom; }
/** * Constructs an ordered list starting at the highest (most general) class * in the tree and moving down the tree, ensuring no generalization comes * after one of its specializations. * @return a list ordered as above */ public List getOrderedList() { List list = new ArrayList(); list.add(getBottom()); buildList(getBottom(),list); Collections.sort(list); // Refactor list into a list of classes from a list of ClassTreeNodes for (int i = 0; i < list.size(); i++) { ClassTreeNode node = (ClassTreeNode) list.get(i); list.set(i,node.getObjectClass()); } // Reverse the list so that the top class in the hierarchy comes first Collections.reverse(list); return list; } /***
Build breadth first in order to maintain sudo ordering as per * class declarations (i.e. if A implements B, C... B is closer in the * chain to A than C is, because B comes first in the implements clause.
**
Note that the list coming out here is preordered, but not natural * ordered. (i.e. some classes are out of order in relation to classes * they have direct relationships with. This is later fixed by a sort * on the list by natural ordering. Collecitons.sort, does preserve * the preordering for nodes that have no relationship.
* * @param node the node to be browsed. * @param output this list is altered to add the contents as they are * browsed in breadth-first order. Start with a list containing only * the bottom node. */ private void buildList(ClassTreeNode node, List output) { for (int i = 0; i < node.getParents().size(); i++) { ClassTreeNode parent = (ClassTreeNode) node.getParents().get(i); if (!output.contains(parent)) { output.add(parent); } } List parents = node.getParents(); for (int i = 0; i < parents.size(); i++) { ClassTreeNode parent = (ClassTreeNode) parents.get(i); buildList(parent, output); } }
/***
Inner class representing each node in the tree. Holds references to the * nodes children, parent and provides the Comparable interface for sorting * by inheritance hierarchy.
*/ public static class ClassTreeNode implements Comparable { /** The class of this node */ protected Class objectClass; /** The map of children classes to their class names */ protected List children; /** A reference to the parent node of this node */ protected List parents; /***
Constructs a ClassTreeNode with the given Class.
* * @param objectClass the Class of the node */ public ClassTreeNode(Class objectClass) { this.children = new ArrayList(); this.objectClass = objectClass; this.parents = new ArrayList();
} public static ClassTreeNode buildNode(Class objectClass) { Map allNodes = new HashMap(); return buildNode(objectClass, allNodes); } protected static ClassTreeNode buildNode(Class objectClass, Map allNodes) { ClassTreeNode node; if (allNodes.containsKey(objectClass)) { node = (ClassTreeNode) allNodes.get(objectClass); } else { node = new ClassTreeNode(objectClass); allNodes.put(objectClass, node); } // Add the implemented interfaces... Class[] superInterfaces = objectClass.getInterfaces(); for (int i = 0; i < superInterfaces.length; i++) { Class superInterface = superInterfaces[i]; ClassTreeNode parent = buildNode(superInterface); node.addParent(parent); } // Add the superclass after the interfaces... Class superClass = objectClass.getSuperclass(); if (superClass != null) { ClassTreeNode parent = buildNode(superClass); node.addParent(parent); } return node; }
public List getParents() { return this.parents; } public void addParent(ClassTreeNode node) { this.parents.add(node); node.addChild(this); } public boolean removeChild(ClassTreeNode node) { return this.children.remove(node); } public void addChild(ClassTreeNode node) { this.children.add(node); } public List getChildren() { return this.children; } public boolean equals(Object obj) { return ((ClassTreeNode)obj).getObjectClass().equals(this.objectClass); } public Class getObjectClass() { return this.objectClass; } public String getClassName() { return this.objectClass.getName(); }
public int hashCode() { return this.objectClass.hashCode(); } /***
Compares one class to another class by their inheritance tree.
* * @return an integer representing the comparison results as follows:
* 2 if this is a subclass of past in object
* -2 if this is a superclass of past in object
* 0 if they are not related (and in relation to sorting, equal)
* 0 if they are the same
*/ public int compareTo(Object obj) { Class objClass = ((ClassTreeNode)obj).getObjectClass(); if (objClass.equals(this.objectClass)) { return 0; } else if (this.objectClass.isAssignableFrom(objClass)) { return 2; } else if (objClass.isAssignableFrom(this.objectClass)) { return -2; } else { return 0; } } } // End of ClassTree$ClassTreeNode
}
</source>
Binary Tree
<source lang="java"> /*
DEVELOPING GAME IN JAVA Caracteristiques Editeur : NEW RIDERS Auteur : BRACKEEN Parution : 09 2003 Pages : 972 Isbn : 1-59273-005-1 Reliure : Paperback Disponibilite : Disponible a la librairie
- /
public class BinaryTreeTest {
public static void main(String[] args) { new BinaryTreeTest().run(); } static class Node { Node left; Node right; int value; public Node(int value) { this.value = value; } } public void run() { // build the simple tree from chapter 11. Node root = new Node(5); System.out.println("Binary Tree Example"); System.out.println("Building tree with root value " + root.value); insert(root, 1); insert(root, 8); insert(root, 6); insert(root, 3); insert(root, 9); System.out.println("Traversing tree in order"); printInOrder(root); System.out.println("Traversing tree front-to-back from location 7"); printFrontToBack(root, 7); } public void insert(Node node, int value) { if (value < node.value) { if (node.left != null) { insert(node.left, value); } else { System.out.println(" Inserted " + value + " to left of " + node.value); node.left = new Node(value); } } else if (value > node.value) { if (node.right != null) { insert(node.right, value); } else { System.out.println(" Inserted " + value + " to right of " + node.value); node.right = new Node(value); } } } public void printInOrder(Node node) { if (node != null) { printInOrder(node.left); System.out.println(" Traversed " + node.value); printInOrder(node.right); } } /** * uses in-order traversal when the origin is less than the node"s value * * uses reverse-order traversal when the origin is greater than the node"s * order */ public void printFrontToBack(Node node, int camera) { if (node == null) return; if (node.value > camera) { // print in order printFrontToBack(node.left, camera); System.out.println(" Traversed " + node.value); printFrontToBack(node.right, camera); } else if (node.value < camera) { // print reverse order printFrontToBack(node.right, camera); System.out.println(" Traversed " + node.value); printFrontToBack(node.left, camera); } else { // order doesn"t matter printFrontToBack(node.left, camera); printFrontToBack(node.right, camera); } }
}
</source>
Data structure that mantains data in a ordered binary tree; each node is greater (smaller) or equal than its 2 sub-nodes, for all the hierarchy.
<source lang="java">
/*
* JBoss, Home of Professional Open Source * Copyright 2005, JBoss Inc., and individual contributors as indicated * by the @authors tag. See the copyright.txt in the distribution for a * full listing of individual contributors. * * This is free software; you can redistribute it and/or modify it * under the terms of the GNU Lesser General Public License as * published by the Free Software Foundation; either version 2.1 of * the License, or (at your option) any later version. * * This software is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public * License along with this software; if not, write to the Free * Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA * 02110-1301 USA, or see the FSF site: http://www.fsf.org. */
import java.util.ruparator; /**
* Data structure that mantains data in a ordered binary tree; each node is * greater (smaller) or equal than its 2 sub-nodes, for all the hierarchy.*
* Elements of this data structure should either implement Comparable, or a
* Comparator should be given as argument to the constructor.
*
* @author
* @version $Revision: 2787 $
*/
@SuppressWarnings("unchecked")
public class Heap {
private Comparator m_comparator;
private int m_count;
private Object[] m_nodes;
/**
* Creates a new Heap whose elements inserted implement the {@link Comparable}
* interface.
*/
public Heap() {
this(null);
}
/**
* Creates a new Heap whose elements are compared using the given
* {@link Comparator}.
*
* @param comparator
*/
public Heap(Comparator comparator) {
m_comparator = comparator;
clear();
}
/**
* Inserts the given element in this heap.
*
* @param obj
*
* @see #extract
*/
public void insert(Object obj) {
int length = m_nodes.length;
// Expand if necessary
if (m_count == length) {
Object[] newNodes = new Object[length + length];
System.arraycopy(m_nodes, 0, newNodes, 0, length);
m_nodes = newNodes;
}
// Be cur_slot the first unused slot index; be par_slot its parent index.
// Start from cur_slot and walk up the tree comparing the object to
// insert with the object at par_slot; if it"s smaller move down the object
// at par_slot,
// otherwise cur_slot is the index where insert the object. If not done,
// shift up the tree so that now cur_slot is the old par_slot and
// par_slot is the parent index of the new cur_slot (so the grand-parent
// index of the old cur_slot) and compare again.
int k = m_count;
while (k > 0) {
int par = parent(k);
if (compare(obj, m_nodes[par]) < 0) {
m_nodes[k] = m_nodes[par];
k = par;
} else
break;
}
m_nodes[k] = obj;
++m_count;
}
/**
* Removes and returns the least element of this heap.
*
* @return the extracted object
*
* @see #insert
* @see #peek
*/
public Object extract() {
if (m_count < 1) {
return null;
} else {
int length = m_nodes.length >> 1;
// Shrink if necessary
if (length > 5 && m_count < (length >> 1)) {
Object[] newNodes = new Object[length];
System.arraycopy(m_nodes, 0, newNodes, 0, length);
m_nodes = newNodes;
}
//
int k = 0;
Object ret = m_nodes[k];
--m_count;
Object last = m_nodes[m_count];
for (;;) {
int l = left(k);
if (l >= m_count) {
break;
} else {
int r = right(k);
int child = (r >= m_count || compare(m_nodes[l], m_nodes[r]) < 0) ? l : r;
if (compare(last, m_nodes[child]) > 0) {
m_nodes[k] = m_nodes[child];
k = child;
} else {
break;
}
}
}
m_nodes[k] = last;
m_nodes[m_count] = null;
return ret;
}
}
/**
* @return without removing it, the least element of this heap.
*
* @see #extract
*/
public Object peek() {
if (m_count < 1) {
return null;
} else {
return m_nodes[0];
}
}
/**
* Empties this heap
*/
public void clear() {
m_count = 0;
m_nodes = new Object[10];
}
protected int compare(Object o1, Object o2) {
if (m_comparator != null) {
return m_comparator.rupare(o1, o2);
} else {
if (o1 == null) {
if (o2 == null) {
return 0;
} else {
return -((Comparable) o2).rupareTo(o1);
}
} else {
return ((Comparable) o1).rupareTo(o2);
}
}
}
/**
* @return the parent index of index
.
* @param index
*/
protected int parent(int index) {
return (index - 1) >> 1;
}
/**
* @param index
* @return the left child index of index
.
*/
protected int left(int index) {
return index + index + 1;
}
/**
* @param index
* @return the right child index of index
.
*/
protected int right(int index) {
return index + index + 2;
}
}
</source>
Tree Node for the for a general tree of Objects
<source lang="java">
/*
* * This software is subject to the terms of the Common Public License * Agreement, available at the following URL: * http://www.opensource.org/licenses/cpl.html . * Copyright (C) 2003-2004 TONBELLER AG. * All Rights Reserved. * You must accept the terms of that agreement to use this software. * * * */
import java.util.ArrayList; import java.util.Iterator; import java.util.List; /**
* Tree Node for the for a general tree of Objects */
public class TreeNode {
private TreeNode parent = null; private List children = null; private Object reference; /** * cTtor * @param obj referenced object */ public TreeNode(Object obj) { this.parent = null; this.reference = obj; this.children = new ArrayList(); } /** * remove node from tree */ public void remove() { if (parent != null) { parent.removeChild(this); } } /** * remove child node * @param child */ private void removeChild(TreeNode child) { if (children.contains(child)) children.remove(child); } /** * add child node * @param child node to be added */ public void addChildNode(TreeNode child) { child.parent = this; if (!children.contains(child)) children.add(child); } /** * deep copy (clone) * @return copy of TreeNode */ public TreeNode deepCopy() { TreeNode newNode = new TreeNode(reference); for (Iterator iter = children.iterator(); iter.hasNext();) { TreeNode child = (TreeNode) iter.next(); newNode.addChildNode(child.deepCopy()); } return newNode; } /** * deep copy (clone) and prune * @param depth - number of child levels to be copied * @return copy of TreeNode */ public TreeNode deepCopyPrune(int depth) { if (depth < 0) throw new IllegalArgumentException("Depth is negative"); TreeNode newNode = new TreeNode(reference); if (depth == 0) return newNode; for (Iterator iter = children.iterator(); iter.hasNext();) { TreeNode child = (TreeNode) iter.next(); newNode.addChildNode(child.deepCopyPrune(depth - 1)); } return newNode; } /** * @return level = distance from root */ public int getLevel() { int level = 0; TreeNode p = parent; while (p != null) { ++level; p = p.parent; } return level; } /** * walk through subtree of this node * @param callbackHandler function called on iteration */ public int walkTree(TreeNodeCallback callbackHandler) { int code = 0; code = callbackHandler.handleTreeNode(this); if (code != TreeNodeCallback.CONTINUE) return code; ChildLoop: for (Iterator iter = children.iterator(); iter.hasNext();) { TreeNode child = (TreeNode) iter.next(); code = child.walkTree(callbackHandler); if (code >= TreeNodeCallback.CONTINUE_PARENT) return code; } return code; } /** * walk through children subtrees of this node * @param callbackHandler function called on iteration */ public int walkChildren(TreeNodeCallback callbackHandler) { int code = 0; ChildLoop: for (Iterator iter = children.iterator(); iter.hasNext();) { TreeNode child = (TreeNode) iter.next(); code = callbackHandler.handleTreeNode(child); if (code >= TreeNodeCallback.CONTINUE_PARENT) return code; if (code == TreeNodeCallback.CONTINUE) { code = child.walkChildren(callbackHandler); if (code > TreeNodeCallback.CONTINUE_PARENT) return code; } } return code; } /** * @return List of children */ public List getChildren() { return children; } /** * @return parent node */ public TreeNode getParent() { return parent; } /** * @return reference object */ public Object getReference() { return reference; } /** * set reference object * @param object reference */ public void setReference(Object object) { reference = object; }
} // TreeNode /*
* * This software is subject to the terms of the Common Public License * Agreement, available at the following URL: * http://www.opensource.org/licenses/cpl.html . * Copyright (C) 2003-2004 TONBELLER AG. * All Rights Reserved. * You must accept the terms of that agreement to use this software. * * * */
/**
* handle call back for position tree */
interface TreeNodeCallback {
public static final int CONTINUE = 0; public static final int CONTINUE_SIBLING = 1; public static final int CONTINUE_PARENT = 2; public static final int BREAK = 3; /** * @param node the current node to handle * @return 0 continue tree walk * 1 break this node (continue sibling) * 2 break this level (continue parent level) * 3 break tree walk */ int handleTreeNode(TreeNode node);
} // TreeNodeCallback
</source>
Your own tree with generic user object
<source lang="java">
/*
* Copyright 2007 Google Inc. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */
import java.util.ArrayList; import java.util.Collection; import java.util.HashMap; /**
* @author ycoppel@google.ru (Yohann Coppel) * * @param <T> * Object"s type in the tree. */
public class Tree<T> {
private T head; private ArrayList<Tree<T>> leafs = new ArrayList<Tree<T>>(); private Tree<T> parent = null; private HashMap<T, Tree<T>> locate = new HashMap<T, Tree<T>>(); public Tree(T head) { this.head = head; locate.put(head, this); } public void addLeaf(T root, T leaf) { if (locate.containsKey(root)) { locate.get(root).addLeaf(leaf); } else { addLeaf(root).addLeaf(leaf); } } public Tree<T> addLeaf(T leaf) { Tree<T> t = new Tree<T>(leaf); leafs.add(t); t.parent = this; t.locate = this.locate; locate.put(leaf, t); return t; } public Tree<T> setAsParent(T parentRoot) { Tree<T> t = new Tree<T>(parentRoot); t.leafs.add(this); this.parent = t; t.locate = this.locate; t.locate.put(head, this); t.locate.put(parentRoot, t); return t; } public T getHead() { return head; } public Tree<T> getTree(T element) { return locate.get(element); } public Tree<T> getParent() { return parent; } public Collection<T> getSuccessors(T root) { Collection<T> successors = new ArrayList<T>(); Tree<T> tree = getTree(root); if (null != tree) { for (Tree<T> leaf : tree.leafs) { successors.add(leaf.head); } } return successors; } public Collection<Tree<T>> getSubTrees() { return leafs; } public static <T> Collection<T> getSuccessors(T of, Collection<Tree<T>> in) { for (Tree<T> tree : in) { if (tree.locate.containsKey(of)) { return tree.getSuccessors(of); } } return new ArrayList<T>(); } @Override public String toString() { return printTree(0); } private static final int indent = 2; private String printTree(int increment) { String s = ""; String inc = ""; for (int i = 0; i < increment; ++i) { inc = inc + " "; } s = inc + head; for (Tree<T> child : leafs) { s += "\n" + child.printTree(increment + indent); } return s; }
}
</source>