Обход двоичного дерева на Python
Да, двоичные деревья — не самая любимая тема программистов. Это одна из тех старых концепций, о целесообразности изучения которых постоянно ведутся споры. В работе вам довольно редко придется реализовывать двоичные деревья и обходить их, так зачем же уделять им так много внимания на технических собеседованиях?
Сегодня мы не будем переворачивать двоичное дерево (ффухх!), но рассмотрим пару методов его обхода. К концу статьи вы поймете, что двоичные деревья не так страшны, как кажется.
Что такое двоичное дерево?
Недавно мы разбирали реализацию связных списков на Python. Каждый такой список состоит из некоторого количества узлов, указывающих на другие узлы. А если бы узел мог указывать не на один другой узел, а на большее их число? Вот это и есть деревья. В них каждый родительский узел может иметь несколько узлов-потомков. Если у каждого узла максимум два узла-потомка (левый и правый), такое дерево называется двоичным (бинарным).
В приведенном выше примере «корень» дерева, т. е. самый верхний узел, имеет значение 1. Его потомки — 2 и 3. Узлы 3, 4 и 5 называют «листьями»: у них нет узлов-потомков.
Строим двоичное дерево на Python
Как построить дерево на Python? Реализация будет похожей на наш класс Node в реализации связного списка. В этом случае мы назовем класс TreeNode .
Определим метод __init__() . Как всегда, он принимает self . Также мы передаем в него значение, которое будет храниться в узле.
class TreeNode: def __init__(self, value):
Установим значение узла, а затем определим левый и правый указатель (для начала поставим им значение None ).
class TreeNode: def __init__(self, value): self.value = value self.left = None self.right = None
И… все! Что, думали, что деревья куда сложнее? Если речь идет о двоичном дереве, единственное, что его отличает от связного списка, это то, что вместо next у нас тут есть left и right .
Давайте построим дерево, которое изображено на схеме в начале статьи. Верхний узел имеет значение 1. Далее мы устанавливаем левые и правые узлы, пока не получим желаемое дерево.
tree = TreeNode(1) tree.left = TreeNode(2) tree.right = TreeNode(3) tree.left.left = TreeNode(4) tree.left.right = TreeNode(5)
Обход двоичного дерева
Итак, вы построили дерево и теперь вам, вероятно, любопытно, как же его увидеть. Нет никакой команды, которая позволила бы вывести на экран дерево целиком, тем не менее мы можем обойти его, посетив каждый узел. Но в каком порядке выводить узлы?
Самые простые в реализации обходы дерева — прямой (Pre-Order), обратный (Post-Order) и центрированный (In-Order). Вы также можете услышать такие термины, как поиск в ширину и поиск в глубину, но их реализация сложнее, ее мы рассмотрим как-нибудь потом.
Итак, что из себя представляют три варианта обхода, указанные выше? Давайте еще раз посмотрим на наше дерево.
При прямом обходе мы посещаем родительские узлы до посещения узлов-потомков. В случае с нашим деревом мы будем обходить узлы в таком порядке: 1, 2, 4, 5, 3.
Обратный обход двоичного дерева — это когда вы сначала посещаете узлы-потомки, а затем — их родительские узлы. В нашем случае порядок посещения узлов при обратном обходе будет таким: 4, 5, 2, 3, 1.
При центрированном обходе мы посещаем все узлы слева направо. Центрированный обход нашего дерева — это посещение узлов 4, 2, 5, 1, 3.
Давайте напишем методы обхода для нашего двоичного дерева.
Pre-Order
Начнем с определения метода pre_order() . Наш метод принимает один аргумент — корневой узел (расположенный выше всех).
Дальше нам нужно проверить, существует ли этот узел. Вы можете возразить, что лучше бы проверить существование потомков этого узла перед их посещением. Но для этого нам пришлось бы написать два if-предложения, а так мы обойдемся одним.
def pre_order(node): if node: pass
Написать обход просто. Прямой обход — это посещение родительского узла, а затем каждого из его потомков. Мы «посетим» родительский узел, выведя его на экран, а затем «обойдем» детей, вызывая этот метод рекурсивно для каждого узла-потомка.
# Выводит родителя до всех его потомков def pre_order(node): if node: print(node.value) pre_order(node.left) pre_order(node.right)
Просто, правда? Можем протестировать этот код, совершив обход построенного ранее дерева.
Post-Order
Переходим к обратному обходу. Возможно, вы думаете, что для этого нужно написать еще один метод, но на самом деле нам нужно изменить всего одну строчку в предыдущем.
Вместо «посещения» родительского узла и последующего «обхода» детей, мы сначала «обойдем» детей, а затем «посетим» родительский узел. То есть, мы просто передвинем print на последнюю строку! Не забудьте поменять имя метода на post_order() во всех вызовах.
# Выводит потомков, а затем родителя def post_order(node): if node: post_order(node.left) post_order(node.right) print(node.value)
Каждый узел-потомок посещен до посещения его родителя.
In-Order
Наконец, напишем метод центрированного обхода. Как нам обойти левый узел, затем родительский, а затем правый? Опять же, нужно переместить предложение print!
# выводит левого потомка, затем родителя, затем правого потомка def in_order(node): if node: in_order(node.left) print(node.value) in_order(node.right)
Вот и все, мы рассмотрели три простейших способа совершить обход двоичного дерева.
Источник
Дерево
Дерево – структура данных, представляющая собой древовидную структуру в виде набора связанных узлов.
Бинарное дерево — это конечное множество элементов, которое либо пусто, либо содержит элемент ( корень ), связанный с двумя различными бинарными деревьями, называемыми левым и правым поддеревьями . Каждый элемент бинарного дерева называется узлом . Связи между узлами дерева называются его ветвями .
Способ представления бинарного дерева:
Корень дерева расположен на уровне с минимальным значением.
Узел D , который находится непосредственно под узлом B , называется потомком B . Если D находится на уровне i , то B – на уровне i-1 . Узел B называется предком D .
Максимальный уровень какого-либо элемента дерева называется его глубиной или высотой .
Если элемент не имеет потомков, он называется листом или терминальным узлом дерева.
Остальные элементы – внутренние узлы (узлы ветвления).
Число потомков внутреннего узла называется его степенью . Максимальная степень всех узлов есть степень дерева.
Число ветвей, которое нужно пройти от корня к узлу x , называется длиной пути к x . Корень имеет длину пути равную 0 ; узел на уровне i имеет длину пути равную i .
Бинарное дерево применяется в тех случаях, когда в каждой точке вычислительного процесса должно быть принято одно из двух возможных решений.
Имеется много задач, которые можно выполнять на дереве.
Распространенная задача — выполнение заданной операции p с каждым элементом дерева. Здесь p рассматривается как параметр более общей задачи посещения всех узлов или задачи обхода дерева.
Если рассматривать задачу как единый последовательный процесс, то отдельные узлы посещаются в определенном порядке и могут считаться расположенными линейно.
Способы обхода дерева
Пусть имеем дерево, где A — корень, B и C — левое и правое поддеревья.
Существует три способа обхода дерева:
- Обход дерева сверху вниз (в прямом порядке): A, B, C — префиксная форма.
- Обход дерева в симметричном порядке (слева направо): B, A, C — инфиксная форма.
- Обход дерева в обратном порядке (снизу вверх): B, C, A — постфиксная форма.
Реализация дерева
Узел дерева можно описать как структуру:
struct tnode <
int field; // поле данных
struct tnode *left; // левый потомок
struct tnode *right; // правый потомок
>;
При этом обход дерева в префиксной форме будет иметь вид
void treeprint(tnode *tree) <
if (tree!= NULL ) < //Пока не встретится пустой узел
cout field; //Отображаем корень дерева
treeprint(tree->left); //Рекурсивная функция для левого поддерева
treeprint(tree->right); //Рекурсивная функция для правого поддерева
>
>
Обход дерева в инфиксной форме будет иметь вид
void treeprint(tnode *tree) <
if (tree!= NULL ) < //Пока не встретится пустой узел
treeprint(tree->left); //Рекурсивная функция для левого поддерева
cout field; //Отображаем корень дерева
treeprint(tree->right); //Рекурсивная функция для правого поддерева
>
>
Обход дерева в постфиксной форме будет иметь вид
void treeprint(tnode *tree) <
if (tree!= NULL ) < //Пока не встретится пустой узел
treeprint(tree->left); //Рекурсивная функция для левого поддерева
treeprint(tree->right); //Рекурсивная функция для правого поддерева
cout field; //Отображаем корень дерева
>
>
Бинарное (двоичное) дерево поиска – это бинарное дерево, для которого выполняются следующие дополнительные условия (свойства дерева поиска):
- оба поддерева – левое и правое, являются двоичными деревьями поиска;
- у всех узлов левого поддерева произвольного узла X значения ключей данных меньше, чем значение ключа данных самого узла X ;
- у всех узлов правого поддерева произвольного узла X значения ключей данных не меньше, чем значение ключа данных узла X .
Данные в каждом узле должны обладать ключами, на которых определена операция сравнения меньше.
Как правило, информация, представляющая каждый узел, является записью, а не единственным полем данных.
Для составления бинарного дерева поиска рассмотрим функцию добавления узла в дерево.
Добавление узлов в дерево
struct tnode * addnode( int x, tnode *tree) <
if (tree == NULL ) < // Если дерева нет, то формируем корень
tree = new tnode; // память под узел
tree->field = x; // поле данных
tree->left = NULL ;
tree->right = NULL ; // ветви инициализируем пустотой
> else if (x < tree->field) // условие добавление левого потомка
tree->left = addnode(x,tree->left);
else // условие добавление правого потомка
tree->right = addnode(x,tree->right);
return (tree);
>
Удаление поддерева
void freemem(tnode *tree) <
if (tree!= NULL ) <
freemem(tree->left);
freemem(tree->right);
delete tree;
>
>
Пример Написать программу, подсчитывающую частоту встречаемости слов входного потока.
Поскольку список слов заранее не известен, мы не можем предварительно упорядочить его. Неразумно пользоваться линейным поиском каждого полученного слова, чтобы определять, встречалось оно ранее или нет, т.к. в этом случае программа работает слишком медленно.
Один из способов — постоянно поддерживать упорядоченность уже полученных слов, помещая каждое новое слово в такое место, чтобы не нарушалась имеющаяся упорядоченность. Воспользуемся бинарным деревом.
В дереве каждый узел содержит:
- указатель на текст слова;
- счетчик числа встречаемости;
- указатель на левого потомка;
- указатель на правого потомка.
Рассмотрим выполнение программы на примере фразы
now is the time for all good men to come to the aid of their party
При этом дерево будет иметь следующий вид
#include
#include
#include
#include
//#include
#define MAX WORD 100
struct tnode < // узел дерева
char * word; // указатель на строку (слово)
int count; // число вхождений
struct tnode* left; // левый потомок
struct tnode* right; // правый потомок
>;
// Функция добавления узла к дереву
struct tnode* addtree( struct tnode* p, char * w) int cond;
if (p == NULL ) p = ( struct tnode*)malloc( sizeof ( struct tnode));
p->word = _strdup(w);
p->count = 1;
p->left = p->right = NULL ;
>
else if ((cond = strcmp(w, p->word)) == 0)
p->count++;
else if (cond < 0)
p->left = addtree(p->left, w);
else
p->right = addtree(p->right, w);
return p;
>
// Функция удаления поддерева
void freemem(tnode* tree) if (tree != NULL ) freemem(tree->left);
freemem(tree->right);
free(tree->word);
free(tree);
>
>
// Функция вывода дерева
void treeprint( struct tnode* p) if (p != NULL ) treeprint(p->left);
printf( «%d %s\n» , p->count, p->word);
treeprint(p->right);
>
>
int main() struct tnode* root;
char word[MAX WORD ];
root = NULL ;
do scanf_s( «%s» , word, MAX WORD );
if (isalpha(word[0]))
root = addtree(root, word);
> while (word[0] != ‘0’ ); // условие выхода – ввод символа ‘0’
treeprint(root);
freemem(root);
getchar();
getchar();
return 0;
>
Результат выполнения
Комментариев к записи: 19
Источник