Arborele binar complet

În acest tutorial, veți afla despre un arbore binar complet și diferitele sale tipuri. De asemenea, veți găsi exemple de lucru ale unui arbore binar complet în C, C ++, Java și Python.

Un copac binar complet este un copac binar în care toate nivelurile sunt complet umplute, cu excepția celui mai mic, care este umplut din stânga.

Un copac binar complet este la fel ca un copac binar complet, dar cu două diferențe majore

  1. Toate elementele frunzei trebuie să se aplece spre stânga.
  2. Este posibil ca ultimul element frunză să nu aibă un frate potrivit, adică un copac binar complet nu trebuie să fie un copac binar complet.
Arborele binar complet

Arborele binar complet vs Arborele binar complet

Comparație între copac complet binar și copac complet binar Comparație între copac complet binar și copac complet binar Comparație între copac complet binar și copac complet binar Comparație între copac complet binar și copac complet binar

Cum se creează un arbore binar complet?

  1. Selectați primul element al listei pentru a fi nodul rădăcină. (nr. de elemente la nivelul I: 1) Selectați primul element ca rădăcină
  2. Puneți al doilea element ca un copil stâng al nodului rădăcină și al treilea element ca copilul drept. (nr. de elemente la nivelul II: 2) 12 ca un copil stâng și 9 ca un copil drept
  3. Puneți următoarele două elemente ca copii ai nodului stâng al celui de-al doilea nivel. Din nou, puneți următoarele două elemente ca fiind copii ai nodului drept al celui de-al doilea nivel (numărul de elemente de la nivelul III: 4) elemente).
  4. Repetați până ajungeți la ultimul element. 5 ca un copil stâng și 6 ca un copil drept

Exemple Python, 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"; )

Relația dintre indicii matrice și elementul arbore

Un copac binar complet are o proprietate interesantă pe care o putem folosi pentru a găsi copiii și părinții oricărui nod.

Dacă indexul oricărui element din matrice este i, elementul din index 2i+1va deveni copilul stâng și elementul din 2i+2index va deveni copilul potrivit. De asemenea, părintele oricărui element de la indexul i este dat de limita inferioară a (i-1)/2.

Să testăm,

 Copilul stâng al 1 (index 0) = element în (2 * 0 + 1) index = element în 1 index = 12 Fig. Dreapta al 1 = element în (2 * 0 + 2) index = element în 2 index = 9 În mod similar, Copil stâng de 12 (index 1) = element în (2 * 1 + 1) index = element în 3 index = 5 Copil drept din 12 = element în (2 * 1 + 2) index = element în 4 index = 6

Să confirmăm, de asemenea, că regulile sunt valabile pentru găsirea părintelui oricărui nod

 Părinte de 9 (poziția 2) = (2-1) / 2 = ½ = 0,5 ~ 0 index = 1 Părinte de 12 (poziția 1) = (1-1) / 2 = 0 index = 1

Înțelegerea acestei mapări a indexurilor matrice în pozițiile arborelui este esențială pentru înțelegerea modului în care funcționează structura de date Heap și modul în care este utilizată pentru a implementa sortarea Heap.

Aplicații complete pentru arborele binar

  • Structuri de date bazate pe heap
  • Sortare grămadă

Articole interesante...