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

В този урок ще научите за цялостно двоично дърво и различните му видове. Също така ще намерите работещи примери за цялостно двоично дърво в 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) индекс = елемент в 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

Разбирането на това картографиране на индексите на масиви в позиции на дърво е от решаващо значение за разбирането как работи структурата на данните от купчината и как се използва за реализиране на сортиране на купчини.

Пълни приложения за двоично дърво

  • Структури от данни, базирани на купчина
  • Сортиране на купчини

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