이진 트리의 이등변삼각형 수

이진 트리는 각 노드가 최대 2개의 하위 노드를 가질 수 있는 데이터 구조입니다. 이 아이들을 각각 왼쪽 아이들, 오른쪽 아이들이라고 부릅니다. 부모 배열 표현이 주어졌다고 가정하면 이를 사용하여 이진 트리를 만들어야 합니다. 이진 트리에는 여러 개의 이등변삼각형이 있을 수 있습니다. 우리는 이 이진 트리에서 가능한 이등변삼각형의 총 개수를 찾아야 합니다.

이 기사에서는 C++에서 이 문제를 해결하기 위한 몇 가지 기술을 살펴보겠습니다.

문제 이해하기

상위 배열을 제공합니다. 배열 인덱스가 트리 노드의 값을 형성하고 배열의 값이 해당 특정 인덱스의 상위 노드를 제공하도록 이진 트리 형식으로 표현해야 합니다.

-1은 항상 루트 상위 노드라는 점에 유의하세요. 아래에는 배열과 이진 트리 표현이 나와 있습니다.

이진 트리 -

모든 이진 트리에는 세 가지 유형의 이등변삼각형이 있을 수 있습니다. -

• 왼쪽 이등변 삼각형 − 이 삼각형에서 꼭지점은 왼쪽 부모 노드의 자식 노드이고 밑변(이등변삼각형의 양쪽)을 이루는 꼭지점은 왼쪽입니다. 자식 노드. 하위 노드는 직접적이거나 간접적일 수 있습니다. 위 트리에는 (2, 6, 3), (3, 7, 1)이라는 두 개의 이등변삼각형이 있습니다.

• 오른쪽 이등변삼각형 − 이 삼각형에서 꼭짓점은 부모의 오른쪽 자식이고, 밑면을 구성하는 꼭짓점은 꼭짓점의 오른쪽 자식입니다. 어린이는 직접적일 수도 있고 간접적일 수도 있습니다. 위의 트리에는 이등변삼각형(4, 1, 8)이 하나만 있습니다.

• Balanced Isosceles Triangle − 이 삼각형에서 밑면을 이루는 꼭짓점은 꼭짓점 노드의 왼쪽 및 오른쪽 자식 노드입니다. 위 트리에는 (1, 3, 4), (3, 2, 7), (4, 8, 9), (2, 5, 6), (1, 2, 9)와 같은 이등변삼각형 5개가 있습니다.

위의 이진 트리에는 총 8개의 이등변삼각형이 있습니다.

깊이 우선 탐색을 사용한 순회

깊이 우선 탐색(DFS)은 트리의 모든 노드를 깊이 있게 탐색하는 방법입니다. 루트 노드에서 시작하여 각 분기로 이동한 다음 역추적합니다.

• 먼저 DFS를 사용하여 이진 트리의 각 노드를 순회하고 각 노드가 서로 인접한 것으로 표시되도록 그래프로 변환합니다. 이렇게 하면 탐색이 더 쉬워집니다.

• 각 노드에 대해 하위 노드가 있는지 확인합니다. 확인한 후 sort(node[x].begin(), node[x].end()) 함수를 사용하여 정렬합니다.

• 다음으로 현재 노드가 해당 상위 노드의 왼쪽 또는 오른쪽 후속 노드인지 확인합니다. 우리는 이진 트리의 모든 노드에서 DFS 함수를 재귀적으로 사용합니다.

• 현재 노드에 두 개의 자식(직접 또는 간접)이 있는 경우 두 자식 사이의 모서리를 계산하여 이등변삼각형이 존재할 가능성을 확인합니다. 아래 코드에 제공된 graph 함수를 통해 그들 사이의 가장자리를 찾을 것입니다.

• 마지막으로 서로 다른 위치에 있는 가능한 모든 삼각형을 더하여 이등변삼각형의 총 개수를 계산합니다.

예

출력

결론

부모 배열이 주어졌을 때 이진 트리에서 정삼각형의 총 개수를 찾는 방법을 논의했습니다. 우리는 이진 트리를 탐색할 수 있는 깊이 우선 탐색을 사용하여 이를 달성할 수 있습니다.

위 내용은 이진 트리의 이등변삼각형 수의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!