Pokok Perduaan Lengkap

Dalam tutorial ini, anda akan belajar mengenai pokok binari lengkap dan jenisnya. Anda juga akan mendapat contoh pokok binari lengkap di C, C ++, Java dan Python.

Pokok binari lengkap adalah pokok binari di mana semua peringkat dipenuhi sepenuhnya kecuali mungkin yang paling rendah, yang diisi dari kiri.

Pokok binari lengkap sama seperti pokok binari penuh, tetapi dengan dua perbezaan utama

  1. Semua elemen daun mesti condong ke kiri.
  2. Unsur daun terakhir mungkin tidak mempunyai saudara yang betul iaitu pokok binari yang lengkap tidak harus menjadi pokok binari yang lengkap.
Pokok Perduaan Lengkap

Pokok Perduaan Penuh vs Pokok Perduaan Lengkap

Perbandingan antara pokok binari penuh dan pokok binari lengkap Perbandingan antara pokok binari penuh dan pokok binari lengkap Perbandingan antara pokok binari penuh dan pokok binari lengkap Perbandingan antara pokok binari penuh dan pokok binari lengkap

Bagaimana Pokok Perduaan Lengkap Dicipta?

  1. Pilih elemen pertama senarai yang menjadi simpul akar. (bilangan elemen pada tahap-I: 1) Pilih elemen pertama sebagai root
  2. Letakkan elemen kedua sebagai anak kiri simpul akar dan elemen ketiga sebagai anak kanan. (bilangan elemen pada tahap-II: 2) 12 sebagai anak kiri dan 9 sebagai anak kanan
  3. Letakkan dua elemen seterusnya sebagai anak simpul kiri tahap kedua. Sekali lagi, letakkan dua elemen seterusnya sebagai anak dari simpul kanan tahap kedua (bilangan elemen pada tahap-III: 4) elemen).
  4. Terus ulangi sehingga anda mencapai elemen terakhir. 5 sebagai anak kiri dan 6 sebagai anak kanan

Contoh Python, Java dan C / C ++

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"; )

Hubungan antara indeks array dan elemen pokok

Pokok binari yang lengkap mempunyai harta yang menarik yang boleh kita gunakan untuk mencari anak-anak dan ibu bapa mana-mana nod.

Sekiranya indeks unsur dalam array adalah i, elemen dalam indeks 2i+1akan menjadi anak kiri dan elemen dalam 2i+2indeks akan menjadi anak kanan. Juga, induk bagi mana-mana elemen pada indeks i diberikan oleh batas bawah (i-1)/2.

Mari kita mengujinya,

 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 Begitu juga, 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

Marilah kita juga mengesahkan bahawa peraturan tersebut berlaku untuk mencari ibu bapa sebarang nod

 Ibu bapa 9 (kedudukan 2) = (2-1) / 2 = ½ = 0.5 ~ 0 indeks = 1 Ibu bapa 12 (kedudukan 1) = (1-1) / 2 = 0 indeks = 1

Memahami pemetaan indeks array ke kedudukan pokok sangat penting untuk memahami bagaimana Struktur Data Heap berfungsi dan bagaimana ia digunakan untuk melaksanakan Urutan Heap.

Aplikasi Pohon Perduaan Lengkap

  • Struktur data berdasarkan timbunan
  • Jenis timbunan

Artikel menarik...