Двоичное дерево - Нахождение количества узлов глубиной k

Question

Следующая функция работает с двоичным деревом. Функция будет принимать указатель на корень дерева и неотрицательный int k. Он должен возвращать количество узлов глубины k от корня.

struct treenode {
  int data;
  struct treenode* left;
  struct treenode* right;
}

int numNodesHeightK(struct treenode* root, int k){
  if(root == NULL) return 0; //if the tree is empty return 0
  if(k == 0) return 1; //if k = 0, then the root is the only node to return 

  //How does this statement work?
  return numNodesHeightK(root->left, k-1) + numNodesHeightK(root->right, k-1);
}

Если бы кто-то мог просто объяснить логику последнего утверждения. Я не вижу, как эта строка кода может вернуть правильную глубину.

Answer 1

Для каждого узла вы хотите сложить количество узлов на глубине k от каждого из поддеревьев. Это означает прохождение этих поддеревьев для узлов глубиной k-1 от их соответствующих корней (левого и правого поддеревьев текущего узла). Когда k достигает 0, это означает возврат 1 для этого узла - так как это глубина k от исходного корня.

Последний оператор выполняет именно эту операцию - сначала пересекает левое поддерево, а затем правое поддерево, находит количество узлов на глубине k из текущего узла, складывает их вместе и затем возвращает результат.

Алгоритм довольно прост - нарисуйте тестовое дерево на бумаге и пошагово проработайте его. Логика должна выскочить на тебя довольно быстро.

Answer 2

Просто подумай об этом рекурсивно ...

Сколько узлов в поддереве, чей каталог null? 0

if (root == NULL) return 0;

Сколько узлов находится под узлом на глубине 0? 1 (сам узел).

if (k == 0) return 1;

Сколько узлов и подузлов имеет дерево в противном случае? Узлы на левой боковой ветви плюс узлы на правой боковой ветви. Каждая ветвь находится на более низком уровне.

// left side
numNodesHeightK(root->left, k-1) +
// right side 
numNodesHeightK(root->right, k-1)

Answer 3

Теория состоит в том, что общее количество узлов на заданной глубине (скажем, глубина = 5) совпадает с суммой узлов глубины = 4, подсчитанной от левого и правого дочерних элементов. (потому что переход к ребенку уже вводит глубину 1).

Итак, давайте найдем количество узлов на глубине 4 у левого ребенка:

numNodesHeightK(root->left, k-1)

и количество узлов на 4-й глубине у правого ребенка:

numNodesHeightK(root->right, k-1)

и сложите их вместе, чтобы получить ответ для получения количества узлов глубины 5 от нашего текущего узла.

Одно это не решает проблему, оно просто разбивает ее на две более простые, более мелкие части. Проблема не будет полностью решена до тех пор, пока вы не запросите количество узлов на глубине 0, которое, очевидно, равно 1. Это реализовано в базовом случае функции :

if(k == 0) return 1; //if k = 0, then the root is the only node to return 

И, наконец, вы используете термины Высота и Глубина взаимозаменяемо, что вводит в заблуждение, если вы пытаетесь говорить о «спуске» или «поднятии» дерева. Выберите одно соглашение и придерживайтесь его.

Answer 4

Невозможно понять, что одна строка изолирована, потому что функция рекурсивная, а эта строка - та , которая рекурсивна.

Но есть только три строки, поэтому мы можем легко развить понимание всего этого.

Чтобы подсчитать узлы на заданной глубине, необходимо пройти дерево до этой глубины.

Так что это означает, что мы рекурсивно берем каждую левую и правую ветви.

Первые две исполняемые строки

Если мы пройдем вниз от конечного узла до нулевого узла, мы просто вернем 0. Если мы окажемся на нужной глубине, мы можем остановить любое бессмысленное перемещение дальше вниз по дереву и просто вернуть 1, потому что наш экземпляр Рекурсивная функция приземлилась на одном узле целевой глубины. Эта линия не позволяет нам перебирать ненужно глубоко, а также предоставляет счет для ветви, на которой мы находимся.

Последняя строка

Итак, наконец, ваша последняя строка. На каждом более мелком уровне необходимо спускаться глубже в дерево, и в рекурсивной реализации это делается путем вызова нового экземпляра функции для каждой ветви дерева. Эта строка может быть снова выполнена вызываемым экземпляром, пока сам граф вызовов кумулятивно не отражает реальное дерево, и каждый уровень не возвращает все большие и более консолидированные суммы на предыдущие уровни, что в итоге возвращает одно потенциально довольно большое число из одного экземпляра верхний узел.

Answer 5

Чтобы нарисовать картину того, как это работает ...

Подумайте, как будто у вас есть эта группа на миссии, и есть эти туннели, которые продолжают разветвляться на два субтуннеля.Цель состоит в том, чтобы узнать после стольких вилок, какой субтуннель открывается в пещеру.Расстояние между вилами составляет одну единицу расстояния.

Каждый раз, когда вы достигаете развилки в туннеле, текущая группа в этой ветке делится пополам и отправляет каждую половину вниз по обоим подтоннелям.Когда группа делится на K раз, они останавливаются и смотрят на место.Затем они возвращаются на поверхность, и каждый человек рассказывает, нашел ли он комнату на расстоянии от входа.Если какой-либо из подгрупп подойдет к тупику до расстояния k, они возвращаются назад и говорят, что места нет.

Они суммируют итоги и сообщают вам.

Комнатыузлы.Вилки являются дочерними узлами каждого узла.Подкоманды - это вызовы вашего метода в стеке.