Введение
Предположим, у вас есть контейнер, не имеет значения какой. Этот контейнер содержит некоторый набор элементов. Вам необходимо сослаться на определенное место в этом наборе элементов. Это нужно, например, чтобы затем от этой позиции можно было перейти вперед или назад, при этом выполнив какую-то инструкцию обработки (изменить или вставить элемент, удалить его и т.д.). Чтобы не приходилось писать алгоритмы специфические для каждого контейнера, и были придуманы универсальные итераторы.
Оператор — специальный оператор генерации блока итератора. Оператор генерирует специальный класс, который выступает в качестве итератора для нашей коллекции. Этот оператор сообщает нам и компилятору, что данное выражение — итератор. Задача итератора перемещаться между элементами коллекции и возвращать текущее значение в цикле.
Рекурсию можно увидеть
И это очень красиво. Рекурсивные изображения, они же фрактальные паттерны или просто фракталы, — это рисунки или предметы, которые подобны сами себе: состоят из уменьшенных копий себя.
В природе мы встречаемся с ними, рассматривая кроны деревьев: рисунок более крупных веток повторяется в узоре более мелких. И даже черешок листовой пластинки напоминает ствол дерева, а прилистники — его ветви.
Подобным же образом выстроены кровеносные сосуды и нервы в организме животных. Свойствами фракталов обладают снежинки, а ещё — удивительная капуста романеско. Вот она на картинке ниже — ну разве не красавица?
Капуста романеско. Фото: Reissaamme / Pixabay.com
В архитектуре рекурсия встречается в облике готических соборов.
Реймсский собор. Фото: Ruben Holthuijsen / Flickr.com
В этом соборе XIII века задействован один из характерных для готики приёмов: его окна украшены тонкими ажурными перегородками. Их основной узор — стрельчатая арка с кругом внутри, круг поддерживается двумя арками меньшего размера.
А вот рекурсивная версия того же узора — Собор Линкольна.
Собор Линкольна. Фото: Dom Crossley / Flickr.com
Здесь окно тоже выполнено в форме остроконечной арки с вписанным в неё кругом, а круг лежит на двух других арках. Вот только внутри каждой из этих арок — снова круг и две ещё меньших арки, а внутри них — ещё по одному кругу на двух меньших арках.
Другой пример архитектурной рекурсии — собор Святого Петра в Ватикане.
Собор Святого Петра. Фото: Mike McBey / Flickr.com
Джордж Херси, американский писатель и журналист, его с китайскими шкатулками с секретом. По его словам, архитектурный комплекс состоит из одной макроцеркви, четырёх наборов того, что журналист назвал макси-церквями, 16 мини-церквей и 32 микроцерквей. А мог бы просто сказать, что собор рекурсивный.
В изобразительном искусстве рекурсия тоже отметилась — взять хотя бы «Триптих Стефанески» Джотто. На его центральной панели изображён кардинал Стефанески, которой держит в руках этот же триптих (на котором тоже изображён триптих и так далее).
«Триптих Стефанески», Джотто. Оборотная сторона. Фото:
А вот пример посвежее — литография «Рисующие руки» нидерландского художника XX века Маурица Эшера:
Литография «Рисующие руки», Мауриц Корнелис Эшер. Фото: Renzo Giusti / Flickr.com
Чтобы увидеть рекурсию, необязательно идти в картинную галерею — просто посмотрите на герб России. Двуглавый орёл держит в правой лапе скипетр, который увенчан двуглавым орлом, а тот тоже держит скипетр, который… 
В общем — вот:
Обход в ширину
Английское сокращение BFS или Breadth FirstSearch. Тест процесса состоит в том, чтобы посещать каждый уровень узлов по очереди, после доступа одного уровня к следующему уровню, и каждый узел можно посетить только один раз. Для приведенного выше примера результаты обхода в ширину: A, B, C, D, E, F, G, H, I (при условии, что доступ к каждому слою узлов осуществляется слева направо).
Сначала вставьте левый узел в очередь, а затем вставьте правый узел, чтобы левый узел был первым, а затем правым.
Дерево обхода в ширину, необходимо использовать очередь (Queue) для хранения объектов узлов, характеристики очереди — «первым пришел — первым вышел». Например, посещение дерева выше выглядит следующим образом:
Сначала вставьте узел A в очередь, в очереди есть элементы (A);
Поместите узел A и вставьте левый и правый узлы узла A в очередь последовательно, B во главе команды, C в конце команды (B, C), затем получите узел A;
Продолжайте вставлять элемент head, то есть pop B, и вставляйте левый и правый узлы B в очередь, C — во главе команды, а E — в конце команды (C, D, E), затем получите узел B;
Продолжайте вставлять, то есть вставлять C, и вставлять левый, центральный и правый узлы узла C в очередь по очереди (D, E, F, G, H), затем получать узел C;
Pop D, в это время D не имеет дочерних узлов, элементами в очереди являются (E, F, G, H), получить узел D;
, , , И так далее. ,
Код: здесь мы возьмем двоичное дерево в качестве примера для прохождения значений всех узлов
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
ArrayList<Integer> lists=new ArrayList<Integer>();
if(root==null)
return lists;
Queue<TreeNode> queue=new LinkedList<TreeNode>();
queue.offer(root);
while(!queue.isEmpty()){
TreeNode tree=queue.poll();
if(tree.left!=null)
queue.offer(tree.left);
if(tree.right!=null)
queue.offer(tree.right);
lists.add(tree.val);
}
return lists;
}
}
2. Глубина первая
Английская аббревиатура — DFS, то есть Поиск в глубину. Процесс состоит в том, чтобы углубить каждый возможный путь ветвления до точки, где он больше не может быть углублен, и каждыйузелДоступ только один раз. Для приведенного выше примера результат обхода в глубину: A, B, D, E, I, C, F, G, H. (при условии, что левая сторона дочернего узла берется первой).
Обход различных узлов в глубину требует использования структуры данных стека (Stack). Характеристика стека заключается в том, что он выходит первым. Весь процесс обхода выглядит следующим образом:
Сначала вставьте правый узел в стек, а затем нажмите левый узел, чтобы стек был первым левым узлом, а затем правым узлом.
Сначала вставьте узел A в стек, стек (A);
Вставьте узел A и поместите дочерние узлы C и B из A в стек в это время, B находится на вершине стека, стек (B, C);
Вставьте узел B и вставьте в стек дочерние узлы E и D B. В это время D находится на вершине стека, стек (D, E, C);
Вставьте D-узел без каких-либо дочерних узлов, и E находится на вершине стека, stack (E, C);
Вставьте узел E и нажмите дочерний узел I в E, стек (I, C);
… в свою очередь, обход окончен.
Код: возьмите двоичное дерево в качестве примера. Нерекурсивна
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
ArrayList<Integer> lists=new ArrayList<Integer>();
if(root==null)
return lists;
Stack<TreeNode> stack=new Stack<TreeNode>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode tree=stack.pop();
// Сначала вставьте правый узел в стек, а затем нажмите левый узел, чтобы стек был первым левым узлом, а затем правым узлом.
if(tree.right!=null)
stack.push(tree.right);
if(tree.left!=null)
stack.push(tree.left);
lists.add(tree.val);
}
return lists;
}
}
Рекурсивная реализация в глубину:
public void depthOrderTraversalWithRecursive()
{
depthTraversal(root);
}
private void depthTraversal(TreeNode tn)
{
if (tn!=null)
{
System.out.print(tn.value+" ");
depthTraversal(tn.left);
depthTraversal(tn.right);
}
}
Эта статья цитируется по адресу: http://www.cnblogs.com/toSeeMyDream/p/5816682.html
Категория:java,Структуры данных и алгоритмы
Метки:алгоритм, java
Хорошая статья Подписывайтесь на меня Избранное этой статьи
Глава 8 ночиПоследующие 6Вентиляторы-4
Предыдущая:Шаблон дизайнаСледующий:Режим разработки стратегического режима
posted on 2017-10-31 21:36 Глава 8 ночиЧтение (11592) Комментариев (1)редактировать
Заметки [ править ]
- ^ Не проверять входные данные.
- ^ Более элегантно, можно начать с помещения самого корневого узла в структуру данных, а затем запустить процесс.
- ^ Пост-заказ состоит в том, чтобы сделать «листовой узел — базовый случай» явным для описания, но тот же анализ работает для предварительного заказа или для упорядоченного.
- ^ Обход в ширину, в отличие от поиска в глубину, является однозначным и обращается к значению узла перед обработкой дочерних элементов.
- ^ Технически можно определить обход в ширину на упорядоченном, несвязном наборе деревьев — сначала корневой узел каждого дерева, затем потомки каждого дерева по очереди, затем внуки по очереди и т. Д.
- ^ Предположим фиксированный коэффициент ветвления (например, двоичный) или, по крайней мере, ограниченный и сбалансированный (бесконечный во всех направлениях).
-
^ Сначала определяем древовидный класс, скажем, через:
дерево классов def __init__ ( self , value , left = None , right = None ): self . Значение = значение собственной . left = левый я . right = право
и инициализировать дерево, скажем, через:
t = Дерево ( 1 , Дерево ( 2 , Дерево ( 4 ), Дерево ( 5 )), Дерево ( 3 , Дерево ( 6 ), Дерево ( 7 )))
В этом примере узлы помечены в порядке убывания ширины:
1
- ^ Интуитивно функция выполняет итерацию по поддеревьям (возможно, пустым), а затем после их завершения остается только сам узел, значение которого затем возвращается; это соответствует обработке листового узла как основного.
- ^ Здесь аргумент (и переменная цикла) рассматривается как целое, возможное бесконечное дерево, представленное (идентифицированное) его корневым узлом (дерево = корневой узел), а не как потенциальный листовой узел, отсюда и выбор имени переменной.
Приложения
Дерево, представляющее арифметическое выражение: A * ( B — C ) + ( D + E )
Предварительный обход может использоваться для создания префиксного выражения ( польская нотация ) из деревьев выражений : предварительный обход дерева выражений. Например, переход по изображенному арифметическому выражению в предварительном порядке дает «+ * A — B C + D E ».
Пост-заказный обход может генерировать постфиксное представление ( обратная польская нотация ) двоичного дерева. Переход по изображенному арифметическому выражению в пост-порядке дает « A B C — * D E + +»; последний может быть легко преобразован в машинный код для вычисления выражения стековой машиной .
Обход по порядку очень часто используется в деревьях двоичного поиска, потому что он возвращает значения из базового набора в порядке, в соответствии с компаратором, который установил дерево двоичного поиска.
Пост-заказ обход при удалении или освобождении узлов и значений может удалить или освободить все двоичное дерево. Таким образом, узел освобождается после освобождения своих дочерних узлов.
Кроме того, дублирование двоичного дерева дает последовательность действий пост-порядка, потому что копия указателя на копию узла назначается соответствующему дочернему полю N.child в копии родительского N сразу после копирования в рекурсивной процедуре. . Это означает, что родительский элемент не может быть завершен до завершения всех дочерних элементов.
Определение [ править ]
| Этот раздел может быть слишком техническим, чтобы его могло понять большинство читателей . Пожалуйста, помогите улучшить его, чтобы он был понятен неспециалистам , не удаляя технические детали. ( Ноябрь 2010 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения ) |
Исходные типы данных можно определить как наименьшую фиксированную точку (с точностью до изоморфизма ) некоторого уравнения типа; тогда изоморфизм задается исходной алгеброй . Соответственно, окончательные (или оконечные) типы данных могут быть определены как наибольшая фиксированная точка уравнения типа; тогда изоморфизм задается финальной коалгеброй .
Если предметом обсуждения является категория множеств и общих функций, то окончательные типы данных могут содержать бесконечные, необоснованные значения, тогда как исходные типы — нет. С другой стороны, если предметом обсуждения является категория полных частичных порядков и непрерывных функций , что примерно соответствует языку программирования Haskell , то конечные типы совпадают с начальными типами, а соответствующая конечная коалгебра и исходная алгебра образуют изоморфизм.
Таким образом, Corecursion — это метод рекурсивного определения функций, диапазон которых (codomain) является конечным типом данных, двойственным тому, как обычная рекурсия рекурсивно определяет функции, домен которых является начальным типом данных.
Ниже приводится несколько примеров на Haskell, которые различают corecursion. Грубо говоря, если перенести эти определения в категорию множеств, они все равно будут коркурсивными. Это неформальное использование согласуется с существующими учебниками по Haskell. Примеры, используемые в этой статье, предшествуют попыткам дать определение corecursion и объяснить, что это такое.
Рекурсивные операции с пересборкой дерева
При рекурсивной пересборке дерева мы не нуждаемся в указателе на родителя. Родитель «при нас», это текущий элемент, так что мы можем контролировать дельнейшие действия.
Определение узла и функции, которая возвращает новый узел.
typedef int T;
#define CMP_EQ(a, b) ((a) == (b))
#define CMP_LT(a, b) ((a) < (b))
#define CMP_GT(a, b) ((a) > (b))
typedef struct Node {
T data;
struct Node *left;
struct Node *right;
} Node;
Node *getNode(T value) {
Node* tmp = (Node*) malloc(sizeof(Node));
tmp->left = tmp->right = NULL;
tmp->data = value;
return tmp;
}
Функция вставки нового элемента возвращает новое дерево. Это дерево построено из старого, в которое добавлен новый узел. Причём процесс пересборки в тоже время производит поиск места, в которое нужно произвести вставку.
Если функция получает NULL в качестве аргумента, то она возвращает новый узел. Если узел больше значения, которое мы хотим вставить, то левой ветви присваиваем значение, которое возвращает наша же функция insert, то есть она «дособирает» левую ветвь. Аналогично, если значение узла меньше, то мы «дособираем» правую ветвь и возвращаем узел.
Node* insert(Node* root, T value) {
if (root == NULL) {
return getNode(value);
}
if (CMP_GT(root->data, value)) {
root->left = insert(root->left, value);
return root;
} else if (CMP_LT(root->data, value)) {
root->right = insert(root->right, value);
return root;
} else {
exit(3);
}
}
Удаление элемента состоит из пересборки дерева, во время которого мы пропускаем добавление удаляемого узла. При этом сам процесс является ещё и нахождением нужного нам узла (того, который мы хотим удалить).
Когда мы доходим до конца дерева, то логично закончить работу и вернуть NULL.
if (root == NULL) {
return NULL;
}
Теперь проверяем, если текущий узел не равен удаляемому значению, то продолжаем сборку левой и правой ветвей.
if (CMP_GT(root->data, value)) {
root->left = deleteNode(root->left, value);
return root;
} else if (CMP_LT(root->data, value)) {
root->right = deleteNode(root->right, value);
return root;
} else {
//Магия здесь
}
}
Если же мы наткнулись на узел, который хотим удалить, то есть несколько ситуаций.
if (root->left && root->right) {
//Заменить значение текущего узла на максимум левой подветви
//Удалить максимум левой подветви
//Вернуть собранное значение
} else if (root->left) {
//Удалить узел и вернуть его левую подветвь
} else if (root->right) {
//Удалить узел и вернуть его правую подветвь
} else {
//Удалить узел и вернуть NULL
}
Полный код
Node* deleteNode(Node* root, T value) {
if (root == NULL) {
return NULL;
}
if (CMP_GT(root->data, value)) {
root->left = deleteNode(root->left, value);
return root;
} else if (CMP_LT(root->data, value)) {
root->right = deleteNode(root->right, value);
return root;
} else {
if (root->left && root->right) {
Node* locMax = findMaxNode(root->left);
root->data = locMax->data;
root->left = deleteNode(root->left, locMax->data);
return root;
} else if (root->left) {
Node *tmp = root->left;
free(root);
return tmp;
} else if (root->right) {
Node *tmp = root->right;
free(root);
return tmp;
} else {
free(root);
return NULL;
}
}
}
Функции нахождения узла, максимум и минимума не изменятся.
Q&A
Всё ещё не понятно? – пиши вопросы на ящик
Хвостовая рекурсия — как не надо делать
Хвостовая рекурсия — частный случай рекурсии, при котором любой рекурсивный вызов является последней операцией перед возвратом из функции.
Вот пример обратного отсчета, написанного с использованием хвостовой рекурсии:
Любое вычисление, которое может быть выполнено с использованием итерации, также может быть выполнено с использованием рекурсии. Вот версия find_max, написанная с использованием хвостовой рекурсии:
Хвостовую рекурсию лучше не использовать, поскольку компилятор Python не обрабатывает оптимизацию для хвостовых рекурсивных вызовов. В таких случаях рекурсивное решение использует больше системных ресурсов, чем итеративное.
Модульные тесты
TestClasspublic class BinaryTreeIteratorsTests
{
#region Public methods
lExpectedSequence = new[] {3, 4, 2, 5, 8, 9, 10, 6, 20, 21, 23};
int lIndex = ;
while (lIterator.HasNext())
{
Trace.WriteLine(lIterator.Current.Value);
Assert.AreEqual(lExpectedSequencelIndex], lIterator.Current.Value);
lIterator.Next();
lIndex++;
}
Assert.AreEqual(11, lIndex, "Wrong number of elements!!!");
Assert.IsNull(lIterator.Current);
}
lExpectedSequence = new[] {10, 8, 4, 3, 5, 2, 9, 20, 6, 23, 21};
int lIndex = ;
while (lIterator.HasNext())
{
Trace.WriteLine(lIterator.Current.Value);
Assert.AreEqual(lExpectedSequencelIndex], lIterator.Current.Value);
lIterator.Next();
lIndex++;
}
Assert.AreEqual(11, lIndex, "Wrong number of elements!!!");
Assert.IsNull(lIterator.Current);
}
lExpectedSequence = new[] {3, 2, 5, 4, 9, 8, 6, 21, 23, 20, 10};
int lIndex = ;
while (lIterator.HasNext())
{
Trace.WriteLine(lIterator.Current.Value);
Assert.AreEqual(lExpectedSequencelIndex], lIterator.Current.Value);
lIterator.Next();
lIndex++;
}
Assert.AreEqual(11, lIndex, "Wrong number of elements!!!");
Assert.IsNull(lIterator.Current);
}
lExpectedSequence = new[] {10, 8, 20, 4, 9, 6, 23, 3, 5, 21, 2};
int lIndex = ;
while (lIterator.HasNext())
{
Trace.WriteLine(lIterator.Current.Value);
Assert.AreEqual(lExpectedSequencelIndex], lIterator.Current.Value);
lIterator.Next();
lIndex++;
}
Assert.AreEqual(11, lIndex, "Wrong number of elements!!!");
Assert.IsNull(lIterator.Current);
}
#endregion
#region Private methods
private BinaryTreeNode GetTestTree()
{
return new BinaryTreeNode(
10,
new BinaryTreeNode(
8,
new BinaryTreeNode(
4,
new BinaryTreeNode(
3,
null,
null),
new BinaryTreeNode(
5,
new BinaryTreeNode(
2,
null,
null),
null)),
new BinaryTreeNode(
9,
null,
null)),
new BinaryTreeNode(
20,
new BinaryTreeNode(
6,
null,
null),
new BinaryTreeNode(
23,
new BinaryTreeNode(
21,
null,
null),
null)));
}
#endregion
}
Замена циклов на рекурсию
Вставка нового узла будет завершаться в том случае, если текущий узел равен NULL, то есть искать место для узла дальше некуда. Проблемой будет
являться то, что обратиться к родительскому узлу в таком случае будет уже невозможно. Поэтому будем передавать родительский узел, к которому нужно добавить новый, как параметр
функции.
void insertRec(Node **root, Node* parent, T value) {
Node *tmp = NULL;
//Если это корень, то у него нет родителя
if (*root == NULL) {
*root = getNode(value, parent);
return;
}
tmp = (*root);
if (CMP_GT(value, tmp->data)) {
insertRec(&(tmp->right), tmp, value);
} else if (CMP_LT(value, tmp->data)) {
insertRec(&(tmp->left), tmp, value);
} else {
exit(2);
}
}
Поиск узла выгладит следующим образом: если текущий узел меньше, то вызываем функцию поиска, передавая в качестве аргумента правое поддерево, если больше, то левое.
Node* getByValueRec(Node* root, T value) {
if (!root) {
return NULL;
}
if (CMP_GT(root->data, value)) {
getByValueRec(root->left, value);
} else if (CMP_LT(root->data, value)) {
getByValueRec(root->right, value);
} else {
return root;
}
}
Поиск минимального и максимального элемента также тривиальны
Node* findMaxNodeRec(Node *root) {
if (root == NULL) {
exit(4);
}
if (root->right) {
return findMaxNodeRec(root->right);
}
return root;
}
Node* findMinNodeRec(Node* root) {
if (root == NULL) {
exit(3);
}
if (root->left) {
return findMinNodeRec(root->left);
}
return root;
}
Удаление элемента выглядит похоже на итеративное удаление. Здесь также будем передавать указатель на родителя в качестве одного из аргументов.
void removeNodeRec(Node *target, T value, Node *parent) {
if (target == NULL) {
return;
}
if (CMP_GT(target->data, value)) {
removeNodeRec(target->left, value, target);
} else if (CMP_LT(target->data, value)) {
removeNodeRec(target->right, value, target);
} else {
if (target->left && target->right) {
} else if (target->left) {
Node* localMax = findMaxNodeRec(target->left);
target->data = localMax->data;
removeNodeRec(target->left, localMax->data, target);
} else if (target->right) {
if (target->left == parent) {
parent->left = target->right;
} else {
parent->right = target->right;
}
free(target);
} else {
if (parent->left == target) {
parent->left = NULL;
} else {
parent->right = NULL;
}
free(target);
}
}
}
Заметьте: теперь нам вообще не нужен указатель на родительский элемент! Каждый раз мы храним указатель на родителя в предыдущем вызове, передавая его в качестве аргумента в следующий, поэтому в определении узла можно отказаться от использования parent.
Заодно нужно переписать функцию getNode, чтобы она не получала указатель на родителя.
Вообще, можно было сделать это и в итеративной реализации. То есть отказ от указателя на родителя не связан с использованием рекурсивного подхода.
Рекурсивные структуры
Рекурсивная (рекурсивно определяемая) структура данных – это структура, которая повторяет саму себя в своих частях.
Мы только что видели это на примере структуры компании выше.
Отдел компании – это:
- Либо массив людей.
- Либо объект с отделами.
Для веб-разработчиков существуют гораздо более известные примеры: HTML- и XML-документы.
В HTML-документе HTML-тег может содержать:
- Фрагменты текста.
- HTML-комментарии.
- Другие HTML-теги (которые, в свою очередь, могут содержать фрагменты текста/комментарии или другие теги и т.д.).
Это снова рекурсивное определение.
Для лучшего понимания мы рассмотрим ещё одну рекурсивную структуру под названием «связанный список», которая в некоторых случаях может использоваться в качестве альтернативы массиву.
Представьте себе, что мы хотим хранить упорядоченный список объектов.
Естественным выбором будет массив:
…Но у массивов есть недостатки. Операции «удалить элемент» и «вставить элемент» являются дорогостоящими. Например, операция должна переиндексировать все элементы, чтобы освободить место для нового , и, если массив большой, на это потребуется время. То же самое с .
Единственные структурные изменения, не требующие массовой переиндексации – это изменения, которые выполняются с конца массива: . Таким образом, массив может быть довольно медленным для больших очередей, когда нам приходится работать с его началом.
Или же, если нам действительно нужны быстрые вставка/удаление, мы можем выбрать другую структуру данных, называемую связанный список.
Элемент связанного списка определяется рекурсивно как объект с:
- ,
- – свойство, ссылающееся на следующий элемент связанного списка или , если это последний элемент.
Пример:
Графическое представление списка:
Альтернативный код для создания:
Здесь мы можем ещё лучше увидеть, что есть несколько объектов, каждый из которых имеет и , указывающий на соседа. Переменная является первым объектом в цепочке, поэтому, следуя по указателям из неё, мы можем попасть в любой элемент.
Список можно легко разделить на несколько частей и впоследствии объединить обратно:
Для объединения:
И, конечно, мы можем вставить или удалить элементы из любого места.
Например, для добавления нового элемента нам нужно обновить первый элемент списка:
Чтобы удалить элемент из середины списка, нужно изменить значение предыдущего элемента:
перепрыгнуло с на значение . Значение теперь исключено из цепочки. Если оно не хранится где-нибудь ещё, оно будет автоматически удалено из памяти.
В отличие от массивов, нет перенумерации, элементы легко переставляются.
Естественно, списки не всегда лучше массивов. В противном случае все пользовались бы только списками.
Главным недостатком является то, что мы не можем легко получить доступ к элементу по его индексу. В простом массиве: является прямой ссылкой. Но в списке мы должны начать с первого элемента и перейти в N раз, чтобы получить N-й элемент.
…Но нам не всегда нужны такие операции. Например, нам может быть нужна очередь или даже двухсторонняя очередь – это упорядоченная структура, которая позволяет очень быстро добавлять/удалять элементы с обоих концов, но там не нужен доступ в середину.
Списки могут быть улучшены:
- Можно добавить свойство в дополнение к для ссылки на предыдущий элемент, чтобы легко двигаться по списку назад.
- Можно также добавить переменную , которая будет ссылаться на последний элемент списка (и обновлять её при добавлении/удалении элементов с конца).
- …Возможны другие изменения: главное, чтобы структура данных соответствовала нашим задачам с точки зрения производительности и удобства.
Ширина Первый обход
Английское сокращение BFS или Breadth FirstSearch. Инспекция процесса состоит в том, чтобы посещать каждый уровень узлов по очереди, после доступа к одному уровню, перейти на следующий уровень, и каждый узел может посетить только один раз. Для приведенного выше примера результаты обхода в ширину следующие: A, B, C, D, E, F, G, H, I (при условии, что доступ к каждому слою узлов осуществляется слева направо).
Обход дерева в ширину требует использования очереди для хранения объектов узлов. Характеристики очереди — «первым пришел — первым вышел». Например, доступ к дереву выше выглядит следующим образом:
Сначала вставьте узел в очередь, есть элементы (A) в очереди;
Поместите узел A и вставьте левый и правый узлы узла A в очередь последовательно, B — во главе команды, C — в конце команды, (B, C), и в это время получен узел A;
Продолжайте вставлять первый элемент команды, то есть B, и вставьте левый и правый узлы B в очередь, C — во главе команды, а E — в конце команды (C, D, E). В это время получается узел B;
Продолжайте вставлять, то есть вставлять C, и вставлять левый, средний и правый узлы узла C в очередь по порядку (D, E, F, G, H) и получать узел C в это время;
Pop D, в это время D не имеет дочерних узлов, и элементы в очереди (E, F, G, H), чтобы получить узел D;
, , , И так далее. ,
Код: возьмите в качестве примера бинарное дерево, переберите значения всех узлов
2. Глубина первая
Английское сокращение — DFS, то есть поиск в глубину. Процесс состоит в том, чтобы кратко углубить каждый возможный путь ветвления, пока он не может быть углублен дальше, и каждыйузелДоступ только один раз. Для приведенного выше примера результаты первого обхода глубины: A, B, D, E, I, C, F, G, H. (при условии, что левая сторона дочернего узла берется первой).
Обход в глубину каждого узла требует структуры данных, называемой стеком. Стек характеризуется первым во-первых. Весь процесс обхода выглядит следующим образом:
Сначала вставьте узел A в стек, стек (A);
Вставьте узел A и одновременно вставьте в стек дочерние узлы C и B из A. В это время B находится на вершине стека, стек (B, C);
Вставьте узел B и вставьте в стек дочерние узлы E и D B. В это время D находится на вершине стека и стека (D, E, C);
Узел D выскочил, и никакие дочерние узлы не выдвинуты. В это время E находится наверху стека, и стек (E, C);
Вставьте узел E и одновременно вставьте дочерний узел I в E, стек (I, C);
… вниз по одному, и, наконец, обход завершен.
Код: возьмите двоичное дерево в качестве примера. Нерекурсивна
Рекурсивная реализация в глубину:
Эта статья цитируется по адресу: http://www.cnblogs.com/toSeeMyDream/p/5816682.html
Теория
Для начал немного теории. Бинарное дерево – древовидная структура данных, в которой каждый узел имеет не более двух потомков (детей). Как правило, первый называется родительским узлом, а дети называются левым и правым наследниками.
Далее по тексту я буду использовать следующее бинарное дерево.
Дерево можно обойти различными способами:
-
Обход в прямом порядке (preorder depth-first traversal) – каждый узел посещается до того, как посещены его дети. Для нашего дерева это будет последовательность: {10, 8, 4, 3, 5, 2, 9, 20, 6, 23, 21}. Для корня дерева рекурсивно вызывается следующая процедура:
- Посетить узел
- Обойти левое поддерево
- Обойти правое поддерево
-
Симметричный обход (inorder depth-first traversal) – посещается сначала левое поддерево, затем узел, затем правое поддерево: {3, 4, 2, 5, 8, 9, 10, 6, 20, 21, 23}. Для корня дерева рекурсивно вызывается следующая процедура:
- Обойти левое поддерево
- Посетить узел
- Обойти правое поддерево
-
Обход в обратном порядке (postorder depth-first traversal) – узлы посещаются снизу вверх: {3, 2, 5, 4, 9, 8, 6, 21, 23, 20, 10}. Для корня дерева рекурсивно вызывается следующая процедура:
- Обойти левое поддерево
- Обойти правое поддерево
- Посетить узел
- Обход в ширину (breadth-first traversal) – узлы посещаются уровень за уровнем сверху вниз, каждый уровень слева направо: {10, 8, 20, 4, 9, 6, 23, 3, 5, 21, 2}.
Симметричный обход (inorder depth-first traversal)
/// <summary>
/// Binary tree inorder depth-first iterator.
/// </summary>
public class BinaryTreeInorderIterator BinaryTreeIterator
{
#region Constructors
/// <summary>
/// Initializes a new instance of binary tree inorder depth-first iterator with the root
/// node of the traversing tree.
/// </summary>
/// <param name="aRoot">
/// Root node of the traversing tree.
/// </param>
public BinaryTreeInorderIterator(BinaryTreeNode aRoot)
{
Current = aRoot;
if (Current == null)
{
// The tree is empty.
return;
}
// Push the terminator.
NodeStack.Push(null);
// To initialize inorder iterator go deep to the leftmost node of the left subtree
// of the root node along the way pushing nodes traversed so far.
while (Current.Left != null)
{
NodeStack.Push(Current);
Current = Current.Left;
}
}
#endregion
#region Public methods
/// <summary>
/// Advances the iterator to the next node if possible.
/// </summary>
/// <returns>
/// Returns <see langword="true"/> if iterator has advanced to the next node, otherwise -
/// <see langword="false"/>.
/// </returns>
public override bool Next()
{
if (Current == null)
{
// Iterating finished already.
return false;
}
if (Current.Right != null)
{
// There is right subtree.
// Go deep to the leftmost node of the left subtree
// of the current node along the way pushing nodes traversed so far.
Current = Current.Right;
while (Current.Left != null)
{
NodeStack.Push(Current);
Current = Current.Left;
}
}
else
{
// There is no right subtree.
// Go a level up.
Current = NodeStack.Pop();
}
return HasNext();
}
#endregion
#region Private properties
private Stack<BinaryTreeNode> NodeStack
{
get { return mNodeStack; }
}
#endregion
#region Private data
private readonly Stack<BinaryTreeNode> mNodeStack = new Stack<BinaryTreeNode>();
#endregion
}
Connect by
Oracle имеет свой собственный синтаксис для написания
рекурсивных запросов. Сначала пример:
select d.* from departments d start with d.id = 1 connect by prior id = d.parent_id
Данный запрос проходит по дереву вниз начиная с узла, имеющего .
задает правило, по которому дерево будет обходиться.
В данном примере мы указываем, что у строк, которые должны
будут выбираться на следующем шаге, значение столбца
должно быть таким же, как значение столбца на текущем.
В конструкции не обязательно указывать некие
значения для строк. Там можно указывать любое
выражение. Те строки, для которых оно будет истинным,
и будут являть собой стартовые узлы в выборке.
Итог по применению оператора yield
Сводим все приведенные выше концепции воедино. Напишем максимально оптимальный код для вывода букв массива:
using System;
using System.Collections;
namespace abcd
{
class Bukva
{
char ch = 'А';
int end;
public Bukva(int end)
{
this.end = end;
}
public IEnumerator GetEnumerator()
{
for (int i = 0; i < this.end; i++)
{
if (i == 33) yield break; // Остановка итератора, как только заканчивается массив букв
yield return (char)(ch + i);
}
}
// Создание именованного итератора
public IEnumerable imennovaniyItr(int begin, int end)
{
for (int i = begin; i <= end; i++)
{
yield return (char)(ch + i);
}
}
}
class Program
{
static void Main()
{
Console.Write("Какое количество символов показать? ");
int i = int.Parse(Console.ReadLine());
Bukva lt = new Bukva(i);
Console.WriteLine("\nДемонстрация букв: \n");
foreach (char c in lt)
Console.Write(c + " ");
Console.Write("\nВведите пределы\n\nMin: ");
int j = int.Parse(Console.ReadLine());
Console.Write("Max: ");
int y = int.Parse(Console.ReadLine());
Console.WriteLine("\nБуквы в указанном диапазоне: \n");
foreach (char c in lt.imennovaniyItr(j, y))
Console.Write(c + " ");
Console.ReadLine();
}
}
}
