// Created by Anton Böhler import java.util.ArrayList; public class Main { public static void main(String[] args) throws EmptyElementAssignmentException { ArrayList list; Tree tree = new Tree(3); System.out.println(tree.getK() + "-tree"); tree.insertRoot("root"); //adding a root tree.insertRoot("newRoot"); //inserting root tree.add("node1", "root"); //adding String tree.add("node2", "newRoot"); tree.add(3, "node1"); //adding Integer(int) /* * newRoot * / \ * root node2 * | * node1 * | * 3 */ tree.changeValue("root", "node3"); //changing value of existing nodes/root tree.changeValue("newRoot", "root"); tree.add("node4", "node2"); tree.add("node5", "node2"); /* * root * / \ * node3 node2 * | | \ * node1 node4 node5 * | * 3 */ System.out.println("preorder:"); list = tree.getPreOrder(); for(int i=0;i getPreOrder(){ ArrayList list = new ArrayList(); root.getPreOrder(list); return list; } public ArrayList getInOrder(){ ArrayList list = new ArrayList(); root.getInOrder(list); return list; } public ArrayList getPostOrder(){ ArrayList list = new ArrayList(); root.getPostOrder(list); return list; } public ArrayList getLevels(){ ArrayList list = new ArrayList(); ArrayList queue = new ArrayList(); queue.add(root); while(queue.size() > 0) { TreeElement front = queue.get(0); queue.remove(0); if(front.isEnd()) { continue; }else { list.add(front.getValue()); } TreeElement[] children = front.getChildren(); for(int i=0;i list); public abstract void getInOrder(ArrayList list); public abstract void getPostOrder(ArrayList list); public abstract TreeElement getNode(DataElement d); public abstract boolean isEnd(); public abstract int getNodeCount(); public abstract boolean isLeaf(); public abstract boolean isInternalNode(); public abstract int getLevelNode(DataElement d); public abstract int getLeafNodeCount(); public abstract int getInternalNodeCount(); public abstract int getChildrenCount(); } //-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- import java.util.ArrayList; public class TreeEnd extends TreeElement{ private int k; private TreeElement parent; public TreeEnd(int k, TreeElement parent) { this.k = k; this.parent = parent; } public int getK() { return k; } public DataElement getValue() { return new DataElementEmpty(); } public void setValue(DataElement d) throws EmptyElementAssignmentException { throw new EmptyElementAssignmentException(); } public TreeElement[] getChildren() { return null; } public int getTreeHeight() { return 0; } public boolean contains(DataElement d) { return false; } public void getPreOrder(ArrayList list) { } public void getInOrder(ArrayList list) { } public void getPostOrder(ArrayList list) { } public TreeElement getNode(DataElement d) { return null; } public boolean isEnd() { return true; } public TreeElement getParent() { return parent; } public void setParent(TreeElement p) { parent = p; } public int getNodeCount() { return 0; } public boolean isLeaf() { return false; } public boolean isInternalNode() { return false; } public int getLevelNode(DataElement d) { return -1; } public int getLeafNodeCount() { return 0; } public int getInternalNodeCount() { return 0; } public int getChildrenCount() { return 0; } } //-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- import java.util.ArrayList; public class TreeNode extends TreeElement { private int k; private DataElement value; private TreeElement[] children; private TreeElement parent; public TreeNode(int k, DataElement d, TreeElement parent) { this.k = k; this.parent = parent; children = new TreeElement[k]; for (int i = 0; i < children.length; i++) { children[i] = new TreeEnd(k, this); } value = d; } public int getK() { return k; } public DataElement getValue() { return value; } public void setValue(DataElement d) throws EmptyElementAssignmentException { value = d; } public TreeElement[] getChildren() { return children; } public int getTreeHeight() { int biggest = 0; for (int i = 0; i < children.length; i++) { biggest = Math.max(biggest, children[i].getTreeHeight()); } return biggest + 1; } public boolean contains(DataElement d) { if (value.equals(d)) { return true; } for (int i = 0; i < children.length; i++) { if (children[i].contains(d)) { return true; } } return false; } public void getPreOrder(ArrayList list) { list.add(value); for (int i = 0; i < children.length; i++) { children[i].getPreOrder(list); } } public void getInOrder(ArrayList list) { for (int i = 0; i < children.length / 2; i++) { children[i].getInOrder(list); } list.add(value); for (int i = children.length / 2; i < children.length; i++) { children[i].getInOrder(list); } } public void getPostOrder(ArrayList list) { for (int i = 0; i < children.length; i++) { children[i].getPostOrder(list); } list.add(value); } public TreeElement getNode(DataElement d) { if (d.equals(value)) { return this; } else { for (int i = 0; i < children.length; i++) { TreeElement node = children[i].getNode(d); if (node != null) { return node; } } } return null; } public boolean isEnd() { return false; } public TreeElement getParent() { return parent; } public void setParent(TreeElement p) { parent = p; } public int getNodeCount() { int sum = 1; for(int i=0;i