Binary Trees ( Ağaçlar )

Ağaçlar; lineer olmayan belirli niteliklere sahip iki boyutlu veri yapılarıdır. Bağlı listeler, yığıtlar ve kuyruklar gibi doğrusal bir veri yapısı değildir. İkili ağaçlar (Binary Trees) düğümlerinde en fazla iki bağ içerir ve sol düğüm root'dan küçük ve sağ düğüm root'dan her zaman büyüktür.

İkili ağaç yapısını Java kodu ile örneklendireceğim. Bu kodda ikili ağaca ait bir çok özellik ve fonksiyon mevcut.

class Tree
{
private TreeNode root;
int h1 = 0,h2=0;
public Tree()
{ 
root = null; 
}
public TreeNode getRoot()
{ 
return root; 
}



int dugumsayisi(TreeNode p)    //Ağaçtaki node sayısını bulur
{
if(p==null)return 0;
if(p.leftChild!=null)
{
h1=dugumsayisi(p.leftChild);
}
if(p.rightChild!=null)
{
h2=dugumsayisi(p.rightChild);
}
return(max(h1,h2)+1);
}


private int max(int h1, int h2) {
if(h1>h2)return h1;
return h2;
}


public void preOrder(TreeNode localRoot)    //Önce kök sonra left child
{                                           //Son olarak right child taranır
if(localRoot!=null)
{
localRoot.displayNode();
preOrder(localRoot.leftChild);
preOrder(localRoot.rightChild);
}
}

public void inOrder(TreeNode localRoot)     //Önce left child sonra kök
{                                           //Son olarak right child taranır
if(localRoot!=null)                       //Aynı zamanda ağacı sıralı bir şekilde yazar
{
inOrder(localRoot.leftChild);
localRoot.displayNode();
inOrder(localRoot.rightChild);
}
}

public void postOrder(TreeNode localRoot)      //Önce left child
{                                              //Sonra right child
if(localRoot!=null)                          //Son olarak kök taranır
{   
postOrder(localRoot.leftChild);
postOrder(localRoot.rightChild);
localRoot.displayNode();
}
}


public void insert(int yenidata)            //Ağaca eleman ekleme
{
TreeNode yeniNode = new TreeNode();
yeniNode.data = yenidata;
if(root==null)
root = yeniNode;
else
{
TreeNode current = root;
TreeNode parent;
while(true)
{
parent = current;
if(yenidata < current.data)
{
current = current.leftChild;
if(current==null)
{
parent.leftChild=yeniNode;
return;
}
} 
else
{
current = current.rightChild;
if(current==null)
{
parent.rightChild=yeniNode;
return;
}
}
}   
}
}



int derinlik(TreeNode root)              //Ağacın derinliğini hesaplama
{ 
if (root==null) 
{ 
return -1; 
} 
else { 
int lDepth = derinlik(root.getLeftChild()); 
int rDepth = derinlik(root.getRightChild());
if (lDepth > rDepth)
return(lDepth+1); 
else return(rDepth+1); 
} 
}




public int minValue() { 
return( minValue(root) ); 
} 

private int minValue(TreeNode node) { 
TreeNode current = node; 
while (current.getLeftChild() != null) { 
current = current.getLeftChild(); 
}
return(current.getData()); 
}





public int maxValue() { 
return( maxValue(root) ); 
} 


private int maxValue(TreeNode node) { 
TreeNode current = node; 
while (current.getRightChild() != null) { 
current = current.getRightChild(); 
}
return(current.getData()); 
}






static void lookup(TreeNode node, int target)    //Ağaçta arama
{ 
if (node == null) 
{ 
return; 
} 
else 
{ 
if (target == node.getData()) 
System.out.println(node.getData()+"bulundu"); 
else { 
if (target < node.getData()) lookup(node.getLeftChild(), target); 
else lookup(node.getRightChild(), target); 
} 
} 
}


public boolean isBST() {        //Ağaç ikili ağaç mı?
return(isBST(root)); 
}

private boolean isBST(TreeNode node) 
{ 
if (node==null) return(true);
if (node.leftChild!=null && maxValue(node.leftChild) > node.data) 
return(false); 
if (node.rightChild!=null && minValue(node.rightChild) <= node.data) 
return(false);
return( isBST(node.leftChild) && isBST(node.rightChild) ); 
} 


public boolean sameTree(Tree other) {      //İki ağaç eşit mi?
return( sameTree(root, other.root) ); 
}

boolean sameTree(TreeNode a, TreeNode b) 
{ 
if (a==null && b==null) 
return(true);
else if (a!=null && b!=null) 
{ 
return( a.data == b.data && 
sameTree(a.leftChild, b.leftChild) && 
sameTree(a.rightChild, b.rightChild) 
); 
} 
else return(false); 
} 

}