Bu eğitimde, tam bir ikili ağaç ve onun farklı türleri hakkında bilgi edineceksiniz. Ayrıca, C, C ++, Java ve Python'da eksiksiz bir ikili ağacın çalışma örneklerini bulacaksınız.
Tam bir ikili ağaç, soldan doldurulmuş, muhtemelen en alttaki hariç tüm seviyelerin tamamen doldurulduğu bir ikili ağaçtır.
Tam bir ikili ağaç, tam bir ikili ağaç gibidir, ancak iki büyük fark vardır
- Tüm yaprak elemanları sola doğru eğilmelidir.
- Son yaprak öğesinin bir doğru kardeşi olmayabilir, yani tam bir ikili ağacın tam bir ikili ağaç olması gerekmez.
Tam İkili Ağaç
Full Binary Tree vs Complete Binary Tree
Tam ikili ağaç ile tam ikili ağaç arasında karşılaştırma Tam ikili ağaç ile tam ikili ağaç 
arasında karşılaştırma Tam ikili ağaç ile tam ikili ağaç 
arasında karşılaştırma Tam ikili ağaç ile tam ikili ağaç 
arasında karşılaştırma
Tam Bir İkili Ağaç Nasıl Oluşturulur?
- Listenin ilk öğesini kök düğüm olarak seçin. (seviye I'deki
öğe sayısı : 1) İlk öğeyi kök olarak seçin - İkinci öğeyi kök düğümün sol çocuğu ve üçüncü öğeyi sağ alt öğe olarak koyun. (II. düzeydeki öğe sayısı: 2)
Sol çocuk olarak 12 ve sağ çocuk olarak 9 - Sonraki iki öğeyi ikinci seviyenin sol düğümünün çocukları olarak koyun. Yine, sonraki iki öğeyi ikinci seviyenin sağ düğümünün çocukları olarak koyun (seviye III: 4'teki eleman sayısı).
- Son öğeye ulaşana kadar tekrar etmeye devam edin.
Sol çocuk olarak 5 ve sağ çocuk olarak 6
Python, Java ve C / C ++ Örnekleri
Python Java C C ++ # Checking if a binary tree is a complete binary tree in C class Node: def __init__(self, item): self.item = item self.left = None self.right = None # Count the number of nodes def count_nodes(root): if root is None: return 0 return (1 + count_nodes(root.left) + count_nodes(root.right)) # Check if the tree is complete binary tree def is_complete(root, index, numberNodes): # Check if the tree is empty if root is None: return True if index>= numberNodes: return False return (is_complete(root.left, 2 * index + 1, numberNodes) and is_complete(root.right, 2 * index + 2, numberNodes)) root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) root.right.left = Node(6) node_count = count_nodes(root) index = 0 if is_complete(root, index, node_count): print("The tree is a complete binary tree") else: print("The tree is not a complete binary tree")
// Checking if a binary tree is a complete binary tree in Java // Node creation class Node ( int data; Node left, right; Node(int item) ( data = item; left = right = null; ) ) class BinaryTree ( Node root; // Count the number of nodes int countNumNodes(Node root) ( if (root == null) return (0); return (1 + countNumNodes(root.left) + countNumNodes(root.right)); ) // Check for complete binary tree boolean checkComplete(Node root, int index, int numberNodes) ( // Check if the tree is empty if (root == null) return true; if (index>= numberNodes) return false; return (checkComplete(root.left, 2 * index + 1, numberNodes) && checkComplete(root.right, 2 * index + 2, numberNodes)); ) public static void main(String args()) ( BinaryTree tree = new BinaryTree(); tree.root = new Node(1); tree.root.left = new Node(2); tree.root.right = new Node(3); tree.root.left.right = new Node(5); tree.root.left.left = new Node(4); tree.root.right.left = new Node(6); int node_count = tree.countNumNodes(tree.root); int index = 0; if (tree.checkComplete(tree.root, index, node_count)) System.out.println("The tree is a complete binary tree"); else System.out.println("The tree is not a complete binary tree"); ) )
// Checking if a binary tree is a complete binary tree in C #include #include #include struct Node ( int key; struct Node *left, *right; ); // Node creation struct Node *newNode(char k) ( struct Node *node = (struct Node *)malloc(sizeof(struct Node)); node->key = k; node->right = node->left = NULL; return node; ) // Count the number of nodes int countNumNodes(struct Node *root) ( if (root == NULL) return (0); return (1 + countNumNodes(root->left) + countNumNodes(root->right)); ) // Check if the tree is a complete binary tree bool checkComplete(struct Node *root, int index, int numberNodes) ( // Check if the tree is complete if (root == NULL) return true; if (index>= numberNodes) return false; return (checkComplete(root->left, 2 * index + 1, numberNodes) && checkComplete(root->right, 2 * index + 2, numberNodes)); ) int main() ( struct Node *root = NULL; root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); root->right->left = newNode(6); int node_count = countNumNodes(root); int index = 0; if (checkComplete(root, index, node_count)) printf("The tree is a complete binary tree"); else printf("The tree is not a complete binary tree"); )
// Checking if a binary tree is a complete binary tree in C++ #include using namespace std; struct Node ( int key; struct Node *left, *right; ); // Create node struct Node *newNode(char k) ( struct Node *node = (struct Node *)malloc(sizeof(struct Node)); node->key = k; node->right = node->left = NULL; return node; ) // Count the number of nodes int countNumNodes(struct Node *root) ( if (root == NULL) return (0); return (1 + countNumNodes(root->left) + countNumNodes(root->right)); ) // Check if the tree is a complete binary tree bool checkComplete(struct Node *root, int index, int numberNodes) ( // Check if the tree is empty if (root == NULL) return true; if (index>= numberNodes) return false; return (checkComplete(root->left, 2 * index + 1, numberNodes) && checkComplete(root->right, 2 * index + 2, numberNodes)); ) int main() ( struct Node *root = NULL; root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); root->right->left = newNode(6); int node_count = countNumNodes(root); int index = 0; if (checkComplete(root, index, node_count)) cout << "The tree is a complete binary tree"; else cout << "The tree is not a complete binary tree"; )
Dizi dizinleri ve ağaç öğesi arasındaki ilişki
Tam bir ikili ağacın, herhangi bir düğümün çocuklarını ve ebeveynlerini bulmak için kullanabileceğimiz ilginç bir özelliği vardır.
Dizideki herhangi bir öğenin dizini i ise, dizindeki 2i+1öğe sol alt öğe ve 2i+2dizindeki öğe sağ alt öğe olur. Ayrıca, i indeksindeki herhangi bir elemanın ebeveyni alt sınırı ile verilir (i-1)/2.
Hadi deneyelim,
1'in sol çocuğu (dizin 0) = (2 * 0 + 1) dizindeki öğe = 1 dizindeki öğe = 12 1'in sağ alt öğesi = (2 * 0 + 2) dizindeki öğe = 2 dizindeki öğe = 9 Benzer şekilde, 12'nin sol alt öğesi (dizin 1) = (2 * 1 + 1) dizindeki öğe = 3 dizindeki öğe = 5 12'nin sağ çocuğu = (2 * 1 + 2) dizindeki öğe = 4 dizindeki öğe = 6
Herhangi bir düğümün ebeveynini bulmak için kuralların geçerli olduğunu da doğrulayalım
9'un üst öğesi (konum 2) = (2-1) / 2 = ½ = 0,5 ~ 0 dizin = 1 12'nin üst öğesi (konum 1) = (1-1) / 2 = 0 dizin = 1
Dizi dizinlerinin ağaç konumlarıyla bu eşlemesini anlamak, Yığın Veri Yapısının nasıl çalıştığını ve Yığın Sıralamayı uygulamak için nasıl kullanıldığını anlamak için kritik öneme sahiptir.
Komple İkili Ağaç Uygulamaları
- Yığın tabanlı veri yapıları
- Yığın sıralama
