Запросы по дереву для поиска длины пути в log n time [duplicate]

Question

Запросы по дереву для поиска длины пути в log n time [duplicate]

Я могу думать о сценарии, где требуется пустой оператор (не для условия if, а для цикла while).

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

    System.out.println("Enter Y to proceed. Waiting...");
    System.out.println("");

    while(!(new Scanner(System.in).next().equalsIgnoreCase("Y")));

    System.out.println("Proceeding...");
    // do the work here

2

algorithm tree

задан venkysmarty 21 September 2012 в 12:27

1 ответ

Другие вопросы по тегам:

algorithm tree

Похожие вопросы:

score 1 · Answer 1

             A
           /   \
          B     C
         / \   / \
        D   E F   G

Здесь N = общее число. узлов в дереве = 7

(длина пути листового узла берется как ноль.)

Acc. к рекурсивному определению:

Path length of tree = Path length with Root A
                    = Path length with Root B + Path length with Root C + (7-1)

                    = (Path length with Root D + Path length with Root E + (3-1))
                    + (Path length with Root F + Path length with Root G + (3-1))
                    + (7-1)

                    = ((0 + 0 + 2) + (0 + 0 + 2)) + 6
                    = 10

Его реализация может быть следующей:

int Recurse(Node root, int totalNodes)
{
    if (totalNodes == 1)
        return 0;
    int noOfNodes1 = CountNodes(root.left);
    int noOfNodes2 = CountNodes(root.right);
    return ( Recurse(root.left, noOfNodes1)
           + Recurse(root.right, noOfNodes2) + totalNodes - 1);
}

1

ответ дан phant0m 17 August 2018 в 14:22

1

Ваша интерпретация неверна. В вашем примере есть поддеревья B и C. Оба они имеют длину пути 2: 3 узла - 1. Теперь для всего поддерева это 7 - 1 + оба поддерева = 10. – phant0m 21 September 2012 в 12:39
2

@phantom: это 14. – Azodious 21 September 2012 в 12:43
3

Нет, это 10. Ошибка, которую вы сделали, заключается в том, что длина пути дерева с единственным узлом - 0, а не 1. – verdesmarald 21 September 2012 в 12:45
4

Вы имеете в виду, что листовой узел находится на уровне нуля? если да, то это может быть 10. – Azodious 21 September 2012 в 12:45
5

Это все еще некорректно: их не должно быть. Дерево с единственным узлом имеет длину пути 0. Исходя из этого поддерева B: 0 + (3-1) = 2. – phant0m 21 September 2012 в 12:47