Java Binarno Tenarno drvo

[ RasoRaso @ 23.05.2016. 18:17 ] @

Zna li ko riješiti ove zadatke?

Na slici je dato ternarno drvo traženja (ternary search tree). Čvorovi binarnog i ternarnog drveta opisani su klasama BNode i Tnode (vidi sliku ispod). Referenca left pokazuje na poddrvo koje sadrži vrijednosti manje od key1; referenca middle pokazuje na poddrvo koje sadrži vrijednosti veće od key1 i manje od key2; referenca right pokazuje na poddrvo koje sadrži vrijednosti veće od key2. Ako je key2 = -1, tada ne postoji poddrvo sa vrijednostima većim od key1. Reference na null prikazane su isprekidanom linijom. Sve vrijednosti u drvetu su nenegativne i različite. Napisati metode boolean FindKey(TNode t, int value) koja vraća true ako value postoji u ternarnom drvetu i false inače, metod void PrintInOrder(TNode t) koja štampa u rastućem redosljedu vrijednosti sačuvane u ternarnom drvetu i proceduru TNode BuildTernaryTree (TNode t, Bnode b) koja od binarnog drveta traženja b kreira odgovarajuće ternarno drvo t. Na posljednjoj slici dato je binarno drvo od kojeg je nastalo ternarno drvo sa prve slike. Pravila konverzije su sljedeća:
• Broj iz korijena drveta B postaje key1 u T (broj 14)
• Ključevi u lijevom poddrvetu drveta B biće u lijevom poddrvetu drveta T (brojevi 1,5,7,8)
• Neka je R desno poddrvo u B. Korijen poddrveta R postaje key2 u T (broj 20)
• Brojevi iz desnog poddrveta drveta R biće u poddrvetu na koje pokazuje pokazivač middle drveta T (brojevi 15, 16,18, 19)
• Brojevi iz desnog poddrveta drveta R biće u poddrvetu na koje pokazuje pokazivač right drveta T (brojevi 22 i 24)
• Ova pravila se primjenjuju rekurzivno kroz čitavo drvo

class BNode {
int key;
Bnode left,right;
}

class TNode {
int key1, key2;
Tnode left, middle, right;
}

Ternarno drvo

http://www.upslike.net/slika?id=tenarno-5d7a47.png

Drugi zadatak

Napisati klasu BSTView izvedenu iz klase JFrame za dodavanje i brisanje elemenata u binarno drvo traženja i za crtanje drveta. Klikom na dugme Insert, u drvo se unosi broj iz tekstualnog polja i crta se novo drvo. Klikom na dugme Delete, iz drveta se briše broj iz tekstualnog polja i crta se novo drvo. U oba slučaja, ako broj ne postoji u drvetu, štampati poruku odgovarajuću poruku (koristite OptionPane.showMessageDialog ).

http://www.upslike.net/slika?id=tenarno-5d7a47.png

Digitron sam uradio i AVL drvo mada nisam brisanje iz AVL drveta.
Evo koda za AVL drvo:

import java.util.LinkedList;
import java.util.Queue;

