Повне бінарне дерево

У цьому підручнику ви дізнаєтесь про повне бінарне дерево та його різні типи. Крім того, ви знайдете робочі приклади повного бінарного дерева на C, C ++, Java та Python.

Повне бінарне дерево - це бінарне дерево, в якому всі рівні заповнені повністю, за винятком, можливо, найнижчого, яке заповнюється зліва.

Повне двійкове дерево подібне до повного двійкового дерева, але з двома основними відмінностями

Всі елементи листя повинні нахилятися вліво.
Останній елемент листя може не мати правильного брата, тобто повне двійкове дерево не повинно бути повним двійковим деревом.

Повне бінарне дерево

Повне двійкове дерево проти Повне двійкове дерево

Порівняння повного бінарного дерева та повного бінарного дерева

Як створюється повне бінарне дерево?

Виберіть перший елемент списку, який буде кореневим вузлом. (кількість елементів на рівні I: 1) Виберіть перший елемент як кореневий
Помістіть другий елемент як лівий дочірній елемент кореневого вузла, а третій елемент - як правий дочірній елемент. (кількість елементів на рівні II: 2) 12 як ліва дитина та 9 як права дитина
Помістіть наступні два елементи як дочірні елементи лівого вузла другого рівня. Знову ж таки, поставте наступні два елементи як дочірні елементи правого вузла другого рівня (кількість елементів на рівні III: 4).
Продовжуйте повторювати, поки не дійдете до останнього елемента. 5 як ліва дитина і 6 як права дитина

Приклади Python, Java та 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"; )

Зв'язок між індексами масиву та елементом дерева

Повне двійкове дерево має цікаву властивість, за допомогою якої ми можемо знайти дітей та батьків будь-якого вузла.

Якщо індекс будь-якого елемента в масиві дорівнює i, елемент в індексі 2i+1стане лівим дочірнім елементом, а елемент в 2i+2індексі - правильним дочірнім. Крім того, батьківський елемент будь-якого елемента з індексом i задається нижньою межею (i-1)/2.

Давайте перевіримо це,

 Лівий дочірній елемент 1 (індекс 0) = елемент у (2 * 0 + 1) індекс = елемент в 1 індекс = 12 Правий дочірній елемент 1 = елемент у (2 * 0 + 2) індекс = елемент у 2 індекс = 9 Аналогічно, Ліва дочірня частина 12 (індекс 1) = елемент у (2 * 1 + 1) індекс = елемент у 3 індекс = 5 Права дочірня частина 12 = елемент у (2 * 1 + 2) індекс = елемент у 4 індекс = 6

Давайте також підтвердимо, що правила діють для пошуку батьків будь-якого вузла

 Батько 9 (позиція 2) = (2-1) / 2 = ½ = 0,5 ~ 0 індекс = 1 Батько 12 (позиція 1) = (1-1) / 2 = 0 індекс = 1

Розуміння цього зіставлення індексів масиву з позиціями дерева є критичним для розуміння того, як працює структура даних кучі та як вона використовується для реалізації сортування купи.