TechCodeview

İkili ağaç Verileri hiyerarşik biçimde depoladıkları için esas olarak sıralama ve arama için kullanılan ağaç tipi doğrusal olmayan bir veri yapısıdır. Bu bölümde şunları öğreneceğiz: Java'da ikili ağaç veri yapısının uygulanması . Ayrıca ikili ağaç veri yapısının kısa bir açıklamasını da sağlar.

İkili ağaç

Her düğümün (ebeveyn) en fazla iki alt düğüme (sol ve sağ) sahip olduğu ağaca ikili ağaç denir. En üstteki düğüme kök düğüm denir. İkili ağaçta bir düğüm, sol ve sağ alt düğümün verilerini ve işaretçisini (adresini) içerir.

yükseklik bir ikili ağacın ağacın kökü arasındaki kenar sayısı ve en uzak (en derin) yaprağı. Eğer ağaç boş , yükseklik 0 . Düğümün yüksekliği şu şekilde gösterilir: H .

Yukarıdaki ikili ağacın yüksekliği 2'dir.

Aşağıdaki formülü kullanarak yaprak ve düğüm sayısını hesaplayabiliriz.

• Maksimum yaprak düğüm sayısı ikili bir ağaçtır: 2^H
• Maksimum düğüm sayısı ikili bir ağaçtır: 2^sa+1-1

Burada h ikili ağacın yüksekliğidir.

İkili Ağaç Örneği

İkili Ağaç Türleri

Veri yapısında aşağıdaki ikili ağaç türleri vardır:

1. Tam/ Kesinlikle İkili Ağaç
2. Tam İkili Ağaç
3. Mükemmel İkili Ağaç
4. Denge İkili Ağacı
5. Köklü İkili Ağaç
6. Dejenere / Patolojik İkili Ağaç
7. Genişletilmiş İkili Ağaç
8. Çarpık İkili Ağaç
   1. Sola çarpık İkili Ağaç
   2. Sağa çarpık İkili Ağaç
9. Dişli İkili Ağaç
   1. Tek Dişli İkili Ağaç
   2. Çift Dişli İkili Ağaç

Java'da İkili Ağaç Uygulaması

İkili ağacı uygulamanın birçok yolu vardır. Bu bölümde LinkedList veri yapısını kullanarak ikili ağaç gerçekleştireceğiz. Bununla birlikte, geçiş sıralarını da uygulayacağız, bir düğüm arayacağız ve ikili ağaca bir düğüm ekleyeceğiz.

LinkedList Kullanarak İkili Ağacın Uygulanması

Algoritma

Üç nitelik içeren Node sınıfını tanımlayın: sol ve sağ veriler. Burada sol, düğümün sol çocuğunu, sağ ise düğümün sağ çocuğunu temsil eder.

• Bir düğüm oluşturulduğunda, veriler düğümün veri niteliğine aktarılacak ve hem sol hem de sağ değer null olarak ayarlanacaktır.
• Öznitelik köküne sahip başka bir sınıf tanımlayın.
• Kök, ağacın kök düğümünü temsil eder ve onu null olarak başlatır.

sokmak()ağaca yeni bir düğüm ekleyecek:
• Kökün null olup olmadığını kontrol eder, bu da ağacın boş olduğu anlamına gelir. Yeni düğümü kök olarak ekleyecektir.
• Aksi halde kuyruğa kök ekleyecektir.
• Değişken düğüm mevcut düğümü temsil eder.
• İlk olarak, bir düğümün sol ve sağ çocuğunun olup olmadığını kontrol eder. Evetse, her iki düğümü de sıraya ekleyecektir.
• Sol çocuk mevcut değilse, yeni düğümü sol çocuk olarak ekleyecektir.
• Sol varsa, yeni düğümü sağ alt öğe olarak ekleyecektir.
sırayla()ağacın düğümlerini sırayla gösterecektir.
• Ağacın tamamını kat eder, ardından sol çocuğu, ardından kökü ve ardından sağ çocuğu yazdırır.

BinarySearchTree.java

