이것은 알고리즘 이론의 간단한 질문입니다.
이들의 차이점은 루트와 콘크리트 노드 사이의 최단 경로에서 노드 수와 다른 수의 가장자리를 계산한다는 것입니다.
어느 게 어느 건지?
답변
깊이와 높이는 노드의 속성이라는 것을 배웠습니다 .
-
노드 의 깊이 는 노드에서 트리의 루트 노드까지의 가장자리 수입니다.
루트 노드의 깊이는 0입니다. -
노드 의 높이는 노드에서 리프까지 가장 긴 경로 의 가장자리 수입니다 .
리프 노드의 높이는 0입니다.
나무의 속성 :
-
높이 나무는 루트 노드의 높이 것
또는 동등의 깊은 노드의 깊이. -
직경 (또는 폭 나무의가)의 수 의 노드 두 잎 노드 사이의 가장 긴 경로에. 아래 나무의 지름은 6 노드입니다.
답변
나무의 높이와 깊이는 같습니다 …
그러나 노드의 높이와 깊이는 같지 않기 때문에 …
주어진 노드에서 가능한 가장 깊은 리프로 이동하여 높이가 계산됩니다.
깊이는 루트에서 주어진 노드까지 순회에서 계산됩니다 …..
답변
Cormen et al.에 따르면 알고리즘 소개 (부록 B.5.3)에서 트리 T의 노드 X 깊이는 T의 루트 노드에서 X까지의 간단한 경로 (가장자리 수)의 길이로 정의됩니다. 노드 Y의 높이는 Y에서 잎까지 가장 긴 하향 단순 경로 의 모서리 수입니다 . 나무의 높이는 루트 노드의 높이로 정의됩니다.
단순 경로는 반복 정점이없는 경로입니다.
(A)의 신장 트리 (A)의 최대 깊이와 동일하다 트리 . 노드의 깊이와 노드의 높이가 반드시 같을 필요는 없습니다. Cormen et al.의 3 판의 그림 B.6을 참조하십시오. 이러한 개념을 설명합니다.
때로는 가장자리 대신 노드 (정점)를 계산하도록 요청하는 데 문제가 있으므로 시험이나 면접 중에 노드 또는 가장자리를 계산 해야하는지 확실하지 않은 경우 설명을 요청하십시오.
답변
간단한 답 :
깊이 :
1. 나무 : 루트 노드에서 나무의 잎 노드까지 의 가장자리 / 호의 수 를 나무의 깊이라고합니다.
2. Node : 루트 노드에서 해당 노드까지 의 모서리 / 호수 를 해당 노드의 깊이라고합니다.
답변
이러한 개념을 이해하는 또 다른 방법은 다음과 같습니다. 깊이 : 루트 위치에 수평선을 그리고이 선을지면으로 취급합니다. 따라서 루트의 깊이는 0이고 모든 하위 노드는 아래쪽으로 자라므로 각 노드 레벨은 현재 깊이 + 1을 갖습니다.
높이 : 같은 수평선이지만 이번에는 지상 위치는 나무의 잎인 외부 노드입니다.
답변
저학년 CS 학생이기 때문에이 게시물을 만들고 싶었습니다. OpenDSA 및 기타 오픈 소스 교재를 점점 더 많이 사용하고 있습니다. 높이와 깊이를 가르치는 방식이 한 세대에서 다음 세대로 바뀌 었다는 최고 등급의 답변처럼 보입니다.이 게시물을 게시하여 모든 사람들 이이 불일치가 존재하고 희망적으로 어떤 버그도 일으키지 않을 것이라는 것을 알고 있습니다 프로그램들! 감사.
로부터 OpenDSA 데이터 구조 및 Algos 책 :
n 1 , n 2 , …, n k 가 트리에서 노드의 시퀀스이므로 n i 가 1 <= i <k에 대한 n i +1 의 부모 인 경우이 시퀀스를 n의 경로라고합니다. 1 내지 n k . 경로의 길이는 k-1입니다. 노드 R에서 노드 M까지의 경로가있는 경우 R은 M의 조상이고 M은 R의 자손입니다. 따라서 트리의 모든 노드는 트리의 루트의 자손이며 루트는 상위입니다. 모든 노드의. 트리에서 노드 M의 깊이는 트리의 루트에서 M까지의 경로 길이입니다. 트리의 높이는 트리에서 가장 깊은 노드의 깊이보다 하나 더 큽니다.깊이 d의 모든 노드는 트리에서 레벨 d에 있습니다. 루트는 레벨 0에서 유일한 노드이며 깊이는 0입니다.
그림 7.2.1 : 이진 트리. 노드 A가 루트입니다. 노드 B와 C는 A의 자녀입니다. 노드 B와 D는 함께 서브 트리를 형성합니다. 노드 B에는 두 개의 자식이 있습니다. 왼쪽 자식은 빈 트리이고 오른쪽 자식은 D입니다. 노드 A, C 및 E는 G의 조상입니다. 노드 D, E 및 F는 트리의 레벨 2를 구성합니다. 노드 A는 레벨 0에 있습니다. A에서 C로, E에서 G 로의 가장자리는 길이 3의 경로를 형성합니다. 노드 D, G, H 및 I는 나뭇잎입니다. 노드 A, B, C, E 및 F는 내부 노드입니다. I의 깊이는 3입니다.이 나무의 높이는 4입니다.
답변
