Косые двоичные деревья

Question

1) Что понимается под термином «несбалансированное двоичное дерево» и как мы можем написать алгоритм для его проверки?

2) У меня есть проблема, которая требует написать функцию для проверки глубины двоичного файла.дерево.Я думаю, что это будет работать, но не уверен ....:

function getDepth(Node n){
    if(node == null){
        return 0;
    }
    return 1 + Math.max(getDepth(node.left), getDepth(node.right));
}
getDepth(root);

Может кто-нибудь дать мне указатели ...

Answer 1

Перекошенное бинарное дерево - это дерево, которое имеет только один тип поддеревьев. Если дерево имеет только левые поддеревья, оно остается перекошенным и наоборот.

Answer 2

1) Перекошенное двоичное дерево не является распространенным на 100% общим термином (даже Google запутывается).Поищите в своих заметках к лекциям или книге, чтобы понять, что они означают.

1. Чтобы проверить, что дерево имеет столько уровней, сколько узлов, вы можете просто использовать функцию, которая у вас уже есть.который подсчитывает уровни и другую функцию для подсчета количества узлов.

   Однако вы должны быть в состоянии создать другой, более эффективный алгоритм, который завершается раньше, если if обнаружит, что число узлов не может быть таким же, какколичество уровней.

2. Функция глубины правильная.В конце концов, не взято ли это прямо из определения глубины дерева?

   (единственно возможный зазор - это глубина (ноль) = 1. Просто убедитесь, что вам не нужна глубина (ноль) = 0)