Kompletný binárny strom

V tomto výučbe sa dozviete o úplnom binárnom strome a jeho rôznych druhoch. Nájdete tiež pracovné príklady kompletného binárneho stromu v jazykoch C, C ++, Java a Python.

Úplný binárny strom je binárny strom, v ktorom sú úplne vyplnené všetky úrovne, okrem možno najnižšej, ktorá je vyplnená zľava.

Úplný binárny strom je ako úplný binárny strom, má však dva hlavné rozdiely

  1. Všetky listové prvky sa musia nakláňať doľava.
  2. Prvok posledného listu nemusí mať správneho súrodenca, tj úplný binárny strom nemusí byť úplným binárnym stromom.
Kompletný binárny strom

Plný binárny strom vs úplný binárny strom

Porovnanie úplného binárneho stromu a úplného binárneho stromu Porovnanie úplného binárneho stromu a úplného binárneho stromu Porovnanie úplného binárneho stromu a úplného binárneho stromu Porovnanie úplného binárneho stromu a úplného binárneho stromu

Ako sa vytvára kompletný binárny strom?

  1. Vyberte prvý prvok zo zoznamu, ktorý bude koreňovým uzlom. (počet prvkov na úrovni I: 1) Vyberte prvý prvok ako root
  2. Vložte druhý prvok ako ľavé dieťa koreňového uzla a tretí prvok ako pravé dieťa. (počet prvkov na úrovni II: 2) 12 ako ľavé dieťa a 9 ako pravé dieťa
  3. Dajte ďalšie dva prvky ako deti do ľavého uzla druhej úrovne. Opäť dajte ďalšie dva prvky ako deti pravého uzla druhej úrovne (počet prvkov na úrovni III: 4) prvkov).
  4. Stále opakujte, kým nedosiahnete posledný prvok. 5 ako ľavé dieťa a 6 ako pravé dieťa

Príklady jazyka Python, Java a 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"; )

Vzťah medzi indexmi poľa a prvkom stromu

Kompletný binárny strom má zaujímavú vlastnosť, pomocou ktorej môžeme nájsť deti a rodičov ktoréhokoľvek uzla.

Ak je index ľubovoľného prvku v poli i, prvok v indexe 2i+1sa stane ľavým potomkom a prvok v 2i+2indexe sa stane pravým potomkom. Nadradený prvok ľubovoľného prvku v indexe i je tiež daný dolnou hranicou (i-1)/2.

Poďme to vyskúšať

 Ľavé dieťa z 1 (index 0) = prvok v (2 * 0 + 1) index = prvok v 1 index = 12 Pravé dieťa z 1 = prvok v (2 * 0 + 2) index = prvok v 2 index = 9 Podobne, Ľavé dieťa 12 (index 1) = prvok v (2 * 1 + 1) index = prvok v 3 index = 5 Pravé dieťa 12 = prvok v (2 * 1 + 2) index = prvok v 4 index = 6

Potvrdíme tiež, že pravidlá platia pre vyhľadanie rodiča ktoréhokoľvek uzla

 Rodič 9 (pozícia 2) = (2-1) / 2 = ½ = 0,5 ~ 0 index = 1 Rodič 12 (pozícia 1) = (1-1) / 2 = 0 index = 1

Pochopenie tohto mapovania indexov polí na pozície stromov je zásadné pre pochopenie toho, ako funguje dátová štruktúra haldy a ako sa používa na implementáciu triedenia haldy.

Kompletné aplikácie binárnych stromov

  • Haldové dátové štruktúry
  • Hromadné triedenie

Zaujímavé články...