Voltooi binaire structuur

In deze tutorial leer je over een complete binaire boom en zijn verschillende typen. Ook vindt u werkende voorbeelden van een complete binaire boom in C, C ++, Java en Python.

Een complete binaire boom is een binaire boom waarin alle niveaus volledig zijn gevuld, behalve mogelijk de laagste, die van links wordt gevuld.

Een complete binaire boom is net als een volledige binaire boom, maar met twee grote verschillen

  1. Alle bladelementen moeten naar links leunen.
  2. Het laatste leaf-element heeft misschien geen goede broer of zus, dwz een complete binaire boom hoeft geen volledige binaire boom te zijn.
Voltooi binaire structuur

Volledige binaire boom versus volledige binaire boom

Vergelijking tussen volledige binaire boom en volledige binaire boom Vergelijking tussen volledige binaire boom en volledige binaire boom Vergelijking tussen volledige binaire boom en volledige binaire boom Vergelijking tussen volledige binaire boom en volledige binaire boom

Hoe wordt een complete binaire structuur gemaakt?

  1. Selecteer het eerste element van de lijst als hoofdknooppunt. (aantal elementen op niveau-I: 1) Selecteer het eerste element als wortel
  2. Zet het tweede element als een linkerkind van het wortelknooppunt en het derde element als het rechterkind. (aantal elementen op niveau II: 2) 12 als linkerkind en 9 als rechterkind
  3. Zet de volgende twee elementen als kinderen van het linkerknooppunt van het tweede niveau. Plaats opnieuw de volgende twee elementen als kinderen van het rechterknooppunt van het tweede niveau (aantal elementen op niveau III: 4) elementen).
  4. Blijf herhalen totdat je het laatste element hebt bereikt. 5 als linkerkind en 6 als rechtskind

Python, Java en C / C ++ voorbeelden

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

Relatie tussen array-indexen en boomelement

Een complete binaire boom heeft een interessante eigenschap die we kunnen gebruiken om de kinderen en ouders van elk knooppunt te vinden.

Als de index van een element in de array i is, wordt het element in de index 2i+1het linkerkind en het element in de 2i+2index het rechterkind. Ook wordt de ouder van elk element op index i gegeven door de ondergrens van (i-1)/2.

Laten we het uittesten,

 Linker child van 1 (index 0) = element in (2 * 0 + 1) index = element in 1 index = 12 Rechter child van 1 = element in (2 * 0 + 2) index = element in 2 index = 9 Evenzo, Linker child van 12 (index 1) = element in (2 * 1 + 1) index = element in 3 index = 5 Rechter child van 12 = element in (2 * 1 + 2) index = element in 4 index = 6

Laten we ook bevestigen dat de regels gelden voor het vinden van een ouder van een knooppunt

 Ouder van 9 (positie 2) = (2-1) / 2 = ½ = 0,5 ~ 0 index = 1 Ouder van 12 (positie 1) = (1-1) / 2 = 0 index = 1

Het begrijpen van deze toewijzing van array-indexen aan boomposities is van cruciaal belang om te begrijpen hoe de Heap-gegevensstructuur werkt en hoe deze wordt gebruikt om Heap Sort te implementeren.

Voltooi binaire boomtoepassingen

  • Heap-gebaseerde datastructuren
  • Heap sorteren

Interessante artikelen...