JavaScript 데이터 구조와 알고리즘의 이진 트리에 대한 자세한 설명_기본 지식

이진 트리의 개념

이진 트리는 n(n>=0) 노드의 유한 집합입니다. 집합은 빈 집합(빈 이진 트리)이거나 루트 노드와 서로 분리된 두 개의 트리로 구성됩니다. 루트 노드의 왼쪽 하위 트리와 오른쪽 하위 트리로 구성됩니다.

이진 트리의 특징

각 노드에는 최대 2개의 하위 트리가 있으므로 이진 트리에는 차수가 2보다 큰 노드가 없습니다. 이진 트리의 각 노드는 객체이고 각 데이터 노드에는 부모, 왼쪽 자식, 오른쪽 자식에 대한 포인터인 세 개의 포인터가 있습니다. 각 노드는 포인터를 통해 서로 연결됩니다. 연결된 포인터 간의 관계는 부모-자식 관계입니다.

이진 트리 노드의 정의

이진 트리 노드는 다음과 같이 정의됩니다.

코드 복사 코드는 다음과 같습니다.

구조체 BinaryTreeNode
{
int m_nValue;
BinaryTreeNode* m_pLeft;
BinaryTreeNode* m_pRight;
};

이진 트리의 5가지 기본 형태

빈 이진 트리
루트 노드는 하나만 있습니다
루트 노드에는 왼쪽 하위 트리만 있습니다
루트 노드에는 올바른 하위 트리만 있습니다
루트 노드에는 왼쪽과 오른쪽 하위 트리가 모두 있습니다

3개의 노드가 있는 일반 트리에는 2개의 레이어 또는 3개의 레이어라는 두 가지 상황만 있습니다. 하지만 이진 트리는 왼쪽과 오른쪽을 구분해야 하므로 다음과 같은 5가지 형태로 진화하게 됩니다.

특수 이진 트리

비스듬한 나무

위 마지막 사진의 2, 3번째 사진처럼요.

완전 이진 트리

이진 트리에서 모든 가지 노드가 왼쪽 하위 트리와 오른쪽 하위 트리를 갖고 모든 리프가 동일한 레벨에 있는 경우 이러한 이진 트리를 완전 이진 트리라고 합니다. 아래와 같이:

완전 이진 트리

완전한 이진 트리는 마지막 레벨의 왼쪽이 가득 차고, 오른쪽이 가득 차거나 아닐 수도 있으며, 나머지 레벨이 가득 찬다는 의미입니다. 깊이가 k이고 노드 수가 2^k - 1인 이진 트리는 완전 이진 트리(완전 이진 트리)입니다. 깊이 k이고 간격이 없는 트리입니다.

완전 이진 트리의 특징은 다음과 같습니다.

리프 노드는 아래쪽 두 레벨에만 나타날 수 있습니다.

가장 낮은 잎은 왼쪽 연속 위치에 집중되어야 합니다.

두 번째 레이어에서 리프 노드가 있는 경우 오른쪽에 연속적인 위치에 있어야 합니다.

노드 차수가 1이면 노드에는 자식만 남았습니다.

동일한 노드 트리를 갖는 이진 트리, 완전 이진 트리는 가장 작은 깊이를 갖습니다.

참고: 완전 이진 트리는 완전 이진 트리여야 하지만 완전 이진 트리가 반드시 완전 이진 트리는 아닙니다.

알고리즘은 다음과 같습니다.

코드 복사 코드는 다음과 같습니다.

bool is_complete(tree *root)
{
큐
트리 *ptr
// 너비 우선 순회(레벨 순회)를 수행하고 NULL 노드를 대기열에 넣습니다.
q.push(루트)
동안 ((ptr = q.pop()) != NULL)
{ 
           q.push(ptr->왼쪽);
           q.push(ptr->right);
}  

// 방문하지 않은 노드가 있는지 확인
동안 (!q.is_empty())
{ 
ptr = q.pop()

// 방문하지 않은 NULL이 아닌 노드가 있는 경우 트리에는 구멍이 있고 불완전한 이진 트리입니다.
If (NULL != ptr)
~                false 반환;                                ~ }  

true를 반환합니다.
}

이진 트리의 속성

이진 트리의 속성 1: 이진 트리의 i 번째 수준에는 최대 2^(i-1)개의 노드(i>=1)가 있습니다.

이진 트리의 속성 2: 깊이가 k인 이진 트리에는 최대 2^k-1개의 노드가 있습니다(k>=1)

이진 트리의 순차 저장 구조

이진 트리의 순차 저장 구조는 1차원 배열을 사용하여 이진 트리의 각 노드를 저장하며, 노드의 저장 위치는 노드 간의 논리적 관계를 반영할 수 있습니다.

바이너리 연결 리스트

순차 저장의 적용성이 강하지 않기 때문에 체인 저장 구조를 고려해야 합니다. 국제 관행에 따르면 이진 트리 저장은 일반적으로 체인 저장 구조를 사용합니다.

