Комплетно бинарно стабло

У овом упутству ћете научити о комплетном бинарном стаблу и његовим различитим врстама. Такође, наћи ћете радне примере комплетног бинарног стабла на Ц, Ц ++, Јава и Питхон.

Потпуно бинарно стабло је бинарно стабло у којем су сви нивои потпуно попуњени, осим могуће најнижег, који се попуњава с леве стране.

Комплетно бинарно стабло је попут пуног бинарног стабла, али са две главне разлике

  1. Сви елементи листа морају се нагињати лево.
  2. Последњи елемент листа можда нема правог брата или сестру, тј. Комплетно бинарно стабло не мора бити потпуно бинарно стабло.
Комплетно бинарно стабло

Потпуно бинарно стабло вс комплетно бинарно стабло

Поређење пуног бинарног стабла и комплетног бинарног стабла Поређење пуног бинарног стабла и комплетног бинарног стабла Поређење пуног бинарног стабла и комплетног бинарног стабла Поређење пуног бинарног стабла и комплетног бинарног стабла

Како се ствара комплетно бинарно стабло?

  1. Изаберите први елемент листе који ће бити коријенски чвор. (број елемената на нивоу И: 1) Изаберите први елемент као роот
  2. Ставите други елемент као лево дете коријенског чвора, а трећи елемент као десно дете. (број елемената на нивоу ИИ: 2) 12 као лево дете и 9 као десно дете
  3. Следећа два елемента ставите као децу левог чвора другог нивоа. Поново ставите следећа два елемента као деца десног чвора другог нивоа (број елемената на нивоу ИИИ-4: 4).
  4. Понављајте док не дођете до последњег елемента. 5 као лево дете и 6 као десно дете

Примери за Питхон, Јава и Ц / Ц ++

Питхон Јава Ц Ц ++ 
 # 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"; )

Веза између индекса низа и елемента стабла

Комплетно бинарно стабло има занимљиво својство помоћу којег можемо пронаћи децу и родитеље било којег чвора.

Ако је индекс било ког елемента у низу и, елемент у индексу 2i+1постаће лево дете, а елемент у 2i+2индексу право дете. Такође, родитељ било ког елемента у индексу и дат је доњом границом од (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

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

Комплетне апликације Бинарног стабла

  • Структуре података засноване на гомили
  • Сортирање гомиле

Занимљиви Чланци...