1.1. Определение глубины дерева
При определении минимальной (максимальной) длины ветви дерева каждая вершина должна получить значения минимальных длин ветвей от потомков, выбрать из них наименьшую и передать предку результат, увеличив его на 1 — » добавить себя» .
//—- Определение ветви минимальной длины
Для отслеживания процесса » погружения» достаточно дополнительной переменной, которая уменьшает свое значение на 1 при очередном рекурсивном вызове.
//——Включение вершины в дерево на заданную глубину
if (d == 0) return 0; // Ниже не просматривать
if (Insert(ph->p[i], v , d-1)) return 1; // Вершина включена
Для включения простейшим способом нового значения в дерево в ближайшее в корню место достаточно соединить две указанные функции вместе.
1.2. Операции поиска и включения элемента в дерево
При обнаружении в дереве первого значения, удовлетворяющего условию, необходимо прервать не только текущий шаг рекурсии, но и все предыдущие. Поэтому цикл рекурсивного вызова прерывается сразу же, как только потомок возвратит найденное в поддереве значение. Текущая вершина должна » ретранслировать» полученное от потомка значение к собственному предку (» вверх по инстанции» ).
//—- Поиск в дереве строки, длиной больше заданной
if (strlen(q->str)> 5) return q->str; // Найдена в текущей вершине
char *child=big_str(q->p[i]); // Получение строки от потомка
if (child!=NULL) return child; // Вернуть ее » от себя лично»
return NULL;> // Нет ни у себя, ни у потомков
Производится полный обход дерева, в каждой вершине стандартный контекст выбора минимального из текущего значения в вершине и значений, полученных от потомков при рекурсивном вызове функции.
//—- Поиск максимального в дереве
1.3. Оптимизация поиска в дереве
Основное свойство дерева соответствует пословице » дальше в лес — больше дров» . Точнее, количество просматриваемых вершин от уровня к уровню растет в геометрической прогрессии. Если известен некоторый критерий частоты использования различных элементов данных (например, более короткие строки используются чаще, чем длинные), то в соответствии с ним можно частично упорядочить данные по этому критерию с точки зрения их » близости» к корню : в нашем примере в любом поддереве самая короткая строка находится в его корневой вершине. Алгоритм поиска может ограничить глубину просмотра такого дерева.
//— Дерево оптимизацией : короткие ключи ближе к началу
void *data; // Искомая информация
void *find(dtree *q, char *keystr) // Поиск по ключу
if (strcmp(q->key,keystr)==0) return q->data; // Ключ найден
return NULL; // Короткие строки — ближе к корню
if ((s=find(q->p[i],keystr))!=NULL) return s;
Функция включения в такое дерево ради сохранения свойств должна в каждой проходимой ею вершине рекурсивно » вытеснять» более длинную строку в поддерево и заменять ее на текущую (новую), более короткую.
Источник
Как рассчитать глубину бинарного дерева поиска
Я хотел бы рассчитать суммирование глубин каждого node двоичного дерева поиска. Индивидуальные глубины элементов еще не сохранены.
Изменение вопроса после того, как люди предоставили ответы, заставит первоначальные ответы казаться не связанными с последним вопросом. Также вы не можете принять два ответа. Было бы лучше задать новый вопрос, т.е. на новой странице. Вы также можете принять ответ на оригинальный вопрос.
10 ответов
int countChildren(Node node)
И чтобы получить сумму глубин каждого ребенка:
int sumDepthOfAllChildren(Node node, int depth) < if ( node == null ) return 0; // starting to see a pattern? return depth + sumDepthOfAllChildren(node.getLeft(), depth + 1) + sumDepthOfAllChildren(node.getRight(), depth + 1); >Теперь, надеюсь, информативное объяснение в случае, если это домашнее задание. Подсчет количества узлов довольно прост. Прежде всего, если node не является node ( node == null ), он возвращает 0. Если это node, он сначала подсчитывает свое «я» ( 1 ), а также число узлов в его левом поддереве плюс число узлов в его правом поддереве. Еще один способ подумать — вы посещаете каждый node через BFS и добавляете его к счету для каждого node, который вы посещаете.
Суммирование глубин аналогично, за исключением того, что вместо добавления только одного для каждого node, node добавляет глубину его самого. И он знает глубину своего «я», потому что его родитель рассказал об этом. Каждый node знает, что глубина его детей — это собственная глубина плюс одна, поэтому, когда вы получаете глубину левого и правого дочерних элементов node, вы сообщаете им, что их глубина — это текущая глубина node плюс 1.
И снова, если node не является node, он не имеет глубины. Поэтому, если вам нужна сумма глубины всех корневых node детей, вы передаете в корневой каталог node и корневую глубину node следующим образом: sumDepthOfAllChildren(root, 0)
Рекурсия весьма полезна, это совсем другой способ думать о вещах и берет практику, чтобы привыкнуть к ней
Источник
Нахождение глубины бинарного дерева
У меня возникли проблемы с пониманием этого maxdepth-кода. Любая помощь будет оценена по достоинству. Вот пример, который я привел.
int maxDepth(Node *&temp) < if(temp == NULL) return 0; else < int lchild = maxDepth(temp->left); int rchild = maxDepth(temp->right); if(lchild
> В основном, я понимаю, что функция рекурсивно вызывает себя (для каждого левого и правого случаев), пока не достигнет последнего узла. как только он это делает, он возвращает 0, затем 0 +1. то предыдущий узел равен 1 +1. затем следующий — 2 +1. если есть bst с 3 левыми дочерними элементами, int lchild вернет 3. а дополнительный + 1 — корень. Поэтому мой вопрос заключается в том, откуда все эти +1. он возвращает 0 на последнем узле, но почему он возвращает 0 +1 и т.д., когда он идет вверх по левым/правым дочерним узлам? Я не понимаю, почему. Я знаю, что это так, но почему?
8 ответов
Помните, что в бинарных деревьях узел имеет не более 2-х детей (слева и справа)
Это рекурсивный алгоритм, поэтому он называет себя снова и снова.
Если temp (рассматриваемый узел) имеет значение null, он возвращает 0, поскольку этот узел ничего не должен и не должен учитываться. это основной случай.
Если рассматриваемый узел не является нулевым, у него могут быть дети. поэтому он получает максимальную глубину левого под дерева (и добавляет 1, для уровня текущего узла) и правого поддерева (и добавляет 1 для уровня текущего узла). он затем сравнивает два и возвращает большее из двух.
Он погружается в два поддерева (temp-> влево и temp-> вправо) и повторяет операцию до тех пор, пока не достигнет узлов без детей. в этот момент он будет вызывать maxDepth слева и справа, который будет null и возвращает 0, а затем начнет возвращать цепочку вызовов.
Поэтому, если у вас есть цепочка из трех узлов (скажем, root-left1-left2), она перейдет влево2 и вызовет maxDepth (слева) и maxDepth (справа). каждый из них возвращает 0 (они равны нулю). то он возвращается влево2. он сравнивается, оба равны 0, поэтому больший из них, конечно, равен 0. он возвращает 0 + 1. то мы находимся налево1 — повторяет, обнаруживает, что 1 является большим из его правых справа (возможно, они одинаковы или не имеют права ребенка), поэтому он возвращает 1 + 1. теперь мы находимся у корня, то же самое, он возвращает 2 + 1 = 3, что является глубиной.
Рассмотрим эту часть (большего дерева):
Теперь мы хотим рассчитать глубину этой части дерева, поэтому мы передаем указатель на A как свой параметр.
Очевидно, указатель на A не является NULL , поэтому код должен:
- call maxDepth для каждого из детей A (левая и правая ветки). A->right — B , но A->left явно NULL (поскольку A не имеет левой ветки)
- сравните их, выберите наибольшее значение
- вернуть это выбранное значение + 1 (поскольку сам A берет уровень, не так ли?)
Теперь мы рассмотрим, как maxDepth(NULL) и maxDepth(B) .
Первое довольно легко: первая проверка сделает maxDepth возвращение 0. Если другой ребенок были NULL тоже, как глубина будет равна (0), и мы должны возвращать 0 + 1 для A сам.
Но B не пуст; он не имеет ветвей, хотя, поэтому (как мы заметили) его глубина равна 1 (наибольшая из 0 для NULL на обеих частях + 1 для самого B ).
Теперь вернитесь к A maxDepth его левой ветки ( NULL ) равен 0, maxDepth его правой ветки равно 1. Максимум из них равен 1, и мы должны добавить 1 для самого A , поэтому он 2.
Дело в том, что те же самые шаги должны быть выполнены, когда A является лишь частью большего дерева; результат этого вычисления (2) будет использоваться на более высоких уровнях вызовов maxDepth .
Источник