В чем разница между деревом и списком?

Разница между деревом и списком (в контексте структур данных и UI)

Дерево (Tree) и Список (List) — это две фундаментально разные структуры данных, каждая предназначена для разных задач.

Список (List)

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

// Связный список
class ListNode<T> {
  T data;
  ListNode<T>? next;
  
  ListNode(this.data, {this.next});
}

// Создание списка: 1 -> 2 -> 3 -> null
var node1 = ListNode(1);
var node2 = ListNode(2);
var node3 = ListNode(3);

node1.next = node2;
node2.next = node3;

// Обход списка
var current = node1;
while (current != null) {
  print(current.data);
  current = current.next;
}

Характеристики списка:

• Линейная структура — один элемент -> следующий элемент
• Одна ветвь — каждый узел имеет максимум одного потомка
• Простая навигация — только вперёд (или вперёд-назад для двусвязных)
• Порядок важен — элементы расположены последовательно
• Использование памяти — О(n) для n элементов
• Доступ по индексу — медленный для связных списков O(n)

Дерево (Tree)

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

// Узел дерева
class TreeNode<T> {
  T data;
  List<TreeNode<T>> children = [];
  TreeNode<T>? parent;
  
  TreeNode(this.data, {this.parent});
  
  void addChild(TreeNode<T> child) {
    children.add(child);
    child.parent = this;
  }
}

// Создание дерева
//      1
//     / \\
//    2   3
//   / \\
//  4   5

var root = TreeNode(1);
var node2 = TreeNode(2);
var node3 = TreeNode(3);
var node4 = TreeNode(4);
var node5 = TreeNode(5);

root.addChild(node2);
root.addChild(node3);
node2.addChild(node4);
node2.addChild(node5);

// Обход в глубину (DFS)
void dfs(TreeNode<int> node) {
  print(node.data);
  for (var child in node.children) {
    dfs(child);
  }
}

// Обход в ширину (BFS)
Queue<TreeNode<int>> queue = Queue();
queue.add(root);

while (queue.isNotEmpty) {
  var node = queue.removeFirst();
  print(node.data);
  queue.addAll(node.children);
}

Характеристики дерева:

• Иерархическая структура — узел может иметь несколько потомков
• Корень — один главный узел (без родителя)
• Листья — узлы без потомков
• Путь — есть уникальный путь от корня к каждому узлу
• Глубина и высота — имеют значение расстояния в иерархии
• Использование памяти — О(n) для n элементов

Типичные деревья

Бинарное дерево поиска (Binary Search Tree):

class BSTNode {
  int value;
  BSTNode? left;
  BSTNode? right;
  
  BSTNode(this.value);
  
  void insert(int newValue) {
    if (newValue < value) {
      if (left == null) {
        left = BSTNode(newValue);
      } else {
        left!.insert(newValue);
      }
    } else {
      if (right == null) {
        right = BSTNode(newValue);
      } else {
        right!.insert(newValue);
      }
    }
  }
  
  bool contains(int searchValue) {
    if (searchValue == value) return true;
    if (searchValue < value) {
      return left?.contains(searchValue) ?? false;
    } else {
      return right?.contains(searchValue) ?? false;
    }
  }
}

var bst = BSTNode(50);
bst.insert(30);
bst.insert(70);
bst.insert(20);
bst.insert(40);

print(bst.contains(40)); // true
print(bst.contains(100)); // false

Flutter: Widget Tree

В Flutter приложения построены как деревья виджетов:

// Структура виджетов - это дерево
MyApp
  ├── MaterialApp
  │   └── Scaffold
  │       ├── AppBar
  │       │   └── Text('Title')
  │       └── Body
  │           ├── Column
  │           │   ├── Text('Hello')
  │           │   ├── Button
  │           │   │   └── Text('Click me')
  │           │   └── ListView
  │           │       ├── ListTile
  │           │       ├── ListTile
  │           │       └── ListTile

// В коде это выглядит так:
scaffold(
  appBar: AppBar(title: Text('Title')),
  body: Column(
    children: [
      Text('Hello'),
      ElevatedButton(
        onPressed: () {},
        child: Text('Click me'),
      ),
      ListView(
        children: [
          ListTile(title: Text('Item 1')),
          ListTile(title: Text('Item 2')),
          ListTile(title: Text('Item 3')),
        ],
      ),
    ],
  ),
)

Сравнение

Примеры использования

Список используется для:

// Очередь задач
List<Task> todoList = [
  Task('Task 1'),
  Task('Task 2'),
  Task('Task 3'),
];

// История покупок
List<Purchase> purchases = [...];

// Лента сообщений в чате
List<Message> messages = [...];

Дерево используется для:

// Иерархия папок
class FileSystem {
  Folder root = Folder('/');
  
  void addFolder(String path, String folderName) {
    var folder = root.findFolder(path);
    folder.addChild(Folder(folderName));
  }
}

// Организационная иерархия
class Department {
  String name;
  Employee manager;
  List<Department> subDepartments = [];
}

// DOM дерево в веб-приложении (как Flutter widget tree)
html.Element body = html.querySelector('body')!;
// body -> div -> p -> text

// JSON структура (часто выглядит как дерево)
const Map<String, dynamic> person = {
  'name': 'John',
  'contacts': {
    'email': 'john@example.com',
    'phone': '1234567890',
  },
  'addresses': [
    {'type': 'home', 'city': 'NYC'},
    {'type': 'work', 'city': 'Boston'},
  ],
};

Обход списка vs обход дерева

// Обход списка - просто цикл
void traverseList<T>(List<T> items) {
  for (var item in items) {
    print(item);
  }
}

// Обход дерева - рекурсия (DFS)
void traverseTreeDFS<T>(TreeNode<T> node) {
  print(node.data);
  for (var child in node.children) {
    traverseTreeDFS(child);
  }
}

// Обход дерева - итерация с очередью (BFS)
void traverseTreeBFS<T>(TreeNode<T> root) {
  var queue = Queue<TreeNode<T>>();
  queue.add(root);
  
  while (queue.isNotEmpty) {
    var node = queue.removeFirst();
    print(node.data);
    queue.addAll(node.children);
  }
}

Практическое применение в Flutter

// Дерево категорий с подкатегориями
class Category {
  String name;
  List<Category> subcategories = [];
}

// Отображение дерева категорий
class CategoryTree extends StatelessWidget {
  final Category category;
  
  @override
  Widget build(BuildContext context) {
    return ExpansionTile(
      title: Text(category.name),
      children: [
        for (var sub in category.subcategories)
          CategoryTree(category: sub),
      ],
    );
  }
}

Ключевое различие: Список — это линейная цепь, дерево — это иерархия с ветвлением. Выбирай структуру в зависимости от задачи: список для упорядоченных данных, дерево для иерархических отношений.