В чем разница между высотой дерева и высотой?
Это простой вопрос из теории алгоритмов. Разница между ними заключается в том, что в одном случае вы подсчитываете количество узлов, а в другом-количество ребер на самом коротком пути между корневым и конкретным узлом. Что есть что?
6 ответов:
Я узнал, что глубина и высота свойства узел:
The глубина узла-количество ребер от узла до корневого узла дерева.
корневой узел будет иметь глубину 0.The высота узла-это количество ребер на длинный путь от узла к листу.
конечный узел будет иметь высоту 0.свойства a дерево:
The высота дерева будет высота его корневого узла
или, что то же самое, глубина его самого глубокого узла.The диаметр (или ширина) дерева-это число узлы на самом длинном пути между любыми двумя конечными узлами. Дерево ниже имеет диаметр 6 узлы.
высота и глубина дерева равна...
но высота и глубина узла не равны, потому что...
высота вычисляется путем перехода от данного узла к самому глубокому возможному листу.
глубина вычисляется от обхода от корня до заданного узла.....
согласно Cormen et al. Введение в алгоритмы (приложение B. 5.3), глубина узла X в дереве T определяется как длина простого пути (количество ребер) от корневого узла T до X. высота узла Y - это количество ребер на длинной вниз простой путь от Y до листа. Высота дерева определяется как высота его корневого узла.
обратите внимание, что простой путь-это путь без повторения вершин.
высота a дерево равно максимальной глубине a дерево. Глубина узла и высота узла не обязательно равны. См. рисунок B. 6 3-го издания Cormen et al. для иллюстрации этих понятий.
Я иногда видел проблемы с просьбой считать узлы (вершины) вместо ребер, поэтому попросите разъяснить, если вы не уверены, что должны считать узлы или ребра во время экзамена или собеседования.
Простой Ответ:
глубину:
1. дерево:количество ребер/дуг от корневого узла до листового узла дерева называется глубиной дерева.
2. узел:количество ребер/дуг от корневого узла до этого узла называется глубиной этого узла.
другой способ понять эту концепцию заключается в следующем: Глубина: нарисуйте горизонтальную линию в корневом положении и рассматривайте эту линию как землю. Таким образом, глубина корня равна 0, и все его дочерние элементы растут вниз, поэтому каждый уровень узлов имеет текущую глубину + 1.
Высота: та же горизонтальная линия, но на этот раз положение Земли-это внешние узлы, которые являются листом дерева и отсчитывают вверх.
Я хотел сделать этот пост, потому что я студент бакалавриата CS и все больше и больше мы используем OpenDSA и другие учебники с открытым исходным кодом. Похоже, что из самого рейтингового ответа, что способ обучения высоте и глубине изменился от одного поколения к другому, и я публикую это, чтобы все знали, что это несоответствие теперь существует и, надеюсь, не вызовет ошибок в каких-либо программах! Спасибо.
с OpenDSA Data Structures & Algos book:
Если n1, n2,..., nk - это последовательность узлов в дереве такие что nЯ является родителем nЯ+1 для 11 до nk. Длина пути равна k-1. Если существует путь от узла R к узлу м, то р является предком M, и M является потомком R. таким образом, все узлы в дереве являются потомки корня дерева, в то время как корень является родоначальником все узлы. глубина узла M в дереве равна длине путь от корня дерева до м. Высота дерева Еще одна чем глубина самого глубокого узла в дереве. все узлы глубины d находятся на уровне d в дереве. Корень является единственным узлом на уровне 0, и его глубина-0.
рисунок 7.2.1: двоичное дерево. Узел A является корнем. Узлы B и C Дети А. Узлы B и D вместе образуют поддерево. Узел B имеет два ребенка: его левый ребенок-пустое дерево и его правый ребенок D. узлы A, C и E являются предками G. узлы D, E и F составьте Уровень 2 дерева; узел A находится на уровне 0. Края от К С К Е К Г образуют путь длиной 3. Узлы D, G, H И I являются листья. Узлы A, B, C, E и F являются внутренними узлами. Глубина из I - 3. Высота этого дерева-4.
