Java/Collections Data Structure/Tree
Содержание
- 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
/*
* 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;
/**
* <p>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.</p>
*
*
* 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;
}
/**
* <p>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.</p>
*
* <p>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.</p>
*
* @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);
}
}
/**
* <p>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.</p>
*/
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;
/**
* <p>Constructs a ClassTreeNode with the given Class.</p>
*
* @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();
}
/**
* <p>Compares one class to another class by their inheritance tree.</p>
*
* @return an integer representing the comparison results as follows:<br>
* 2 if this is a subclass of past in object<br>
* -2 if this is a superclass of past in object<br>
* 0 if they are not related (and in relation to sorting, equal)<br>
* 0 if they are the same<br>
*/
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
}
Binary Tree
/*
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);
}
}
}
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.
/*
* 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.
* <p>
* 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 <code>index</code>.
* @param index
*/
protected int parent(int index) {
return (index - 1) >> 1;
}
/**
* @param index
* @return the left child index of <code>index</code>.
*/
protected int left(int index) {
return index + index + 1;
}
/**
* @param index
* @return the right child index of <code>index</code>.
*/
protected int right(int index) {
return index + index + 2;
}
}
Tree Node for the for a general tree of Objects
/*
*
* 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
Your own tree with generic user object
/*
* 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;
}
}
