Kompletní binární strom

V tomto kurzu se dozvíte o úplném binárním stromu a jeho různých typech. Také najdete pracovní příklady kompletního binárního stromu v jazycích C, C ++, Java a Python.

Kompletní binární strom je binární strom, ve kterém jsou všechny úrovně zcela vyplněny, s výjimkou nejnižší, která je vyplněna zleva.

Kompletní binární strom je jako úplný binární strom, ale se dvěma hlavními rozdíly

Všechny listové prvky se musí naklánět doleva.
Poslední listový prvek nemusí mít správného sourozence, tj. Úplný binární strom nemusí být úplným binárním stromem.

Kompletní binární strom

Full Binary Tree vs Complete Binary Tree

Porovnání úplného binárního stromu a úplného binárního stromu

Jak je vytvořen kompletní binární strom?

Vyberte první prvek seznamu, který má být kořenovým uzlem. (počet prvků na úrovni I: 1) Vyberte první prvek jako root
Vložte druhý prvek jako levé dítě kořenového uzlu a třetí prvek jako pravé dítě. (počet prvků na úrovni II: 2) 12 jako levé dítě a 9 jako pravé dítě
Umístěte další dva prvky jako podřízené do levého uzlu druhé úrovně. Opět vložte další dva prvky jako podřízené prvky pravého uzlu druhé úrovně (počet prvků na úrovni III: 4) prvků).
Opakujte, dokud nedosáhnete posledního prvku. 5 jako levé dítě a 6 jako pravé dítě

Python, Java a C / C ++ příklady

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

Vztah mezi indexy pole a stromovým prvkem

Kompletní binární strom má zajímavou vlastnost, kterou můžeme použít k vyhledání dětí a rodičů libovolného uzlu.

Pokud je index libovolného prvku v poli i, prvek v indexu 2i+1se stane levým potomkem a prvek v 2i+2indexu se stane pravým potomkem. Nadřazený prvek libovolného prvku v indexu i je dán dolní mezí (i-1)/2.

Pojďme to vyzkoušet

 Levé dítě 1 (index 0) = prvek v (2 * 0 + 1) index = prvek v 1 index = 12 Pravé dítě 1 = prvek v (2 * 0 + 2) index = prvek v 2 index = 9 Podobně Levé dítě 12 (index 1) = prvek v (2 * 1 + 1) index = prvek ve 3 index = 5 Pravé dítě 12 = prvek v (2 * 1 + 2) index = prvek ve 4 index = 6

Potvrďte také, že pravidla platí pro nalezení rodiče kteréhokoli uzlu

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

Pochopení tohoto mapování indexů pole na pozice stromů je zásadní pro pochopení toho, jak funguje halda datová struktura a jak se používá k implementaci třídění haldy.