Kompletter Binärbaum

In diesem Tutorial lernen Sie einen vollständigen Binärbaum und seine verschiedenen Typen kennen. Außerdem finden Sie Arbeitsbeispiele für einen vollständigen Binärbaum in C, C ++, Java und Python.

Ein vollständiger Binärbaum ist ein Binärbaum, in dem alle Ebenen vollständig gefüllt sind, mit Ausnahme der möglicherweise niedrigsten, die von links gefüllt wird.

Ein vollständiger Binärbaum ist wie ein vollständiger Binärbaum, jedoch mit zwei Hauptunterschieden

  1. Alle Blattelemente müssen sich nach links neigen.
  2. Das letzte Blattelement hat möglicherweise kein richtiges Geschwister, dh ein vollständiger Binärbaum muss kein vollständiger Binärbaum sein.
Kompletter Binärbaum

Vollständiger Binärbaum gegen vollständiger Binärbaum

Vergleich zwischen vollständigem Binärbaum und vollständigem Binärbaum Vergleich zwischen vollständigem Binärbaum und vollständigem Binärbaum Vergleich zwischen vollständigem Binärbaum und vollständigem Binärbaum Vergleich zwischen vollständigem Binärbaum und vollständigem Binärbaum

Wie wird ein vollständiger Binärbaum erstellt?

  1. Wählen Sie das erste Element der Liste als Stammknoten aus. (Anzahl der Elemente auf Ebene I: 1) Wählen Sie das erste Element als Wurzel aus
  2. Setzen Sie das zweite Element als linkes Kind des Wurzelknotens und das dritte Element als rechtes Kind. (Anzahl der Elemente auf Stufe II: 2) 12 als linkes Kind und 9 als rechtes Kind
  3. Fügen Sie die nächsten beiden Elemente als untergeordnete Elemente des linken Knotens der zweiten Ebene ein. Setzen Sie die nächsten beiden Elemente erneut als untergeordnete Elemente des rechten Knotens der Elemente der zweiten Ebene (Anzahl der Elemente auf Ebene III: 4).
  4. Wiederholen Sie diesen Vorgang, bis Sie das letzte Element erreicht haben. 5 als linkes Kind und 6 als rechtes Kind

Beispiele für Python, Java und 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"; )

Beziehung zwischen Array-Indizes und Baumelement

Ein vollständiger Binärbaum hat eine interessante Eigenschaft, mit der wir die Kinder und Eltern eines beliebigen Knotens finden können.

Wenn der Index eines Elements im Array i ist, wird das Element im Index 2i+1zum linken untergeordneten Element und das Element im 2i+2Index zum rechten untergeordneten Element . Außerdem ist das übergeordnete Element eines Elements am Index i durch die Untergrenze von gegeben (i-1)/2.

Lass es uns testen,

 Linkes Kind von 1 (Index 0) = Element in (2 * 0 + 1) Index = Element in 1 Index = 12 Rechtes Kind von 1 = Element in (2 * 0 + 2) Index = Element in 2 Index = 9 Ähnlich Linkes Kind von 12 (Index 1) = Element in (2 * 1 + 1) Index = Element in 3 Index = 5 Rechtes Kind von 12 = Element in (2 * 1 + 2) Index = Element in 4 Index = 6

Lassen Sie uns auch bestätigen, dass die Regeln für die Suche nach Eltern eines Knotens gelten

 Elternteil von 9 (Position 2) = (2-1) / 2 = ½ = 0,5 ~ 0 Index = 1 Elternteil von 12 (Position 1) = (1-1) / 2 = 0 Index = 1

Das Verständnis dieser Zuordnung von Array-Indizes zu Baumpositionen ist entscheidend für das Verständnis der Funktionsweise der Heap-Datenstruktur und der Verwendung zur Implementierung der Heap-Sortierung.

Vollständige Binärbaumanwendungen

  • Heap-basierte Datenstrukturen
  • Haufen sortieren

Interessante Beiträge...