package dataStructures; import java.util.*; /** *
Titulo: Uma implementaçao dinâmica da Árvore Binária
*Descrição: Esta implementaçao usa um nó com duas referências que guardam as subárvores esquerda e direita
* @version 1.0 */ public class DBinTree implements BinTree,Cloneable { private DBinTree leftTree, rightTree; private Object infoTree; public DBinTree() { infoTree = null; leftTree = rightTree = null; } public DBinTree(Object o, BinTree left, BinTree right) { constr(o, left, right); } public BinTree empty() { return new DBinTree(); } public void constr(Object item, BinTree left, BinTree right) { infoTree = item; leftTree = (DBinTree)left; rightTree = (DBinTree)right; } public boolean isEmpty() { return infoTree == null; } public Object root() { return infoTree; } public BinTree left() { return leftTree; } public BinTree right() { return rightTree; } public int length() { if (isEmpty()) return 0; return 1 + left().length() + right().length(); } public int height() { if (isEmpty()) return 0; return 1 + Math.max(right().height(), left().height()); } public boolean isLeaf() { if (isEmpty()) return false; return left().isEmpty() && right().isEmpty(); } public boolean equals(BinTree t) { if (isEmpty() && t.isEmpty()) return true; if (isEmpty() || t.isEmpty()) return false; return root().equals(t.root()) && left().equals(t.left()) && right().equals(t.right()); } public void prefix(Visitor op) { if (!isEmpty()) { op.visit(root()); left().prefix(op); right().prefix(op); } } public void prefixIterative(Visitor op) { // an example of iterative solution if (isEmpty()) return; VStack stack = new VStack(); stack.push(this); while (!stack.isEmpty()) { DBinTree actual = (DBinTree)stack.top(); stack.pop(); op.visit(actual.root()); if (!actual.right().isEmpty()) stack.push(actual.right()); if (!actual.left().isEmpty()) stack.push(actual.left()); } } public void breathIterative(Visitor op) { if (isEmpty()) return; VQueue queue = new VQueue(); queue.enqueue(this); while (!queue.isEmpty()) { DBinTree actual = (DBinTree)queue.front(); queue.dequeue(); op.visit(actual.root()); if (!actual.left().isEmpty()) queue.enqueue(actual.left()); if (!actual.right().isEmpty()) queue.enqueue(actual.right()); } } public void infix(Visitor op) { if (!isEmpty()) { left().prefix(op); op.visit(root()); right().prefix(op); } } public void sufix(Visitor op) { if (!isEmpty()) { left().prefix(op); right().prefix(op); op.visit(root()); } } public Iterator iterator() { return new BinTreeIterator(this); } public String toString() { return isEmpty() ? "[]" : makeTree(0, this); } private String makeTree(int level, DBinTree T) { if (T.isEmpty()) // base da recursão return mark(level) + "[]\n"; if (T.isLeaf()) // base da recursão return mark(level) + T.root() + "\n"; // passo da recursão return mark(level) + T.root() + "\n" + makeTree(level+1,(DBinTree)T.left()) + makeTree(level+1,(DBinTree)T.right()); } private String mark(int level) { // identar o símbolo '|' String s=""; for (int i=0;i