Drzewo binarne
Ostatnia aktualizacja
Drzewo binarne to hierarchia, w której każdy węzeł ma najwyżej dwoje dzieci, nazywanych lewym i prawym dzieckiem. Najwyższy węzeł to korzeń, węzły bez dzieci to liście, a liczba krawędzi od korzenia do najgłębszego liścia to wysokość drzewa. W przeciwieństwie do binarnego drzewa poszukiwań zwykłe drzewo binarne nie ma reguły porządku: to sam kształt. Kliknij odtwarzanie powyżej i zobacz, jak drzewo wypełnia się poziom po poziomie, a potem jest przechodzone in-order (lewe, węzeł, prawe).
Drzewa binarne są podstawą wielu struktur: binarnych drzew poszukiwań, kopców, drzew wyrażeń i innych. Przejścia odwiedzają każdy węzeł w określonej kolejności: in-order, pre-order i post-order to trzy przejścia w głąb, a każde przydaje się do innych zadań.
Pojęcia
| Pojęcie | Znaczenie |
|---|---|
| Korzeń | Najwyższy węzeł, bez rodzica |
| Liść | Węzeł bez dzieci |
| Wysokość | Najdłuższa ścieżka od korzenia do liścia (w krawędziach) |
| Głębokość | Odległość węzła od korzenia |
| Zupełne | Wszystkie poziomy pełne, z wyjątkiem być może ostatniego, wypełnianego od lewej do prawej |
Trzy przejścia w głąb
| Przejście | Kolejność | Typowe zastosowanie |
|---|---|---|
| In-order | Lewe, węzeł, prawe | Posortowany wynik z drzewa BST |
| Pre-order | Węzeł, lewe, prawe | Kopiowanie / serializacja drzewa |
| Post-order | Lewe, prawe, węzeł | Usuwanie / obliczanie drzewa |
Przykład krok po kroku
Przejście in-order drzewa zbudowanego z [4, 2, 6, 1, 3, 5] (wypełnianego poziom po poziomie):
| Krok | W węźle | Działanie |
|---|---|---|
| 1 | 4 | Zejdź rekurencyjnie do lewego poddrzewa 4, zanim go odwiedzisz |
| 2 | 2 | Zejdź rekurencyjnie do lewego poddrzewa 2, zanim go odwiedzisz |
| 3 | 1 | Liść, brak lewego dziecka: odwiedź 1, wynik [1] |
| 4 | 2 | Lewa strona gotowa: odwiedź 2, wynik [1, 2], potem zejdź w prawo |
| 5 | 3 | Liść: odwiedź 3, wynik [1, 2, 3] |
| 6 | 4 | Lewe poddrzewo gotowe: odwiedź 4, wynik [1, 2, 3, 4], potem zejdź w prawo |
| 7 | 5 | Lewe dziecko 6, liść: odwiedź 5, wynik [1, 2, 3, 4, 5] |
| 8 | 6 | Lewa strona gotowa, brak prawego dziecka: odwiedź 6, wynik [1, 2, 3, 4, 5, 6] |
Kiedy używać drzewa binarnego
| Używaj, gdy | Unikaj, gdy |
|---|---|
| Musisz modelować dane z natury hierarchiczne (systemy plików, drzewa wyrażeń, DOM) | Dane są płaskie i wystarczy lista lub tablica: drzewo dodaje tylko narzut |
| Chcesz operacji na uporządkowanych danych i możesz utrzymać równowagę (BST lub drzewo samorównoważące się) | Potrzebujesz średnio O(1) na wyszukiwanie po kluczu: tablica haszująca pokonuje każde drzewo |
| Potrzebujesz przetwarzania danych strukturalnych w kolejności in-order, pre-order lub post-order | Węzły są wstawiane w posortowanej kolejności do niezrównoważonego drzewa BST: degraduje się ono do listy O(n) |
| Liczą się zapytania o zakres lub iteracja w porządku, których tablice haszujące nie zapewniają | Pamięci jest mało: każdy węzeł przechowuje dwa wskaźniki na dzieci oraz dane |
Binary Tree: kod
Przejrzysta, gotowa do uruchomienia implementacja algorytmu Binary Tree w językach: Python, JavaScript, Java, C++, C. Wybierz język, skopiuj kod albo otwórz go od razu w edytorze online Coddy.
Binary Tree: kod (Python)
Python
1from collections import deque2
3
4class Node:5 def __init__(self, value):6 self.value = value7 self.left = None8 self.right = None9
10
11def insert(root, value):12 # Level-order insert: fill the first empty child slot found13 if root is None:14 return Node(value)15 queue = deque([root])16 while queue:17 node = queue.popleft()18 if node.left is None:19 node.left = Node(value)20 return root21 queue.append(node.left)22 if node.right is None:23 node.right = Node(value)24 return root25 queue.append(node.right)26
27
28def inorder(node):29 if node is None:30 return []31 return inorder(node.left) + [node.value] + inorder(node.right)32
33
34root = None35for value in [1, 2, 3, 4, 5, 6, 7]:36 root = insert(root, value)37
38print("Root: ", root.value)39print("Inorder:", inorder(root))Binary Tree: kod (JavaScript)
JavaScript
1class Node {2 constructor(value) {3 this.value = value;4 this.left = null;5 this.right = null;6 }7}8
9class BinaryTree {10 constructor() {11 this.root = null;12 }13
14 // Insert at the first free spot, top to bottom (level order)15 insert(value) {16 const node = new Node(value);17 if (!this.root) {18 this.root = node;19 return;20 }21 const queue = [this.root];22 while (queue.length > 0) {23 const current = queue.shift();24 if (!current.left) {25 current.left = node;26 return;27 }28 if (!current.right) {29 current.right = node;30 return;31 }32 queue.push(current.left, current.right);33 }34 }35
36 inorder(node = this.root, out = []) {37 if (!node) return out;38 this.inorder(node.left, out);39 out.push(node.value);40 this.inorder(node.right, out);41 return out;42 }43}44
45const tree = new BinaryTree();46for (const value of [1, 2, 3, 4, 5, 6, 7]) tree.insert(value);47console.log("Inorder traversal:", tree.inorder().join(" "));Binary Tree: kod (Java)
Java
1import java.util.ArrayDeque;2import java.util.Queue;3
4public class Main {5 static class Node {6 int value;7 Node left, right;8 Node(int value) { this.value = value; }9 }10
11 static Node root;12
13 // Insert at the first free slot in level order (keeps the tree complete)14 static void insert(int value) {15 Node node = new Node(value);16 if (root == null) { root = node; return; }17 Queue<Node> queue = new ArrayDeque<>();18 queue.add(root);19 while (!queue.isEmpty()) {20 Node cur = queue.poll();21 if (cur.left == null) { cur.left = node; return; }22 if (cur.right == null) { cur.right = node; return; }23 queue.add(cur.left);24 queue.add(cur.right);25 }26 }27
28 // Inorder: left subtree, node, right subtree29 static void inorder(Node node, StringBuilder sb) {30 if (node == null) return;31 inorder(node.left, sb);32 sb.append(node.value).append(" ");33 inorder(node.right, sb);34 }35
36 public static void main(String[] args) {37 for (int v = 1; v <= 7; v++) insert(v);38 StringBuilder sb = new StringBuilder();39 inorder(root, sb);40 System.out.println("Root: " + root.value);41 System.out.println("Inorder: " + sb.toString().trim());42 }43}Binary Tree: kod (C++)
C++
1#include <iostream>2
3struct Node {4 int value;5 Node* left = nullptr;6 Node* right = nullptr;7 explicit Node(int v) : value(v) {}8};9
10Node* insert(Node* root, int value) {11 if (root == nullptr) return new Node(value);12 if (value < root->value) root->left = insert(root->left, value);13 else root->right = insert(root->right, value);14 return root;15}16
17// In-order traversal: left subtree, node, right subtree18void inorder(const Node* node) {19 if (node == nullptr) return;20 inorder(node->left);21 std::cout << node->value << " ";22 inorder(node->right);23}24
25int countNodes(const Node* node) {26 if (node == nullptr) return 0;27 return 1 + countNodes(node->left) + countNodes(node->right);28}29
30int main() {31 Node* root = nullptr;32 for (int value : {8, 3, 10, 1, 6, 14, 4}) {33 root = insert(root, value);34 }35 std::cout << "In-order: ";36 inorder(root);37 std::cout << "\n";38 std::cout << "Node count: " << countNodes(root) << "\n";39 return 0;40}Binary Tree: kod (C)
C
1#include <stdio.h>2#include <stdlib.h>3
4typedef struct Node {5 int value;6 struct Node* left;7 struct Node* right;8} Node;9
10Node* newNode(int value) {11 Node* n = malloc(sizeof(Node));12 n->value = value;13 n->left = n->right = NULL;14 return n;15}16
17Node* insert(Node* root, int value) {18 if (root == NULL) return newNode(value);19 if (value < root->value) root->left = insert(root->left, value);20 else root->right = insert(root->right, value);21 return root;22}23
24// In-order traversal: left subtree, node, right subtree25void inorder(const Node* node) {26 if (node == NULL) return;27 inorder(node->left);28 printf("%d ", node->value);29 inorder(node->right);30}31
32int countNodes(const Node* node) {33 if (node == NULL) return 0;34 return 1 + countNodes(node->left) + countNodes(node->right);35}36
37int main(void) {38 int values[] = {8, 3, 10, 1, 6, 14, 4};39 Node* root = NULL;40 for (int i = 0; i < 7; i++) root = insert(root, values[i]);41 printf("In-order: ");42 inorder(root);43 printf("\n");44 printf("Node count: %d\n", countNodes(root));45 return 0;46}Drzewo binarne: najczęstsze pytania
Czym różni się drzewo binarne od binarnego drzewa poszukiwań?
Drzewo binarne po prostu ogranicza każdy węzeł do najwyżej dwojga dzieci, bez żadnego porządku. Binarne drzewo poszukiwań dodaje regułę, że wszystko w lewym poddrzewie jest mniejsze, a wszystko w prawym większe, i właśnie to przyspiesza wyszukiwanie.
Czym jest przejście in-order?
Przejście in-order odwiedza rekurencyjnie lewe poddrzewo, potem węzeł, a potem prawe poddrzewo. W binarnym drzewie poszukiwań zwraca wartości posortowane rosnąco, dlatego jest to najczęściej prezentowane przejście.
Czym jest zupełne drzewo binarne?
Zupełne drzewo binarne ma każdy poziom całkowicie wypełniony, z wyjątkiem być może ostatniego, który jest wypełniany od lewej do prawej. Taki kształt pozwala zwięźle przechowywać drzewo w tablicy (bez wskaźników na dzieci) i właśnie tak implementuje się kopce binarne.
Kiedy użyć drzewa binarnego zamiast tablicy lub tablicy haszującej?
Sięgnij po drzewo, gdy dane są naturalnie hierarchiczne albo gdy potrzebujesz operacji na uporządkowanych danych, takich jak zapytania o zakres i iteracja w porządku, których tablice haszujące nie dają. Jeśli potrzebujesz tylko szybkiego wyszukiwania po kluczu bez porządku, średni dostęp
O(1) tablicy haszującej pokonuje drzewo, a dla płaskich danych zwykła tablica jest prostsza i lepiej współpracuje z pamięcią podręczną.Czym różni się wysokość od głębokości drzewa binarnego?
Głębokość mierzy się od korzenia w dół do konkretnego węzła: to liczba krawędzi na ścieżce od korzenia do tego węzła. Wysokość mierzy się od węzła w dół do jego najgłębszego liścia, więc wysokość całego drzewa to głębokość jego najgłębszego węzła. Drzewo z jednym węzłem ma wysokość
0, a jego jedyny węzeł ma też głębokość 0.Dlaczego niezrównoważone drzewo binarne działa tak słabo?
Wyszukiwanie, wstawianie i usuwanie w binarnym drzewie poszukiwań kosztują
O(h), gdzie h to wysokość. Gdy klucze są wstawiane w posortowanej kolejności, drzewo staje się prostą linią, więc h rośnie do n, a każda operacja degraduje się do O(n), czyli nie lepiej niż lista jednokierunkowa. Drzewa samorównoważące się, takie jak AVL czy czerwono-czarne, utrzymują wysokość O(log n), aby temu zapobiec.Powiązane materiały
Więcej wizualizacji
