/
martompopulin
/
algor1
Обзор
Документация
Войти
/
martompopulin
/
algor1
Код
Запросы
0
Задачи
Вики
Пакеты
0
Релизы
0
CI/CD
Аналитика
Безопасность
master
binary-trees.html
114 строк
7 KB
martompopulin
create: algorithms-and-data-structures.html, basic-algorithms.html, binary-trees.html, efficiency.html, graphs.html, index.html, lists.html, style.css, trees.html
06 май 2026, 18:23
Верифицирован
06 май 2026, 18:23
8210df3
Код
Авторство
О чём код?
<!doctype html> <html lang="ru"> <head> <meta charset="utf-8"> <meta name="viewport" content="width=device-width, initial-scale=1"> <title>Бинарные деревья</title> <link rel="stylesheet" href="./style.css"> <script> window.MathJax = { tex: { inlineMath: [['\\(','\\)'], ['$', '$']], displayMath: [['\\[','\\]'], ['$$','$$']], processEscapes: true }, svg: { fontCache: 'global' } }; </script> <script defer src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-svg.js"></script> </head> <body> <div class="site-shell"> <section class="hero"> <div class="badge">Obsidian → HTML / GitVerse-ready</div> <h1>Бинарные деревья</h1> <p>Связанная заметка из базы знаний по алгоритмам и структурам данных. Внутренние ссылки сохранены, формулы отображаются через MathJax.</p> </section> <div class="layout"> <aside class="sidebar"> <h2>Разделы</h2> <a class="navlink" href="./algorithms-and-data-structures.html">Алгоритмы и структуры данных</a> <a class="navlink" href="./basic-algorithms.html">Основные алгоритмы</a> <a class="navlink" href="./efficiency.html">Эффективность</a> <a class="navlink" href="./trees.html">Деревья</a> <a class="navlink" href="./binary-trees.html">Бинарные деревья</a> <a class="navlink" href="./graphs.html">Графы</a> <a class="navlink" href="./lists.html">Списки, как наглядные структуры</a> </aside> <main class="page-card"> <a class="back" href="./index.html">← На главную</a> <h1>Бинарные деревья</h1> <p><strong>Бинарное (двоичное) дерево</strong> - это динамическая <a href="./algorithms-and-data-structures.html#d79e48">структура данных</a>, представляющее собой <a href="./trees.html">дерево</a>, в котором каждая вершина имеет не более двух потомков.</p> <h2>Обход бинарного дерева</h2> <p>Пошаговый перебор элементов дерева по связям между предками-узлами и потомками-узлами называется обходом дерево.</p> <p>Есть 3 вида обхода по дереву:</p> <ul class="content-list"> <li><strong>Прямой (pre-order walr)</strong> - сначала посещается корень дерева и, затем в прямом порядке вершины <a href="./trees.html#6d6024">поддерева 1</a> (BDE), далее вершины поддерева 2 (C) и т.д.;</li> <li><strong>Симметричный</strong> - сначала в симметричном порядке посещаются вершины поддерева 1, далее корень поддерева, затем последовательно в симметричном порядке вершины поддеревьев.</li> <li><strong>Обратный (post order walk)</strong> - от вершины поддерева 1 (BDE), далее последовательно в обратном порядке посещаются вершины поддеревьев.</li> </ul> <div class="diagram"> <svg viewBox="0 0 760 300" role="img" aria-label="Схема бинарного дерева"> <line x1="380" y1="50" x2="240" y2="130" class="edge"/> <line x1="380" y1="50" x2="520" y2="130" class="edge"/> <line x1="240" y1="130" x2="170" y2="220" class="edge"/> <line x1="240" y1="130" x2="310" y2="220" class="edge"/> <line x1="520" y1="130" x2="450" y2="220" class="edge"/> <line x1="520" y1="130" x2="590" y2="220" class="edge"/> <circle cx="380" cy="50" r="30" class="node-root"/><text x="380" y="56">A</text> <circle cx="240" cy="130" r="28" class="node"/><text x="240" y="136">B</text> <circle cx="520" cy="130" r="28" class="node"/><text x="520" y="136">C</text> <circle cx="170" cy="220" r="25" class="leaf"/><text x="170" y="226">D</text> <circle cx="310" cy="220" r="25" class="leaf"/><text x="310" y="226">E</text> <circle cx="450" cy="220" r="25" class="leaf"/><text x="450" y="226">F</text> <circle cx="590" cy="220" r="25" class="leaf"/><text x="590" y="226">G</text> </svg> <div class="caption">Бинарное дерево: у каждой вершины не более двух потомков.</div> </div> <h2>Степени вершин бинарного дерева</h2> <p><strong>Степень вершины</strong> - это количество ребер, инцидентных к этой вершине.</p> <p>Каждая вершина бинарного дерева является структурой, состоящей из четырех видов полей. Содержимым этих полей будут соответственно:</p> <ul class="content-list"> <li>информационное поле (ключ вершины);</li> <li>служебное поле;</li> <li>указатель на левое поддерево;</li> <li>указатель на правое поддерево.</li> </ul> <p>По степени вершин бинарные деревья делятся:</p> <ul class="content-list"> <li><strong>Строгие</strong> - вершины дерева имеют степень нуль (у листьев) или два (у внутренних узлов);</li> <li><strong>Нестрогие</strong> - вершины дерева имеют степень нуль (у лисьтев), один или два (у узлов).</li> <li><strong>Полные</strong> - в котором все уровни заполнены, кроме, возможно последнего, который заполняется слева направо;</li> <li><strong>Неполные</strong> - дерево, в котором нарушен порядок заполнения или есть пропуски на уровнях.</li> </ul> <div class="diagram"> <svg viewBox="0 0 760 300" role="img" aria-label="Схема бинарного дерева"> <line x1="380" y1="50" x2="240" y2="130" class="edge"/> <line x1="380" y1="50" x2="520" y2="130" class="edge"/> <line x1="240" y1="130" x2="170" y2="220" class="edge"/> <line x1="240" y1="130" x2="310" y2="220" class="edge"/> <line x1="520" y1="130" x2="450" y2="220" class="edge"/> <line x1="520" y1="130" x2="590" y2="220" class="edge"/> <circle cx="380" cy="50" r="30" class="node-root"/><text x="380" y="56">A</text> <circle cx="240" cy="130" r="28" class="node"/><text x="240" y="136">B</text> <circle cx="520" cy="130" r="28" class="node"/><text x="520" y="136">C</text> <circle cx="170" cy="220" r="25" class="leaf"/><text x="170" y="226">D</text> <circle cx="310" cy="220" r="25" class="leaf"/><text x="310" y="226">E</text> <circle cx="450" cy="220" r="25" class="leaf"/><text x="450" y="226">F</text> <circle cx="590" cy="220" r="25" class="leaf"/><text x="590" y="226">G</text> </svg> <div class="caption">Бинарное дерево: у каждой вершины не более двух потомков.</div> </div> </main> </div> <div class="footer">Сайт собран из Markdown-файлов для публикации на GitVerse Pages.</div> </div> </body> </html>