Как найти глубину определенного узла в BST в c

#c #binary-search-tree #depth

Вопрос:

Я пытаюсь найти глубину определенного узла, отмеченного указателем в c, но, похоже, я не могу понять это правильно

 int depth(Node *root, Node *N){  // Need to find the root N  // At the same time count how many depths you can go down    // If the root is NULL, then no tree and return -1  if (root == NULL){  return -1;  }  // If the root node equals the node N, then return 0  if (root-gt;data == N-gt;data){  return 0;  }  // Search the tree and add one each time recursion called  int count = -1;  if (N-gt;data lt; root-gt;data){  root-gt;left-gt;data = depth(root-gt;left, N);  count  ;  }  else if (N-gt;data gt; root-gt;data){  root-gt;right-gt;data = depth(root-gt;right, N);  count  ;  }  else{    }  return count; }

Любая помощь в решении этой проблемы будет признательна.

1. Почему вы изменяете data при поиске по дереву?

2. Почему вы изменяете содержимое дерева, присваивая возвращаемое значение depth() to root-gt;left-gt;data или root-gt;right-gt;data ?

3. Я пытаюсь рекурсивно искать в дереве данный узел и после каждой рекурсии добавлять 1 для подсчета, чтобы действовать как глубина. Я не силен в Си, так что просто стараюсь изо всех сил

4. прежде всего, зачем изменять данные? во-вторых, кажется, что счетчик является локальным для функции, и хотя функция возвращает его, вы не накапливаете его при выходе из рекурсии, поэтому он всегда будет равен 1.

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

Ответ №1:

Псевдокод для такой функции соответствует этому, предполагая, что root = уровень 0:

 int search (const node_t* node, int level) {  if(node == NULL)  return -1;  if(node-gt;data == key)  return level;   const node_t* node next;   if(node-gt;data lt; key)  next = node-gt;right;  else if(node-gt;data gt; key)  next = node-gt;left    return search (next, level 1); }

Сначала называется как search(root, 0);

Хотя, как обычно, рекурсия в C почти наверняка является неправильным решением любой проблемы. Вместо этого вышеперечисленное можно довольно тривиально переписать как разумные, читаемые, быстрые циклы.

1. Итак, вы бы рекомендовали в C делать это итеративно — анализировать указатель на корень, а также указатель на значение, которое должно быть определено глубиной, находить это значение и затем возвращать уровень, на котором оно находится 1 ?

2. @Фрейзер Да, что-то похожее на вышесказанное, но переключите обременительную рекурсию на что-то подобное for(cost node_t* i=root; i!=NULL; i=next) { ... } . Рекурсия довольно бесполезна в C, так как она никогда не бывает быстрее цикла, часто намного медленнее, намного опаснее и подвержена ошибкам и часто труднее читается. Основными способами использования рекурсии являются: запутывание, кодовое поле, позирование, сбивающее с толку студентов.