트리의 깊이와 자손 계산하기

Question

여러분이이 작업을 수행하는 알고리즘을 도와 줄 수 있습니까? 선주문, inorder 및 postorder가 구현되어 있으며 이러한 명령 중 하나를 사용하여 트리를 탐색하는 힌트가 제공됩니다. 나는 노드를 레이블링 (또는 "방문")하기 위해 점을 사용하고있다.

깊이는 루트에서 하단 리프까지의 가장자리 수이므로 이동할 때마다 깊이에 +1을 추가합니까? 그게 뭔가?

자손에 대한 알고리즘에 대해 알지 못합니다. 특정 노드가 가지고있는 노드의 수를 묻습니다.

정상 나무 btw입니다.

Answer 1

depth(tree) = 1+ max(depth(tree.left), depth(tree.right)); 

descendants(tree) = descendants(tree.left) + descendants(tree.right); 

null 포인터에 대해 0을 반환하면 재귀가 끝납니다.

Answer 2

숙제에 대한 질문입니까? 내 대답은 그것이 숙제라고 가정합니다.

트리는 재귀 적 데이터 구조이므로, 트리에서 작동하는 알고리즘은 종종 재귀 적입니다. 재귀 알고리즘에는 기본 사례와 귀납적 사례가 필요합니다. 나무의 경우 기본 노드는 리프 노드 (예 : 자식이없는 노드)를 방문 할 때 수행하는 작업입니다. 귀납적 인 경우는 내부 노드 (최소 한 명의 하위 노드가있는 노드)를 방문 할 때하는 일입니다.

• 자료의 경우 : 깊이를 계산 (또는 트리의 "높이")에 대한

  자녀가없는 노드의 깊이는 무엇입니까?

• 귀납적 인 경우 : 자녀의 모든 깊이 (다른 숫자 일 수 있음)를 감안할 때 방문중인 현재 노드의 깊이는 얼마입니까?
  • 자료의 경우 : 자손의 수를 계산하기 위해

  자녀가없는 노드가 얼마나 많은 후손이 있습니까?

• 귀납적 인 경우 : 모든 자녀의 자손 카운트를 알고 있다고 가정 할 때, 현재 방문한 노드의 자손 카운트는 얼마입니까?

질문을 명확히하는 것이 좋습니다.