Täielik binaarne puu

Selles õpetuses saate teada täieliku binaarse puu ja selle eri tüüpide kohta. Samuti leiate C, C ++, Java ja Pythoni täieliku binaarse puu toimivaid näiteid.

Täielik kahendpuu on kahendpuu, milles kõik tasandid on täielikult täidetud, välja arvatud kõige madalam, mis on täidetud vasakult.

Täielik binaarne puu on täpselt nagu täielik binaarne puu, kuid sellel on kaks suurt erinevust

  1. Kõik leheelemendid peavad kalduma vasakule.
  2. Viimasel leheelemendil ei pruugi olla õiget õde-venda, st täielik kahendpuu ei pea olema täielik kahendpuu.
Täielik binaarne puu

Täielik kahendpuu vs täielik kahendpuu

Täisbinaarse puu ja täieliku kahendpuu võrdlus Täisbinaarse puu ja täieliku kahendpuu võrdlus Täisbinaarse puu ja täieliku binaarpuu võrdlus Täisbinaarse puu ja täieliku binaarpuu võrdlus

Kuidas luuakse täielik binaarne puu?

  1. Valige loendi esimene element juursõlm. (elementide arv I tasemel: 1) Valige juurena esimene element
  2. Pange teine ​​element juursõlme vasakule lapsele ja kolmas element paremale lapsele. (II taseme elementide arv: 2) 12 vasakpoolse ja 9 parema lapsena
  3. Pange järgmised kaks elementi teise taseme vasaku sõlme lastena. Jällegi pange järgmised kaks elementi teise taseme parempoolse sõlme (elementide arv III tasandil: 4) elementide lastena.
  4. Korrake, kuni jõuate viimase elemendini. 5 vasaku ja 6 parema lapsena

Pythoni, Java ja C / C ++ näited

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

Massiivindeksite ja puuelemendi suhe

Täielikul binaarsel puul on huvitav omadus, mida saame kasutada mis tahes sõlme laste ja vanemate leidmiseks.

Kui massiivi mis tahes elemendi indeks on i, saab indeksi 2i+1elemendist vasak laps ja 2i+2indeksi elemendist parem laps. Indeksi i mis tahes elemendi vanema annab ka alumine piir (i-1)/2.

Proovime seda,

 1 vasak laps (indeks 0) = element (2 * 0 + 1) indeksis = element 1 indeksis = 12 1 parempoolne laps = indeksi (2 * 0 + 2) element = indeksi 2 indeks = 9 Samamoodi Vasak 12-aastane laps (indeks 1) = element (2 * 1 + 1) indeksis = element 3-s indeksis = 5 Parem 12-aastane laps = element (2 * 1 + 2) indeksis = element 4-s

Kinnitagem ka seda, et reeglid kehtivad mis tahes sõlme vanema leidmiseks

 9 lapse vanem (positsioon 2) = (2-1) / 2 = ½ = 0,5 ~ 0 indeks = 1 12 lapse vanem (positsioon 1) = (1-1) / 2 = 0 indeks = 1

Massiivindeksite puupositsioonidele vastendamise mõistmine on ülioluline, et mõista, kuidas kuhja andmestruktuur töötab ja kuidas seda kasutatakse kuhja sortimise rakendamiseks.

Täielik binaarpuu rakendused

  • Kuhjal põhinevad andmestruktuurid
  • Hunnik sort

Huvitavad Artiklid...