Binær søgetræ

Der er forskellige strukturer der har fordele altefter hvad det binære træ skal bruges til, hvor stort det er og hvor tit der skal ændres i det.

kan du specificere lidt mere?

mvh JakobA

Hvis det er binært skal der kun være 2 børn, ellers er det b-træer du snakker om (Og som du viser).

Her er et ok link om det: http://www.public.asu.edu/~peterjn/btree/

Lave din égen.

class treeNode
private treeNode left,right;
private Object value;

public treeNode(Object v){
value=v;
}

public void setLeft(treeNode t){
left=t;
}
public void setRight(treeNode t){
right=t;
}

Class BinTree

Hvor metoderne til iterere gennem tree\'er med ligger.

Er kommet frem til nedenstående, men skal nu gemme mine noder i en linked liste. For at kunne gemmen mine skal jeg vel kunne skelne imellem højre og venstre node(2 x i +1, 2 x i +2)

public class BTNode
{
private int info;
private BTNode leftChild;
private BTNode rightChild;
public BTNode(int theInfo)
private LinkedListe = new LinkedList();


{
info = theInfo;
leftChild = null;
rightChild = null;
}
// Read Accessors
public int getInfo()
{
return info;
}
public BTNode getLeft()
{
return leftChild;
}
public BTNode getRight()
{
return rightChild;
}
// Write Accessors
public void setInfo(int theInfo)
{
info = theInfo;
}
public void setLeft(BTNode theNode)
{
leftChild = theNode;
{
public void setLeft(int theInfo)
{
BTNode newNode;
newNode = new BTNode(theInfo);
setLeft( newNode );
}
public void setRight(BTNode theNode)
{
rightChild = theNode;
}
public void setRight(int theInfo)
{
BTNode newNode;
newNode = new BTNode(theInfo);
setRight( newNode );
}
}

Her er en løsning der virker.

public class BinTree
{
  protected TreeNode root, temp;

  public BinTree()
  {
    root = null;
   
  }

  private TreeNode insert(TreeNode tree, int x)
  {
    if(tree == null)
      return new TreeNode(x);
    else
    {
      if(x < tree.data)
        tree.left = insert(tree.left, x);
      else
        tree.right = insert(tree.right, x);
    }
    return tree;
  }

  public void insert(int x)
  {
    root = insert(root, x);
  }
 
  public void delete(int v)
  {
      if (root.getData()==v)
      {
         
      }
    else
    {
      root.delete(root,v);   
    }
   
}



  private TreeNode delete(TreeNode tree,int v)
  {
      TreeNode papa=getPapa(tree,null,v);
      TreeNode chil=null;
    if (papa!=null)
      {
          if (papa.getLeft().getData()==v)
                chil=papa.getLeft()
        else
            chil=papa.getRight();
       
        if (chil.getLeft()==null && chil.getRight()==null)
            papa.null   
    }
  }
 
  public boolean findes(int v)
  {
      return (findes(root,v));
   
  }
 
  private boolean findes(TreeNode tree,int v)
  {
      if (tree==null)
        return(false);
       
    if (tree.getData()==v))
        return(true);
    if (v<tree.getData())
        return findes(tree.getLeft(),v);
       
    else
        return findes(tree.getRight(),v);   
   

  }
 
  private TreeNode getPapa(TreeNode chil,TreeNode papa, int v)
  {
      if (chil==null)
        return(null);
       
    if (chil.getData()==v))
        return(papa);
    if (v<chil.getData())
        return getPapa(chil.getLeft(),chil,v);
       
    else
        return getPapa(chil.getRight(),chil,v);
  }
}

public class TreeNode
{
  protected int data;
  protected TreeNode left, right;

  public TreeNode(int d)
  {
    data = d;
    left = null;
    right = null;
  }
 
  public int getData()
  {
      return(data);
     
  }
  public TreeNode getLeft()
  {
      return(left);
  }
 
  public TreeNode getRight()
  {
      return(right);
  }     
}

Hvis ikke du skal havde andet end int\'s liggende i dit træ, hvorfor implementerer du det så ikke bare i et array... Det er lidt nemmere at overskue i starten! :)

Din formel skal evt. redigeres lidt:

1) spring index 0 over
2) index 1 = rod
3) venstre barn = index 2
4) højre barn = index 3
osv.

venstre barn = index for given knude * 2
højre barn = index for given knude * 2 + 1
parent = index for given knude / 2 (pga. heltalsdivision)

takker for hjælpen :-) allesammen