Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package LigaVerwaltung;
- public class BinarySearchTree<ContentType extends ComparableContent<ContentType>>
- {
- private class BSTNode<CT extends ComparableContent<CT>>
- {
- private CT content;
- private BinarySearchTree<CT> left, right;
- public BSTNode(CT pContent)
- {
- this.content = pContent;
- left = new BinarySearchTree<CT>();
- right = new BinarySearchTree<CT>();
- }
- }
- private BSTNode<ContentType> node;
- public BinarySearchTree()
- {
- this.node = null;
- }
- public boolean isEmpty()
- {
- return this.node == null;
- }
- public void insert(ContentType pContent)
- {
- if (pContent != null)
- {
- if (isEmpty())
- {
- this.node = new BSTNode<ContentType>(pContent);
- }
- else if (pContent.isLess(this.node.content))
- {
- this.node.left.insert(pContent);
- }
- else if (pContent.isGreater(this.node.content))
- {
- this.node.right.insert(pContent);
- }
- }
- }
- public BinarySearchTree<ContentType> getLeftTree()
- {
- if (this.isEmpty())
- {
- return null;
- }
- else
- {
- return this.node.left;
- }
- }
- public ContentType getContent()
- {
- if (this.isEmpty())
- {
- return null;
- }
- else
- {
- return this.node.content;
- }
- }
- public BinarySearchTree<ContentType> getRightTree()
- {
- if (this.isEmpty())
- {
- return null;
- }
- else
- {
- return this.node.right;
- }
- }
- public void remove(ContentType pContent)
- {
- if (isEmpty())
- {
- return;
- }
- if (pContent.isLess(node.content))
- {
- node.left.remove(pContent);
- }
- else if (pContent.isGreater(node.content))
- {
- node.right.remove(pContent);
- }
- else
- {
- if (node.left.isEmpty())
- {
- if (node.right.isEmpty())
- {
- node = null;
- }
- else
- {
- node = getNodeOfRightSuccessor();
- }
- }
- else if (node.right.isEmpty())
- {
- node = getNodeOfLeftSuccessor();
- }
- else
- {
- if (getNodeOfRightSuccessor().left.isEmpty())
- {
- node.content = getNodeOfRightSuccessor().content;
- node.right = getNodeOfRightSuccessor().right;
- }
- else
- {
- BinarySearchTree<ContentType> previous = node.right.ancestorOfSmallRight();
- BinarySearchTree<ContentType> smallest = previous.node.left;
- this.node.content = smallest.node.content;
- previous.remove(smallest.node.content);
- }
- }
- }
- }
- public ContentType search(ContentType pContent)
- {
- if (this.isEmpty() || pContent == null)
- {
- return null;
- }
- else
- {
- ContentType content = this.getContent();
- if (pContent.isLess(content))
- {
- return this.getLeftTree().search(pContent);
- }
- else if (pContent.isGreater(content))
- {
- return this.getRightTree().search(pContent);
- }
- else if (pContent.isEqual(content))
- {
- return content;
- }
- else
- {
- return null;
- }
- }
- }
- private BinarySearchTree<ContentType> ancestorOfSmallRight()
- {
- if (getNodeOfLeftSuccessor().left.isEmpty())
- {
- return this;
- }
- else
- {
- return node.left.ancestorOfSmallRight();
- }
- }
- private BSTNode<ContentType> getNodeOfLeftSuccessor()
- {
- return node.left.node;
- }
- private BSTNode<ContentType> getNodeOfRightSuccessor()
- {
- return node.right.node;
- }
- }
- package LigaVerwaltung;
- public interface ComparableContent<ContentType> {
- public boolean isGreater(ContentType pContent);
- public boolean isEqual(ContentType pContent);
- public boolean isLess(ContentType pContent);
- boolean isGreater(Verein pContent);
- }
- package LigaVerwaltung;
- public class Verein implements ComparableContent<Verein>
- {
- private String name;
- private int Platz;
- public Verein(String pName, int pPlatz)
- {
- name=pName;
- Platz=pPlatz;
- }
- public String getName()
- {
- return name;
- }
- public int getPlatz()
- {
- return Platz;
- }
- @Override
- public boolean isGreater( Verein pContent)
- {
- if(this.getPlatz()>pContent.getPlatz())
- {
- return false;
- }
- else
- {
- return true;
- }
- }
- @Override
- public boolean isEqual(Verein pContent)
- {
- return false;
- }
- @Override
- public boolean isLess(Verein pContent)
- {
- return false;
- }
- public void setName(String name)
- {
- this.name = name;
- }
- public void setPlatz(int platz)
- {
- Platz = platz;
- }
- }
- package LigaVerwaltung;
- public class Ligaverwaltung
- {
- private BinarySearchTree<Verein> dieLiga;
- public static void main(String[]args)
- {
- new Ligaverwaltung();
- }
- public Ligaverwaltung()
- {
- dieLiga= new BinarySearchTree<Verein>();
- dieLiga.insert(new Verein("L.A. Lakers", 10));
- dieLiga.insert(new Verein("Chicago Bulls", 1));
- dieLiga.insert(new Verein("Cleavland Caveliers", 3));
- dieLiga.insert(new Verein("Dallas Mavericks",12));
- dieLiga.insert(new Verein("Miami Heats", 9));
- dieLiga.insert(new Verein("Minnesota Timberwolves", 4));
- inOrder(dieLiga);
- }
- public void inOrder(BinarySearchTree<Verein> baum)
- {
- if(!baum.getLeftTree().isEmpty()) inOrder(baum.getLeftTree());
- System.out.println(baum.getContent().getName() + ","+ baum.getContent().getPlatz());
- if(!baum.getRightTree().isEmpty()) inOrder(baum.getRightTree());
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement