4

Есть дерево BST заданное как

struct treeNode {
    int info;
    treeNode *left //левый
    treeNode *right; // правый
    treeNode *parent; // предыдущий
};

Нужно запилить метод, который возвращал бы указатель на самый дальний листик этого дерева(конец самого длинного пути). Если таких несколько, то на любой из них.

Нужно достать именно указатель на листик, потому что от него дальше я пойду назад до корня зеркально разворачивать дерево относительно этого пути вот так:

void mirror (treeNode *farthestLeaf) {
    treeNode *tmp = NULL;
    while (farthestLeaf->parent != NULL) {
        tmp = farthestLeaf->parent->left;
        farthestLeaf->parent->left = farthestLeaf->parent->right;
        farthestLeaf->parent->right = tmp;
        farthestLeaf = farthestLeaf->parent;
    }
}

Есть ли у вас какие-нибудь идеи?

5
  • дерево сбалансировано?
    – Fat-Zer
    28 фев 2019 в 16:34
  • Добрый вечер, @fat-zer. Нет не сбалансировано.
    – acc
    28 фев 2019 в 16:36
  • 2
    тогда банальный обход на основе поиска в глубину — ничего эффективней не придумать...
    – Fat-Zer
    28 фев 2019 в 16:37
  • да, я правильно понимаю, что нужно найти самую глубокую вершину, т.е. с самым длинным путём от корня?
    – Fat-Zer
    28 фев 2019 в 16:39
  • @fat-zer, да, все верно. Задание именно такое
    – acc
    28 фев 2019 в 16:41

1 ответ 1

3

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

Пример реализации:

const struct treeNode* findDeapest(const struct treeNode* cur, int *deapth) {
  const struct treeNode *rv = cur;
  int curDeapth=*deapth;

  if (cur->left) {
    (*deapth)++;
    rv = findDeapest (cur->left, deapth);
  }
  if (cur->right) {
    int rightDeapth=curDeapth+1;
    const struct treeNode *rightDeapest = findDeapest (cur->right, &rightDeapth);
    if (rightDeapth>*deapth) {
      *deapth = rightDeapth;
      rv = rightDeapest;
    }
  }
  return rv;
}

//вызов
int deapth = 0;
struct treeNode* deapest = findDeapest (myTreeRooteNode, &deapth);
0

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.