Kompletne drzewo binarne

W tym samouczku dowiesz się o pełnym drzewie binarnym i jego różnych typach. Znajdziesz również działające przykłady pełnego drzewa binarnego w językach C, C ++, Java i Python.

Kompletne drzewo binarne to drzewo binarne, w którym wszystkie poziomy są całkowicie wypełnione, z wyjątkiem możliwie najniższego, który jest wypełniony od lewej.

Pełne drzewo binarne jest jak pełne drzewo binarne, ale ma dwie główne różnice

  1. Wszystkie elementy liści muszą być pochylone w lewo.
  2. Ostatni element liścia może nie mieć odpowiedniego rodzeństwa, tj. Pełne drzewo binarne nie musi być pełnym drzewem binarnym.
Kompletne drzewo binarne

Pełne drzewo binarne a pełne drzewo binarne

Porównanie pełnego drzewa binarnego z pełnym drzewem binarnym Porównanie pełnego drzewa binarnego z pełnym drzewem binarnym Porównanie pełnego drzewa binarnego z pełnym drzewem binarnym Porównanie pełnego drzewa binarnego z pełnym drzewem binarnym

Jak powstaje pełne drzewo binarne?

  1. Wybierz pierwszy element listy, który ma być węzłem głównym. (liczba elementów na poziomie-I: 1) Wybierz pierwszy element jako pierwiastek
  2. Umieść drugi element jako lewe dziecko węzła głównego, a trzeci element jako prawe dziecko. (liczba elementów na poziomie II: 2) 12 jako dziecko lewe i 9 jako dziecko prawe
  3. Umieść następne dwa elementy jako dzieci lewego węzła drugiego poziomu. Ponownie umieść kolejne dwa elementy jako dzieci prawego węzła drugiego poziomu (liczba elementów na poziomie III: 4 elementy).
  4. Powtarzaj, aż dotrzesz do ostatniego elementu. 5 jako lewe dziecko i 6 jako prawe dziecko

Przykłady w Pythonie, Javie 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"; )

Związek między indeksami tablicy a elementem drzewa

Kompletne drzewo binarne ma interesującą właściwość, której możemy użyć do znalezienia dzieci i rodziców dowolnego węzła.

Jeśli indeks dowolnego elementu w tablicy to i, element w indeksie 2i+1stanie się lewym dzieckiem, a element w 2i+2indeksie - prawym dzieckiem. Ponadto element nadrzędny dowolnego elementu o indeksie i jest określany przez dolną granicę (i-1)/2.

Przetestujmy to,

 Lewe dziecko 1 (indeks 0) = element w (2 * 0 + 1) indeks = element w 1 indeksie = 12 Prawe dziecko 1 = element w (2 * 0 + 2) indeks = element w 2 indeksie = 9 Podobnie, Lewe dziecko 12 (indeks 1) = element w (2 * 1 + 1) indeks = element w 3 indeks = 5 Prawe dziecko 12 = element w (2 * 1 + 2) indeks = element w 4 indeks = 6

Potwierdźmy również, że obowiązują reguły wyszukiwania rodzica dowolnego węzła

 Rodzic 9 (pozycja 2) = (2-1) / 2 = ½ = 0,5 ~ 0 indeks = 1 Rodzic rodzic 12 (pozycja 1) = (1-1) / 2 = 0 indeks = 1

Zrozumienie tego odwzorowania indeksów tablic na pozycje drzewa ma kluczowe znaczenie dla zrozumienia, jak działa struktura danych sterty i jak jest wykorzystywana do implementacji sortowania sterty.

Kompletne aplikacje drzewa binarnego

  • Struktury danych oparte na stercie
  • Sortowanie na stosie

Interesujące artykuły...