veri yapısında karma

 public class BinarySearchTree { //Represent the node of binary tree public static class Node{ int data; Node left; Node right; public Node(int data){ //Assign data to the new node, set left and right children to null this.data = data; this.left = null; this.right = null; } } //Represent the root of binary tree public Node root; public BinarySearchTree(){ root = null; } //factorial() will calculate the factorial of given number public int factorial(int num) { int fact = 1; if(num == 0) return 1; else { while(num > 1) { fact = fact * num; num--; } return fact; } } //numOfBST() will calculate the total number of possible BST by calculating Catalan Number for given key public int numOfBST(int key) { int catalanNumber = factorial(2 * key)/(factorial(key + 1) * factorial(key)); return catalanNumber; } public static void main(String[] args) { BinarySearchTree bt = new BinarySearchTree(); //Display total number of possible binary search tree with key 5 System.out.println('Total number of possible Binary Search Trees with given key: ' + bt.numOfBST(5)); } } 

Çıktı:

 Binary tree after insertion 1 Binary tree after insertion 2 1 3 Binary tree after insertion 4 2 5 1 3 Binary tree after insertion 4 2 5 1 6 3 7 

İkili Ağaç İşlemleri

Bir ikili ağaçta aşağıdaki işlemler gerçekleştirilebilir:

• Ekleme
• Silme
• Aramak
• Geçiş

İkili Ağaca Düğüm Eklemek için Java Programı

BinaryTreeInsert.java

 public class BinaryTreeInsert { public static void main(String[] args) { new BinaryTreeInsert().run(); } static class Node { Node left; Node right; int value; public Node(int value) { this.value = value; } } public void run() { Node rootnode = new Node(25); System.out.println('Building tree with root value ' + rootnode.value); System.out.println('================================='); insert(rootnode, 11); insert(rootnode, 15); insert(rootnode, 16); insert(rootnode, 23); insert(rootnode, 79); } public void insert(Node node, int value) { if (value node.value) { if (node.right != null) { insert(node.right, value); } else { System.out.println(' Inserted ' + value + ' to right of Node ' + node.value); node.right = new Node(value); } } } } 

Çıktı:

 Building tree with root value 25 ================================= Inserted 11 to left of Node 25 Inserted 15 to right of Node 11 Inserted 16 to right of Node 15 Inserted 23 to right of Node 16 Inserted 79 to right of Node 25 

Java'da Bir Düğümü Silmek için Java Programı

Algoritma

1. Kökten başlayarak ikili ağaçtaki en derin ve en sağdaki düğümü ve silmek istediğimiz düğümü bulun.
2. En sağdaki en derindeki düğümün verilerini silinecek düğümle değiştirin.
3. Daha sonra en sağdaki en derin düğümü silin.

Aşağıdaki şekli düşünün.

SilNode.java

 import java.util.LinkedList; import java.util.Queue; public class DeleteNode { // A binary tree node has key, pointer to // left child and a pointer to right child static class Node { int key; Node left, right; // Constructor Node(int key) { this.key = key; left = null; right = null; } } static Node root; static Node temp = root; // Inorder traversal of a binary tree static void inorder(Node temp) { if (temp == null) return; inorder(temp.left); System.out.print(temp.key + ' '); inorder(temp.right); } // Function to delete deepest // element in binary tree static void deleteDeepest(Node root, Node delNode) { Queue q = new LinkedList(); q.add(root); Node temp = null; // Do level order traversal until last node while (!q.isEmpty()) { temp = q.peek(); q.remove(); if (temp == delNode) { temp = null; return; } if (temp.right!=null) { if (temp.right == delNode) { temp.right = null; return; } else q.add(temp.right); } if (temp.left != null) { if (temp.left == delNode) { temp.left = null; return; } else q.add(temp.left); } } } // Function to delete given element // in binary tree static void delete(Node root, int key) { if (root == null) return; if (root.left == null && root.right == null) { if (root.key == key) { root=null; return; } else return; } Queue q = new LinkedList(); q.add(root); Node temp = null, keyNode = null; // Do level order traversal until // we find key and last node. while (!q.isEmpty()) { temp = q.peek(); q.remove(); if (temp.key == key) keyNode = temp; if (temp.left != null) q.add(temp.left); if (temp.right != null) q.add(temp.right); } if (keyNode != null) { int x = temp.key; deleteDeepest(root, temp); keyNode.key = x; } } // Driver code public static void main(String args[]) { root = new Node(10); root.left = new Node(11); root.left.left = new Node(7); root.left.right = new Node(12); root.right = new Node(9); root.right.left = new Node(15); root.right.right = new Node(8); System.out.print('Inorder traversal before deletion: '); inorder(root); //node to delete int key = 7; delete(root, key); System.out.print('
Inorder traversal after deletion: '); inorder(root); } } 

Çıktı:

 Inorder traversal before deletion: 7 11 12 10 15 9 8 Inorder traversal after deletion: 8 11 12 10 15 9 

İkili Ağaçta Bir Düğümü Arayan Java Programı

Algoritma

• Üç özelliğe sahip olan Node sınıfını tanımlayın: sol ve sağ veriler. Burada sol, düğümün sol çocuğunu, sağ ise düğümün sağ çocuğunu temsil eder.
• Bir düğüm oluşturulduğunda, veriler düğümün veri niteliğine aktarılacak ve hem sol hem de sağ değer null olarak ayarlanacaktır.
• Kök ve bayrak olmak üzere iki özniteliğe sahip başka bir sınıf tanımlayın.
  1. Kök, ağacın kök düğümünü temsil eder ve onu null olarak başlatır.
  2. Bayrak, verilen düğümün ağaçta mevcut olup olmadığını kontrol etmek için kullanılacaktır. Başlangıçta false olarak ayarlanacaktır.

aramaNode()ikili ağaçta belirli bir düğümü arayacaktır:
• Kökün null olup olmadığını kontrol eder, bu da ağacın boş olduğu anlamına gelir.
• Ağaç boş değilse temp'in verilerini değerle karşılaştırır. Eğer eşitlerse, bayrağı true olarak ayarlayacak ve geri dönecektir.
• SearchNode() işlevini yinelemeli olarak çağırarak sol alt ağaçta gezinin ve değerin sol alt ağaçta mevcut olup olmadığını kontrol edin.
• SearchNode() işlevini yinelemeli olarak çağırarak sağ alt ağaçta gezinin ve değerin sağ alt ağaçta mevcut olup olmadığını kontrol edin.

AramaBinaryTree.java

 public class SearchBinaryTree { //Represent a node of binary tree public static class Node { int data; Node left; Node right; public Node(int data) { //Assign data to the new node, set left and right children to null this.data = data; this.left = null; this.right = null; } } //Represent the root of binary tree public Node root; public static boolean flag = false; public SearchBinaryTree() { root = null; } //searchNode() will search for the particular node in the binary tree public void searchNode(Node temp, int value) { //Check whether tree is empty if(root == null) { System.out.println('Tree is empty'); } else { //If value is found in the given binary tree then, set the flag to true if(temp.data == value) { flag = true; return; } //Search in left subtree if(flag == false && temp.left != null) { searchNode(temp.left, value); } //Search in right subtree if(flag == false && temp.right != null) { searchNode(temp.right, value); } } } public static void main(String[] args) { SearchBinaryTree bt = new SearchBinaryTree(); //Add nodes to the binary tree bt.root = new Node(11); bt.root.left = new Node(8); bt.root.right = new Node(12); bt.root.left.left = new Node(78); bt.root.right.left = new Node(23); bt.root.right.right = new Node(36); //Search for node 5 in the binary tree bt.searchNode(bt.root, 23); if(flag) System.out.println('Element is present in the binary tree.'); else System.out.println('Element is not present in the binary tree.'); } } 

Çıktı:

 Element is present in the binary tree. 

İkili Ağaç Geçişi

Not: Yukarıdaki üç geçişin dışında, sınır geçişi adı verilen başka bir geçiş sırası daha vardır.

Sıralama, Ön Sipariş ve Sipariş Sonrası Geçişi Yönlendiren Java Programı

BinaryTree.java

 public class BinaryTree { // first node private Node root; BinaryTree() { root = null; } // Class representing tree nodes static class Node { int value; Node left; Node right; Node(int value) { this.value = value; left = null; right = null; } public void displayData() { System.out.print(value + ' '); } } public void insert(int i) { root = insert(root, i); } //Inserting node - recursive method public Node insert(Node node, int value) { if(node == null){ return new Node(value); } // Move to the left if passed value is // less than the current node if(value node.value) { node.right = insert(node.right, value); } return node; } // Search node in binary search tree public Node find(int searchedValue) { Node current = root; while(current.value != searchedValue) { if(searchedValue = current = current.right; if(current == null) { return null; } } return current; } // For traversing in order public void inOrder(Node node) { if(node != null) { inOrder(node.left); node.displayData(); inOrder(node.right); } } // Preorder traversal public void preOrder(Node node) { if(node != null){ node.displayData(); preOrder(node.left); preOrder(node.right); } } // Postorder traversal public void postOrder(Node node) { if(node != null) { postOrder(node.left); postOrder(node.right); node.displayData(); } } public static void main(String[] args) { BinaryTree bst = new BinaryTree(); bst.insert(34); bst.insert(56); bst.insert(12); bst.insert(89); bst.insert(67); bst.insert(90); System.out.println('Inorder traversal of binary tree'); bst.inOrder(bst.root); System.out.println(); System.out.println('Preorder traversal of binary tree'); bst.preOrder(bst.root); System.out.println(); System.out.println('Postorder traversal of binary tree'); bst.postOrder(bst.root); System.out.println(); } } 

Çıktı:

 Inorder traversal of binary tree 12 34 56 67 89 90 Preorder traversal of binary tree 34 12 56 89 67 90 Postorder traversal of binary tree 12 67 90 89 56 34 

Yukarıdaki işlemlerin yanı sıra büyük düğüm, en küçük düğüm, tüm düğümlerin toplamı gibi işlemleri de gerçekleştirebiliyoruz.

İkili Ağaçtaki En Büyük Düğümü Bulan Java Programı

LargestNode.java

 public class LargestNode { //Represent the node of binary tree public static class Node { int data; Node left; Node right; public Node(int data) { //Assign data to the new node, set left and right children to null this.data = data; this.left = null; this.right = null; } } //Represent the root of binary tree public Node root; public LargestNode() { root = null; } //largestElement() will find out the largest node in the binary tree public int largestElement(Node temp) { //Check whether tree is empty if(root == null) { System.out.println('Tree is empty'); return 0; } else { int leftMax, rightMax; //Max will store temp's data int max = temp.data; //It will find largest element in left subtree if(temp.left != null){ leftMax = largestElement(temp.left); //Compare max with leftMax and store greater value into max max = Math.max(max, leftMax); } //It will find largest element in right subtree if(temp.right != null){ rightMax = largestElement(temp.right); //Compare max with rightMax and store greater value into max max = Math.max(max, rightMax); } return max; } } public static void main(String[] args) { LargestNode bt = new LargestNode(); //Add nodes to the binary tree bt.root = new Node(90); bt.root.left = new Node(99); bt.root.right = new Node(23); bt.root.left.left = new Node(96); bt.root.right.left = new Node(45); bt.root.right.right = new Node(6); bt.root.right.left = new Node(13); bt.root.right.right = new Node(77); //Display largest node in the binary tree System.out.println('Largest element in the binary tree: ' + bt.largestElement(bt.root)); } } 

Çıktı:

 Largest element in the binary tree: 99 

İkili Ağaçtaki En Küçük Düğümü Bulan Java Programı

Algoritma

1. Üç özelliğe sahip olan Node sınıfını tanımlayın: veri, sol ve sağ. Burada sol, düğümün sol çocuğunu, sağ ise düğümün sağ çocuğunu temsil eder.
2. Bir düğüm oluşturulduğunda, veriler düğümün veri niteliğine aktarılacak ve hem sol hem de sağ değer null olarak ayarlanacaktır.
3. Öznitelik köküne sahip başka bir sınıf tanımlayın.
   Kökağacın kök düğümünü temsil eder ve onu null olarak başlatır.

en küçükElement()ikili ağaçtaki en küçük düğümü bulacaktır:
1. olup olmadığını kontrol eder kök boş , bu da ağacın boş olduğu anlamına gelir.
2. Ağaç boş değilse temp verilerini saklayacak bir min değişkeni tanımlayın.
3. En küçükElement() yöntemini yinelemeli olarak çağırarak sol alt ağaçtaki minimum düğümü bulun. Bu değeri leftMin'de saklayın. Min'in değerini leftMin ile karşılaştırın ve minimum ikiyi min'e saklayın.
4. En küçükElement() yöntemini yinelemeli olarak çağırarak sağ alt ağaçtaki minimum düğümü bulun. Bu değeri rightMin'de saklayın. Min değerini rightMin ile karşılaştırın ve maksimum ikiyi min'e saklayın.
5. Sonunda min ikili ağaçtaki en küçük düğümü tutacaktır.

En KüçükNode.java

 public class SmallestNode { //Represent the node of binary tree public static class Node { int data; Node left; Node right; public Node(int data) { //Assign data to the new node, set left and right children to null this.data = data; this.left = null; this.right = null; } } //Represent the root of binary tree public Node root; public SmallestNode() { root = null; } //smallestElement() will find out the smallest node in the binary tree public int smallestElement(Node temp) { //Check whether tree is empty if(root == null) { System.out.println('Tree is empty'); return 0; } else { int leftMin, rightMin; //Min will store temp's data int min = temp.data; //It will find smallest element in left subtree if(temp.left != null) { leftMin = smallestElement(temp.left); //If min is greater than leftMin then store the value of leftMin into min min = Math.min(min, leftMin); } //It will find smallest element in right subtree if(temp.right != null) { rightMin = smallestElement(temp.right); //If min is greater than rightMin then store the value of rightMin into min min = Math.min(min, rightMin); } return min; } } public static void main(String[] args) { SmallestNode bt = new SmallestNode(); //Add nodes to the binary tree bt.root = new Node(9); bt.root.left = new Node(5); bt.root.right = new Node(7); bt.root.left.left = new Node(1); bt.root.right.left = new Node(2); bt.root.right.right = new Node(8); bt.root.right.left = new Node(4); bt.root.right.right = new Node(3); //Display smallest node in the binary tree System.out.println('Smallest element in the binary tree: ' + bt.smallestElement(bt.root)); } } 

Çıktı:

 Smallest element in the binary tree: 1 

İkili Ağacın Maksimum Genişliğini Bulan Java Programı

Algoritma

1. Üç özelliğe sahip olan Node sınıfını tanımlayın: sol ve sağ veriler. Burada sol, düğümün sol çocuğunu, sağ ise düğümün sağ çocuğunu temsil eder.
2. Bir düğüm oluşturulduğunda, veriler düğümün veri niteliğine aktarılacak ve hem sol hem de sağ değer null olarak ayarlanacaktır.
3. Öznitelik köküne sahip başka bir sınıf tanımlayın.
   Kökağacın kök düğümünü temsil eder ve onu null olarak başlatır.

1. maxWidth değişkeni herhangi bir düzeyde mevcut olan maksimum düğüm sayısını saklar.
2. Kuyruk, ikili ağacın seviye bazında geçiş yapması için kullanılır.
3. Kökün null olup olmadığını kontrol eder, bu da ağacın boş olduğu anlamına gelir.
4. Değilse kök düğümü sıraya ekleyin. Değişken nodeInLevel, her düzeydeki düğüm sayısını takip eder.
5. NodeInLevel > 0 ise, düğümü kuyruğun önünden kaldırın ve sol ve sağ çocuğunu kuyruğa ekleyin. İlk yinelemede, düğüm 1 kaldırılacak ve onun alt düğümleri 2 ve 3 kuyruğa eklenecektir. İkinci yinelemede 2. düğüm kaldırılacak, 4. ve 5. çocukları kuyruğa eklenecek ve bu böyle devam edecek.
6. MaxWidth, max(maxWidth, nodeInLevel) değerini depolayacaktır. Yani herhangi bir zamanda maksimum düğüm sayısını temsil edecektir.
7. Bu, ağacın tüm seviyeleri geçilene kadar devam edecektir.

BinaryTree.java

 import java.util.LinkedList; import java.util.Queue; public class BinaryTree { //Represent the node of binary tree public static class Node { int data; Node left; Node right; public Node(int data) { //Assign data to the new node, set left and right children to null this.data = data; this.left = null; this.right = null; } } //Represent the root of binary tree public Node root; public BinaryTree() { root = null; } //findMaximumWidth() will find out the maximum width of the given binary tree public int findMaximumWidth() { int maxWidth = 0; //Variable nodesInLevel keep tracks of number of nodes in each level int nodesInLevel = 0; //queue will be used to keep track of nodes of tree level-wise Queue queue = new LinkedList(); //Check if root is null, then width will be 0 if(root == null) { System.out.println('Tree is empty'); return 0; } else { //Add root node to queue as it represents the first level queue.add(root); while(queue.size() != 0) { //Variable nodesInLevel will hold the size of queue i.e. number of elements in queue nodesInLevel = queue.size(); //maxWidth will hold maximum width. //If nodesInLevel is greater than maxWidth then, maxWidth will hold the value of nodesInLevel maxWidth = Math.max(maxWidth, nodesInLevel); //If variable nodesInLevel contains more than one node //then, for each node, we'll add left and right child of the node to the queue while(nodesInLevel > 0) { Node current = queue.remove(); if(current.left != null) queue.add(current.left); if(current.right != null) queue.add(current.right); nodesInLevel--; } } } return maxWidth; } public static void main(String[] args) { BinaryTree bt = new BinaryTree(); //Add nodes to the binary tree bt.root = new Node(1); bt.root.left = new Node(2); bt.root.right = new Node(3); bt.root.left.left = new Node(4); bt.root.left.right = new Node(5); bt.root.right.left = new Node(6); bt.root.right.right = new Node(7); bt.root.left.left.left = new Node(8); //Display the maximum width of given tree System.out.println('Maximum width of the binary tree: ' + bt.findMaximumWidth()); } } 

Çıktı:

 Maximum width of the binary tree: 4