Kompletno binarno stablo

U ovom uputstvu naučit ćete o cjelovitom binarnom stablu i njegovim različitim vrstama. Također ćete naći radne primjere cjelovitog binarnog stabla u C, C ++, Java i Python.

Potpuno binarno stablo je binarno stablo u kojem su sve razine potpuno ispunjene, osim moguće najniže, koje se popunjava slijeva.

Kompletno binarno stablo je poput punog binarnog stabla, ali s dvije glavne razlike

  1. Svi elementi lista moraju se naginjati lijevo.
  2. Posljednji element lista možda nema pravog brata ili sestru, tj. Cjelovito binarno stablo ne mora biti potpuno binarno stablo.
Kompletno binarno stablo

Potpuno binarno stablo vs Kompletno binarno stablo

Usporedba punog binarnog stabla i cjelovitog binarnog stabla Usporedba punog binarnog stabla i cjelovitog binarnog stabla Usporedba punog binarnog stabla i cjelovitog binarnog stabla Usporedba punog binarnog stabla i cjelovitog binarnog stabla

Kako se stvara cjelovito binarno stablo?

  1. Odaberite prvi element popisa koji će biti korijenski čvor. (broj elemenata na razini I: 1) Odaberite prvi element kao korijen
  2. Stavite drugi element kao lijevo dijete korijenskog čvora, a treći element kao desno dijete. (broj elemenata na razini II: 2) 12 kao lijevo dijete i 9 kao desno dijete
  3. Sljedeća dva elementa stavite kao djeca lijevog čvora druge razine. Ponovno stavite sljedeća dva elementa kao podređena tijela desnog čvora druge razine (broj elemenata na razini III-4: 4).
  4. Ponavljajte dok ne dođete do posljednjeg elementa. 5 kao lijevo dijete i 6 kao desno dijete

Primjeri Pythona, Java i 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"; )

Veza između indeksa niza i elementa stabla

Kompletno binarno stablo ima zanimljivo svojstvo pomoću kojeg možemo pronaći djecu i roditelje bilo kojeg čvora.

Ako je indeks bilo kojeg elementa u nizu i, element u indeksu 2i+1postat će lijevo dijete, a element u 2i+2indeksu postat će desno dijete. Također, roditelj bilo kojeg elementa u indeksu i dat je donjom granicom (i-1)/2.

Isprobajmo,

 Lijevo dijete 1 (indeks 0) = element u (2 * 0 + 1) indeks = element u 1 indeksu = 12 Desno dijete 1 = element u (2 * 0 + 2) indeks = element u 2 indeks = 9 Slično tome, Lijevo dijete od 12 (indeks 1) = element u (2 * 1 + 1) indeks = element u 3 indeks = 5 Desno dijete od 12 = element u (2 * 1 + 2) indeks = element u 4 indeks = 6

Potvrdimo također da vrijede pravila za pronalaženje roditelja bilo kojeg čvora

 Roditelj od 9 (položaj 2) = (2-1) / 2 = ½ = 0,5 ~ 0 indeks = 1 Roditelj od 12 (položaj 1) = (1-1) / 2 = 0 indeks = 1

Razumijevanje ovog mapiranja indeksa nizova na položaje stabla presudno je za razumijevanje kako funkcionira struktura podataka hrpe i kako se koristi za implementaciju sortiranja hrpe.

Kompletne aplikacije binarnog stabla

  • Strukture podataka temeljene na hrpi
  • Razvrstavanje hrpe

Zanimljivi članci...