이진 트리의 각 노드에는 최대 두 개의 하위 항목이 있으므로 데이터 필드와 두 개의 포인터 필드를 디자인하는 것이 자연스러운 아이디어입니다. 이러한 연결 목록을 이진 연결 목록이라고 합니다.

이진 트리 탐색

이진 트리 순회는 루트 노드에서 시작하여 특정 순서로 이진 트리의 모든 노드를 방문하여 각 노드가 한 번만 방문하는 것을 의미합니다.

이진 트리를 순회하는 방법에는 다음과 같은 세 가지가 있습니다.

(1) 선주문 순회(DLR)는 먼저 루트 노드를 방문한 다음 왼쪽 하위 트리를 순회하고 마지막으로 오른쪽 하위 트리를 순회합니다. 약어 루트-왼쪽-오른쪽.

(2) LDR(순차 순회)은 먼저 왼쪽 하위 트리를 순회한 다음 루트 노드를 방문하고 마지막으로 오른쪽 하위 트리를 순회합니다. 줄여서 left-root-right라고 합니다.

(3) LRD(후위 순회)는 먼저 왼쪽 하위 트리를 순회한 다음 오른쪽 하위 트리를 순회하고 마지막으로 루트 노드를 방문합니다. 왼쪽-오른쪽-루트로 축약됩니다.

선주문 순회:

이진 트리가 비어 있으면 작업이 반환되지 않습니다. 그렇지 않으면 루트 노드를 먼저 방문한 다음 왼쪽 하위 트리를 사전 순서로 순회한 다음 오른쪽 하위 트리를 사전 순서로 순회합니다.

순회 순서는 A B D H I E J C F KG

코드 복사 코드는 다음과 같습니다.

//선주문 순회
함수 preOrder(노드){
If(!노드 == null){
          putstr(node.show() " ");
          preOrder(node.left);
          preOrder(node.right);
}
}

순서대로 순회:

트리가 비어 있으면 작업이 반환되지 않으며, 그렇지 않으면 루트 노드부터 시작하여(루트 노드가 먼저 방문되지 않음) 루트 노드의 왼쪽 하위 트리를 순서대로 순회한 다음 루트 노드를 방문합니다. 마지막으로 오른쪽 하위 트리를 순서대로 탐색합니다.

순회 순서는 H D I B E J A F K C G

코드 복사 코드는 다음과 같습니다.

//재귀를 사용하여 순차 순회 구현
함수 inOrder(노드){
If(!(노드 ​​== null)){
inOrder(node.left);//왼쪽 하위 트리를 먼저 방문하세요
           putstr(node.show() " ");//루트 노드 다시 방문
inOrder(node.right);//오른쪽 하위 트리에 대한 마지막 액세스
}
}

주문 후 순회:

트리가 비어 있으면 무작동 작업이 반환되고, 그렇지 않으면 왼쪽 및 오른쪽 하위 트리를 왼쪽에서 오른쪽으로 순회하여 먼저 잎, 노드, 마지막으로 루트 노드를 방문합니다.

순회 순서는 다음과 같습니다: H I D J E B K F G C A

코드 복사 코드는 다음과 같습니다.

//사후순회
함수 postOrder(노드){
If(!node == null){
PostOrder(node.left);
         postOrder(node.right);
           putStr(node.show() " ");
}
}

이진 검색 트리 구현

이진 검색 트리(BST)는 노드로 구성되므로 다음과 같이 노드 노드 객체를 정의합니다.

코드 복사 코드는 다음과 같습니다.

함수 노드(데이터,왼쪽,오른쪽){
This.data = 데이터;
This.left = left;//왼쪽 노드 링크 저장
This.right = 맞아;
This.show = 보여주다;
}

함수 표시(){
Return this.data;//노드에 저장된 데이터 표시
}

최대값과 최소값 찾기

BST에서 최소값과 최대값을 찾는 것은 매우 간단합니다. 더 작은 값이 항상 왼쪽 하위 노드에 있기 때문입니다. BST에서 최소값을 찾으려면 마지막 노드를 찾을 때까지 왼쪽 하위 트리를 순회하면 됩니다. 🎜>

최소값 찾기

코드 복사 코드는 다음과 같습니다.

함수 getMin(){
var current = this.root;
동안(!(current.left == null)){
현재 = 현재.왼쪽;
}
현재.데이터를 반환합니다.
}

이 방법은 BST의 가장 왼쪽 노드를 탐색할 때까지 BST의 왼쪽 하위 트리를 하나씩 탐색합니다. 이는 다음과 같이 정의됩니다.

코드 복사 코드는 다음과 같습니다.

현재.왼쪽 = null;

이때 현재 노드에 저장된 값은 최소값입니다

최대값 찾기

BST에서 최대값을 찾으려면 마지막 노드를 찾을 때까지 오른쪽 하위 트리를 순회하면 되며, 이 노드에 저장된 값이 최대값이 됩니다.

코드 복사 코드는 다음과 같습니다.

함수 getMax(){

var current = this.root;
동안(!(current.right == null)){
            현재 = current.right;
}
현재.data를 반환합니다.
}