найти наименьшую глубину листового узла в BST - PullRequest
Новая
       22

найти наименьшую глубину листового узла в BST

1 голос
/ 04 ноября 2011

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

Ответы [ 2 ]

2 голосов
/ 04 ноября 2011

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

См., Например, псевдокод в мой ответ на«Breadth First против Depth First» просто добавьте еще одно условие в цикл while.

BTW - это даст вам a лист с минимальной глубиной, так как может бытьбольше, чем один на этой глубине.Получить полный набор листьев минимальной глубины немного сложнее.Я думаю, что пойти с итеративной стратегии углубления .

Выяснить, какой уровень этот узел один.

Три варианта:

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

С другой стороны, вы можете следить за ходом.Вы используете три счетчика levelCounter, thisLevelCounter и nextLevelCounter.Каждый раз, когда вы переходите на новый узел, вы уменьшаете thisLevelCounter, а когда он достигает нуля, вы перемещаетесь вниз на уровень, поэтому 

levelCounter++
thisLevelCounter = nextLevelCounter
nextLevelCounter = 0

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

Наконец, стратегия итеративного углубления дает вам уровень успеха бесплатно (какая итерация находит его ...) и имеет тот же порядок производительности (хотя инемного выше множитель) в качестве ширины первого поиска.

0 голосов
/ 25 марта 2013

Здесь версия кода (надеюсь, я не пропустил ни одной проверки ошибок): 

void min_leaf(node_t *t, int *min, int lev, node_t **n) {
    if (!t) {
            return;
    }   

    if (lev > *min) {
            printf("Back from %d at lev %d, min: %d already found\n",
                            t->key,
                            lev,
                            *min);
            return;
    }   

    if (!t->left && !t->right) {
            if (*min > lev) {
                    *min = lev;
                    *n = t;
            }   
    } else {
            min_leaf(t->left, min, lev+1, n); 
            min_leaf(t->right, min, lev+1, n); 
    }   
}

void bst_print_min_leaf(bst_t* bst) {
    int min = 10000; /* Replace it with some really large number */
    node_t *minn = NULL;

    min_leaf(bst->root, &min, 0, &minn); /*level: root is level 0 */
    if (minn) printf("min leaf is at depth: %d: (%p:%d)\n", min, minn, minn->key);
}
...