이진 트리의 용도는 무엇입니까?

이진 트리는 이진 검색 트리와 이진 힙을 구현하는 데 사용할 수 있습니다. 컴퓨터 과학에서 이진 트리는 노드당 최대 2개의 하위 트리가 있는 트리 구조입니다. 일반적으로 하위 트리를 "왼쪽 하위 트리" 및 "오른쪽 하위 트리"라고 합니다. 트리"는 다양한 용도에 따라 다음과 같이 나눌 수 있습니다. 1. 완전 이진 트리; 2. 완전 이진 트리; 3. 균형 이진 트리.

이진 트리의 역할

이진 트리는 이진 검색 트리와 이진 힙을 구현하는 데 자주 사용됩니다.

컴퓨터 과학에서 이진 트리는 노드당 최대 2개의 하위 트리가 있는 트리 구조입니다. 일반적으로 하위 트리를 "왼쪽 하위 트리" 및 "오른쪽 하위 트리"라고 합니다.

다음으로 나눌 수 있습니다.

1. 완전 이진 트리 - 이진 트리의 높이가 h이면 h번째 레이어를 제외하고 각 레이어의 노드 수(1~h-1)가 최대에 도달합니다. number , 레이어 h에는 리프 노드가 있고 리프 노드는 왼쪽에서 오른쪽으로 배열됩니다. 이는 완전한 이진 트리입니다.

2. 완전 이진 트리 - 리프 노드를 제외한 모든 노드가 왼쪽 및 오른쪽 공동 탈퇴를 갖고 리프 노드가 모두 아래쪽에 있는 이진 트리입니다.

3. 균형 이진 트리 - 균형 이진 트리는 AVL 트리라고도 합니다(AVL 알고리즘과 다름). 이진 정렬 트리이며 다음과 같은 속성을 갖습니다. 빈 트리이거나 왼쪽 및 오른쪽 하위 트리입니다. 높이 차이는 1을 초과하지 않으며 왼쪽과 오른쪽 하위 트리는 모두 균형 이진 트리입니다.

확장 정보

깊이가 h인 이진 트리에는 최대 하나의 노드(h>=1)와 적어도 h개의 노드가 있습니다. 임의의 이진 트리에 대해 리프 노드 수가 N0이고 차수가 2인 노드의 총 수가 N2이면 N0=N2+1입니다.

N개의 노드가 있는 완전한 이진 트리의 각 노드가 순차적 방식으로 저장되면 노드 간의 관계는 다음과 같습니다. I가 노드 번호이고 I>1이면 상위 노드의 번호는 I입니다. / 2. 2*IN이면 왼쪽 자식이 없습니다. 2*I+1

위 내용은 이진 트리의 용도는 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!