Dalam tutorial ini, Anda akan belajar tentang pohon biner lengkap dan berbagai jenisnya. Selain itu, Anda akan menemukan contoh kerja dari pohon biner lengkap di C, C ++, Java dan Python.
Pohon biner lengkap adalah pohon biner di mana semua level terisi penuh kecuali mungkin yang terendah, yang diisi dari kiri.
Pohon biner lengkap sama seperti pohon biner penuh, tetapi dengan dua perbedaan utama
- Semua elemen daun harus condong ke kiri.
- Elemen daun terakhir mungkin tidak memiliki saudara yang benar, yaitu pohon biner lengkap tidak harus berupa pohon biner penuh.
Pohon Biner Lengkap
Pohon Biner Penuh vs Pohon Biner Lengkap
Perbandingan antara pohon biner penuh dan pohon biner lengkap 
Perbandingan antara pohon biner penuh dan pohon biner lengkap 
Perbandingan antara pohon biner penuh dan pohon biner lengkap 
Perbandingan antara pohon biner penuh dan pohon biner lengkap
Bagaimana Pohon Biner Lengkap Dibuat?
- Pilih elemen pertama dari daftar untuk menjadi simpul akar. (jumlah elemen pada level-I: 1)
Pilih elemen pertama sebagai root - Letakkan elemen kedua sebagai anak kiri dari simpul akar dan elemen ketiga sebagai anak kanan. (jumlah elemen pada level-II: 2)
12 sebagai anak kiri dan 9 sebagai anak kanan - Letakkan dua elemen berikutnya sebagai anak dari simpul kiri tingkat kedua. Sekali lagi, tempatkan dua elemen berikutnya sebagai anak dari simpul kanan dari elemen level kedua (jumlah elemen pada level-III: 4)).
- Terus ulangi sampai Anda mencapai elemen terakhir.
5 sebagai anak kiri dan 6 sebagai anak kanan
Contoh Python, Java dan C / C ++
Python Java 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"; )
Hubungan antara indeks array dan elemen pohon
Pohon biner lengkap memiliki properti menarik yang dapat kita gunakan untuk menemukan anak dan orang tua dari simpul mana pun.
Jika indeks dari salah satu elemen dalam array adalah i, elemen dalam indeks 2i+1akan menjadi anak kiri dan elemen dalam 2i+2indeks akan menjadi anak kanan. Juga, induk dari setiap elemen pada indeks i diberikan oleh batas bawah (i-1)/2.
Mari kita uji,
Anak kiri 1 (indeks 0) = elemen dalam (2 * 0 + 1) indeks = elemen dalam 1 indeks = 12 Anak kanan 1 = elemen dalam (2 * 0 + 2) indeks = elemen dalam 2 indeks = 9 Demikian pula, Anak kiri 12 (indeks 1) = elemen dalam (2 * 1 + 1) indeks = elemen dalam 3 indeks = 5 Anak kanan 12 = elemen dalam (2 * 1 + 2) indeks = elemen dalam 4 indeks = 6
Mari kita juga mengkonfirmasi bahwa aturan berlaku untuk menemukan induk dari sembarang simpul
Induk dari 9 (posisi 2) = (2-1) / 2 = ½ = 0,5 ~ 0 indeks = 1 Induk dari 12 (posisi 1) = (1-1) / 2 = 0 indeks = 1
Memahami pemetaan indeks larik ke posisi pohon ini sangat penting untuk memahami cara kerja Struktur Data Heap dan cara menggunakannya untuk mengimplementasikan Urutan Heap.
Aplikasi Binary Tree Lengkap
- Struktur data berbasis heap
- Jenis tumpukan