public class AVL<T extends Comparable<T>>
{
public class Cvor<T>
{

private T data;
private Cvor<T> left;
private Cvor<T> right;
public int level;
private int depth;

public Cvor(T data)
{
this(data, null, null);
}

public Cvor(T data, Cvor<T> left, Cvor<T> right)
{
super();
this.data = data;
this.left = left;
this.right = right;
if (left == null && right == null)
setDepth(1);
else if (left == null)
setDepth(right.getDepth() + 1);
else if (right == null)
setDepth(left.getDepth() + 1);
else
setDepth(Math.max(left.getDepth(), right.getDepth()) + 1);
}

public T getData() {
return data;
}

public void setData(T data) {
this.data = data;
}

public Cvor<T> getLeft() {
return left;
}

public void setLeft(Cvor<T> left) {
this.left = left;
}

public Cvor<T> getRight() {
return right;
}

public void setRight(Cvor<T> right) {
this.right = right;
}

public int getDepth() {
return depth;
}

public void setDepth(int depth) {
this.depth = depth;
}

}
Cvor<T> root;

public AVL() {
root = null;
}

public T Maximum() {
Cvor<T> local = root;
if (local == null)
return null;
while (local.getRight() != null)
local = local.getRight();
return local.getData();
}

public T Minimum() {
Cvor<T> local = root;
if (local == null)
return null;
while (local.getLeft() != null) {
local = local.getLeft();
}
return local.getData();
}

private int depth(Cvor<T> Cvor) {
if (Cvor == null)
return 0;
return Cvor.getDepth();
// 1 + Math.max(depth(Cvor.getLeft()), depth(Cvor.getRight()));
}

public Cvor<T> insert(T data) {
root = insert(root, data);
switch (balanceNumber(root)) {
case 1:
root = rotateLeft(root);
break;
case -1:
root = rotateRight(root);
break;
default:
break;
}
return root;
}

public Cvor<T> insert(Cvor<T> Cvor, T data) {
if (Cvor == null)
return new Cvor<T>(data);
if (Cvor.getData().compareTo(data) > 0) {
Cvor = new Cvor<T>(Cvor.getData(), insert(Cvor.getLeft(), data),
Cvor.getRight());
// Cvor.setLeft(insert(Cvor.getLeft(), data));
} else if (Cvor.getData().compareTo(data) < 0) {
// Cvor.setRight(insert(Cvor.getRight(), data));
Cvor = new Cvor<T>(Cvor.getData(), Cvor.getLeft(), insert(
Cvor.getRight(), data));
}
// After insert the new Cvor, check and rebalance the current Cvor if
// necessary.
switch (balanceNumber(Cvor)) {
case 1:
Cvor = rotateLeft(Cvor);
break;
case -1:
Cvor = rotateRight(Cvor);
break;
default:
return Cvor;
}
return Cvor;
}

private int balanceNumber(Cvor<T> Cvor) {
int L = depth(Cvor.getLeft());
int R = depth(Cvor.getRight());
if (L - R >= 2)
return -1;
else if (L - R <= -2)
return 1;
return 0;
}

private Cvor<T> rotateLeft(Cvor<T> Cvor) {
Cvor<T> q = Cvor;
Cvor<T> p = q.getRight();
Cvor<T> c = q.getLeft();
Cvor<T> a = p.getLeft();
Cvor<T> b = p.getRight();
q = new Cvor<T>(q.getData(), c, a);
p = new Cvor<T>(p.getData(), q, b);
return p;
}

private Cvor<T> rotateRight(Cvor<T> Cvor) {
Cvor<T> q = Cvor;
Cvor<T> p = q.getLeft();
Cvor<T> c = q.getRight();
Cvor<T> a = p.getLeft();
Cvor<T> b = p.getRight();
q = new Cvor<T>(q.getData(), b, c);
p = new Cvor<T>(p.getData(), a, q);
return p;
}

public boolean search(T data) {
Cvor<T> local = root;
while (local != null) {
if (local.getData().compareTo(data) == 0)
return true;
else if (local.getData().compareTo(data) > 0)
local = local.getLeft();
else
local = local.getRight();
}
return false;
}

public String toString() {
return root.toString();
}
private void Printaj(Cvor<T> d)
{

if(d == null) return;
Printaj(d.right);
System.out.println(d.data);
Printaj(d.left);
}

public void Printaj()
{
Printaj(root);
}
private void inorder(Cvor<T> d)
{

if(d == null) return;
inorder(d.left);
System.out.println(d.data);
inorder(d.right);

}

public void inorder()
{
inorder(root);
}

private void preorder(Cvor<T> d)
{

if(d == null) return;
System.out.println(d.data);
preorder(d.left);
preorder(d.right);

}

public void preorder()
{
preorder(root);
}

private void postorder(Cvor<T> d)
{

if(d == null) return;
postorder(d.left);
postorder(d.right);
System.out.println(d.data);

}

public void postorder()
{
postorder(root);
}
}

Znači tu mi fali kod za remove.Ako ko imaš nešto optimalnije za ovo već riješeno hvala i u tom slučaju.

Fala unaprijed i pozdrav iz Crne Gore