Полное двоичное дерево

В этом руководстве вы узнаете о полном двоичном дереве и его различных типах. Также вы найдете рабочие примеры полного двоичного дерева на C, C ++, Java и Python.

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

Полное двоичное дерево похоже на полное двоичное дерево, но с двумя основными отличиями.

  1. Все элементы листа должны наклоняться влево.
  2. У последнего листового элемента может не быть правого брата, т.е. полное двоичное дерево не обязательно должно быть полным двоичным деревом.
Полное двоичное дерево

Полное двоичное дерево против полного двоичного дерева

Сравнение полного двоичного дерева и полного двоичного дерева Сравнение полного двоичного дерева и полного двоичного дерева Сравнение полного двоичного дерева и полного двоичного дерева Сравнение полного двоичного дерева и полного двоичного дерева

Как создается полное двоичное дерево?

  1. Выберите первый элемент списка, который будет корневым узлом. (количество элементов на уровне-I: 1) Выберите первый элемент как корневой
  2. Поместите второй элемент как левый дочерний элемент корневого узла, а третий элемент как правый дочерний элемент. (количество элементов на уровне II: 2) 12 как левый ребенок и 9 как правый ребенок
  3. Поместите следующие два элемента как дочерние по отношению к левому узлу второго уровня. Опять же, поместите следующие два элемента как дочерние по отношению к правому узлу второго уровня (количество элементов на уровне III: 4) элементов).
  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) index = элемент в 1 index = 12 Правый дочерний элемент 1 = элемент в (2 * 0 + 2) index = элемент в 2 index = 9 Аналогично, Левый дочерний элемент 12 (индекс 1) = элемент в (2 * 1 + 1) index = элемент в 3 index = 5 Правый дочерний элемент 12 = элемент в (2 * 1 + 2) index = элемент в 4 index = 6

Также подтвердим, что правила поиска родителя любого узла выполняются.

 Родитель 9 (позиция 2) = (2-1) / 2 = ½ = 0,5 ~ 0 index = 1 Родитель 12 (позиция 1) = (1-1) / 2 = 0 index = 1

Понимание этого сопоставления индексов массива с позициями в дереве имеет решающее значение для понимания того, как работает структура данных кучи и как она используется для реализации сортировки кучи.

Полные приложения двоичного дерева

  • Структуры данных на основе кучи
  • Сортировка кучи

Интересные статьи...