Обходы
Симметричный, прямой и обратный обход.
«Обходы» — бесплатный урок C Academy на CoddyKit. Это урок 3 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения C Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс C Academy содержит 4 уроков всего.
Что такое обход
Обход — это систематический способ посетить каждый узел дерева ровно один раз.
Три классических варианта обхода в глубину — in-order, pre-order и post-order. Они различаются только тем, когда обрабатывается текущий узел относительно его поддеревьев.
Обход in-order
При обходе in-order сначала посещается левое поддерево, затем узел, а после него — правое поддерево.
Для BST такой обход выводит значения в отсортированном порядке по возрастанию, поэтому он особенно полезен для деревьев поиска.
void in_order(Node *root) {
if (root == NULL) return;
in_order(root->left);
printf("%d ", root->value);
in_order(root->right);
}Обход pre-order
При обходе pre-order сначала посещается узел, затем левое поддерево, а после него — правое.
Этот порядок удобен для копирования дерева или построения префиксного выражения, поскольку корень выводится раньше дочерних узлов.
void pre_order(Node *root) {
if (root == NULL) return;
printf("%d ", root->value);
pre_order(root->left);
pre_order(root->right);
}Обход post-order
При обходе post-order сначала посещаются оба поддерева, а сам узел — последним.
Поскольку дочерние узлы обрабатываются раньше родителя, этот порядок необходим для освобождения дерева: узел никогда не используется после удаления его потомков.
void post_order(Node *root) {
if (root == NULL) return;
post_order(root->left);
post_order(root->right);
printf("%d ", root->value);
}Общая схема
Все три обхода в глубину имеют одну и ту же основу: базовый случай NULL, рекурсивный вызов для левого потомка, рекурсивный вызов для правого потомка и шаг посещения.
Название порядка меняется только из-за положения шага посещения.
/* visit position decides the order:
* pre : VISIT, left, right
* in : left, VISIT, right
* post : left, right, VISIT
*/Обход in-order выводит отсортированные значения
Эта программа строит небольшое BST и выполняет обход in-order, демонстрируя свойство отсортированного вывода.
Значения выводятся от наименьшего к наибольшему независимо от порядка вставки.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node { int value; struct Node *left, *right; } Node;
Node *cn(int v){ Node *n=malloc(sizeof(Node)); n->value=v; n->left=n->right=NULL; return n; }
Node *insert(Node *r,int v){
if(!r) return cn(v);
if(v<r->value) r->left=insert(r->left,v);
else if(v>r->value) r->right=insert(r->right,v);
return r;
}
void in_order(Node *r){ if(!r) return; in_order(r->left); printf("%d ", r->value); in_order(r->right); }
int main(void){
Node *root=NULL;
int d[]={10,5,15,3,7,12};
for(int i=0;i<6;i++) root=insert(root,d[i]);
in_order(root);
printf("\n");
return 0;
}Сравнение трёх порядков
Для дерева с корнем 10, левым узлом 5 и правым узлом 15 результаты различаются:
Pre-order даёт 10 5 15. In-order даёт 5 10 15. Post-order даёт 5 15 10. Значения узлов остаются теми же — меняется только момент их посещения.
/* 10
* / \
* 5 15
* pre : 10 5 15
* in : 5 10 15
* post: 5 15 10
*/Обход по уровням
При обходе в ширину, или level-order, узлы посещаются по уровням — сверху вниз. Такой обход не является естественно рекурсивным: он использует очередь.
Мы помещаем корень в очередь, затем повторяем следующие действия: извлекаем узел, выводим его и помещаем в очередь его потомков.
void level_order(Node *root) {
if (!root) return;
Node *queue[100];
int head = 0, tail = 0;
queue[tail++] = root;
while (head < tail) {
Node *n = queue[head++];
printf("%d ", n->value);
if (n->left) queue[tail++] = n->left;
if (n->right) queue[tail++] = n->right;
}
}Обход помогает выполнять реальные задачи
Обходы — это шаблоны для любой операции, которая должна затронуть каждый узел, а не только вывести его.
Замените шаг посещения суммированием значений, поиском максимума или копированием узлов — и та же структура выполнит задачу.
int sum_tree(Node *root) {
if (root == NULL) return 0;
return root->value
+ sum_tree(root->left)
+ sum_tree(root->right);
}Стоимость обхода
Каждый обход посещает каждый узел один раз, поэтому работает за время, пропорциональное n — числу узлов.
Рекурсия использует стековое пространство, пропорциональное высоте дерева: это log(n) для сбалансированного дерева и n в худшем случае.
Все три обхода одновременно
Эта программа выводит pre-order, in-order и post-order для одного и того же дерева, чтобы вы могли сравнить их рядом.
Обратите внимание: итоговая последовательность меняется только из-за положения вызова вывода.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node { int value; struct Node *left, *right; } Node;
Node *cn(int v){ Node *n=malloc(sizeof(Node)); n->value=v; n->left=n->right=NULL; return n; }
void pre(Node *r){ if(!r) return; printf("%d ", r->value); pre(r->left); pre(r->right); }
void ino(Node *r){ if(!r) return; ino(r->left); printf("%d ", r->value); ino(r->right); }
void post(Node *r){ if(!r) return; post(r->left); post(r->right); printf("%d ", r->value); }
int main(void){
Node *root = cn(10);
root->left = cn(5); root->right = cn(15);
pre(root); printf("\n");
ino(root); printf("\n");
post(root); printf("\n");
return 0;
}Быстрая проверка
Выберите подходящий обход для задачи.
Итоги
Обходы в глубину используют одну рекурсивную основу; положение шага посещения определяет порядок pre-, in- или post-order. Обход in-order для BST даёт отсортированный вывод, а post-order безопасен для освобождения памяти.
Обход level-order выполняется в ширину и использует очередь. Каждый из этих обходов посещает каждый узел один раз за время O(n).
Часто задаваемые вопросы
Урок «Обходы» бесплатный?
Да — полный текст урока «Обходы» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс C Academy, подпишись на CoddyKit PRO. Курс C Academy содержит 4 уроков всего.
Чему я научусь в уроке «Обходы»?
Симметричный, прямой и обратный обход. Ты практикуешь C Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать C Academy?
Предыдущий опыт не требуется. C Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 3 из 4.
Сколько времени занимает урок «Обходы»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке C Academy?
Да. Каждый урок C Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.