Нужна помощь в написании функции, чтобы определить, сколько детей имеет массив двоичного дерева - PullRequest
Новая
       2

Нужна помощь в написании функции, чтобы определить, сколько детей имеет массив двоичного дерева

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

Для моего класса CSCE 230 я пишу программу, которая работает с массивами двоичного дерева, и часть нашего назначения - написать функцию, которая определяет, является ли дерево сбалансированным. Для тех, кто не знает, чтобы дерево было сбалансировано, высота левого и правого поддеревьев не может отличаться более чем на 1. Мы с ней предпочли бы, чтобы функция была рекурсивной, но это ни в коем случае не должно быть.

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

root из дерево имеет индекс 0.

Массив, в котором хранятся значения в дереве, называется values, мы используем values.length для представления его длины.

Предполагается, что узел расположен по индексу n его левый потомок имеет индекс 2n + 1, а его правый потомок - по индексу 2n + 2.

Мы используем «», чтобы указать, что у узла нет левого и / или правого child.

Предполагая, что я все правильно сохранил, что может быть причиной функции ниже, которая должна измерять высоту поддерева (включая root поддерева) для возврата неверного ответ 

/**
 * Determines if the tree is balanced. A tree is balanced if a 
 * node's left and right subtree heights differ by at most one.
 * @return True if balanced, false otherwise.
 */
public boolean isBalanced() { 
    boolean balanced = false;
    if (values[0] == null) balanced = true;
    // count non-null subchildren for all nodes. Use P-L-R format (parent-L-R)
    // then for all non-leaf nodes, subtract the larger from the smaller.

    for (int i = 0; i < values.length; i++) {
        if (values[i] != "") System.out.println("values["+i+"] has " + getNonNullSC(i) + " non-null children.");
    }

    for (int i = 0; i < values.length; i++) {
        for (int j = 0; j < values.length; j++) {
            if (Math.abs(getNonNullSC(i)-getNonNullSC(j)) >= 0 && Math.abs(getNonNullSC(i)-getNonNullSC(j)) <= 1)
                balanced = true;
        }
    }

    return balanced;
}

// returns the number of non-null children a subtree has
private int getNonNullSC(int a) {
    int count = 0;
    if (a+a+2 < values.length) {
        if (values[a] == null) count = 1; // if it is a leaf node, it has no children
        else if (values[a+a+1] != null) { // if it has a left child
            if (values[a+a+2] == null) count = 2; // it has one child if no right child
            else count = 2; // otherwise it has two children
        }
        else if (values[a+a+2] != null) { // if it has a right child
            if (values[a+a+1] == null) count = 1; // it has one child if no left child
            else count =  2; // otherwise it has two children
        }
    }
    return count;
}

1 Ответ

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

Похоже, вы забыли включить root в какой-то момент.

Простая проверка исправности заключается в том, что вы помните, что у вас есть 4 случая: Случай 1: узел не существует, поэтому посчитайте = 0 Случай 2: у узла нет дочерних элементов, поэтому count = 1 Случай 3: у узла есть один дочерний элемент, поэтому count = 2 (потому что вы сказали, что мы включаем root) Случай 4: у узла есть два дочерних элемента, поэтому count = 3.

Ваш код ни в коем случае не возвращает 3, потому что вы забыли включить root.

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

Примечание: вы проверяете левый и правый узлы дважды. Вы могли бы упростить свой код, чтобы он выглядел примерно так, поскольку нам все равно, какой узел считается первым: 

private int getNonNullSC(int a) {
int count = 0;
if (a+a+2 < values.length) {
    if (values[a] == null) 
    {
        count = count + 1; // Or simplified: count++; which means count is now 1
    }

    if (values[a+a+1] != null) {
        count++; // which means counts is now 2
    }

    if (values[a+a+2] != null) {
        count++; // which means count is now 3 or 2 if there was no left node
    }
}
return count;

}

...