기술나눔

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

이 기사는 이진 트리에 대해 더 자세히 배울 수 있도록 트리 및 이진 트리와 관련된 개념부터 시작합니다.

🌈个人主页：웨이터야
🌈C语言笔记专栏：C 언어 노트
🌈C++笔记专栏： C++ 노트
🌈初阶数据结构笔记专栏： 기본 데이터 구조 참고사항

🌈喜欢的诗句:无人扶我青云志 我自踏雪至山巅

1. 트리 개념 및 구조

트리는 다음과 같은 비선형 데이터 구조입니다.n(n>=0)제한된 노드는 계층적 관계를 갖는 집합을 형성합니다. 그러나 트리는 실제로는 가치가 거의 없지만 이진 트리는 실용적인 가치가 더 큽니다(이 집합을 트리라고 부르는 이유는 루트가 위로 향하고 잎이 있기 때문입니다). 아래를 향하고 있습니다. 나무처럼 보입니다.)

• 루트 노드라는 특수 노드가 있습니다. 루트 노드에는 선행 노드가 없습니다.
• 루트 노드를 제외한 나머지 노드는 다음과 같이 나뉜다.M(M>0)서로소 집합T1、T2、....、Tm, 각 세트는Ti(1<=i<=m) 트리와 유사한 구조를 가진 또 다른 하위 트리입니다. 각 하위 트리의 루트 노드에는 단 하나의 선행 노드가 있고 0개 이상의 후속 노드가 있을 수 있습니다.
• 트리는 재귀적으로 정의되며 동시에 주의가 필요합니다.트리 구조에서하위 트리 사이에는 교차가 있을 수 없습니다. 그렇지 않으면 트리 구조가 아닙니다.

1.1 트리 관련 개념

• 노드의 정도: 위 그림과 같이 노드에 포함된 하위 트리의 수를 노드의 차수라고 합니다. A는 6입니다.
• 리프 노드 또는 터미널 노드: 차수가 0인 노드를 리프 노드라고 합니다. 위 그림에 표시된 대로 B, C, H, I...와 같은 노드는 리프 노드입니다.
• 비단말 노드 또는 분기 노드: 차수가 0이 아닌 노드. 위 그림에 표시된 대로: D, E, F, G...와 같은 노드는 분기 노드입니다.
• 상위 노드 또는 상위 노드: 노드에 하위 노드가 포함된 경우 이 노드를 하위 노드의 상위 노드라고 합니다. 위 그림에 표시된 대로 A는 B의 상위 노드입니다.
• 하위 노드 또는 하위 노드: 노드에 포함된 하위 트리의 루트 노드를 노드의 하위 노드라고 합니다. 위 그림에 표시된 대로 B는 A의 하위 노드입니다.
• 형제 노드: 위와 같이 동일한 부모 노드를 가진 노드를 형제 노드라고 합니다. B와 C는 형제 노드입니다.
• 나무의 정도: 트리에서 가장 큰 노드의 차수는 위에 표시된 대로 트리의 차수라고 합니다. 트리의 차수는 6입니다.
• 노드 수준: 루트 정의부터 시작하여 루트는 첫 번째 수준이고 루트의 하위 노드는 두 번째 수준입니다.
• 나무의 높이 또는 깊이: 위에 표시된 대로 트리의 최대 노드 수준: 트리의 높이는 4입니다.
• 사촌 노드: 부모가 같은 레벨에 있는 노드는 위 그림과 같이 서로 사촌입니다. H와 I는 서로 형제 노드입니다.
• 노드의 조상: 위 그림과 같이 루트에서 노드까지의 분기에 있는 모든 노드: A는 모든 노드의 조상입니다.
• 자손 : 특정 노드를 루트로 하는 하위 트리의 모든 노드를 해당 노드의 자손이라고 합니다.위에 표시된 대로: 모든 노드는 A의 자손입니다.
• 숲: m(m>0)개의 분리된 나무 집합을 숲이라고 합니다.

2. 트리의 저장 표현

트리 구조는 선형 테이블보다 복잡하기 때문에 저장 방법이 더 까다롭습니다. 값 범위와 노드 간의 관계를 모두 저장해야 합니다.

이전 지식을 바탕으로 한 몇 가지 방법은 다음과 같습니다.

• 각 아이는 주소를 가지고 있으며 포인터 배열을 통해 데이터를 저장할 수 있습니다. (공간은 고정되어 있으며, 새로운 공간을 신청할 때 비용과 공간 문제가 있습니다.)
• 첫 번째 방법의 최적화를 위해 포인터 배열을 자식을 저장하는 시퀀스 테이블로 사용하여 고정된 공간 문제를 해결합니다.
• 일반적으로 사용되는 권장 솔루션: 왼쪽 아이와 오른쪽 형제 방법(큰형이 둘째 아이를 맡고, 둘째 아이가 셋째 아이를 맡으므로 부모 모두 피곤할 필요가 없습니다)

typedef int DataType;
struct Node
{
    struct Node* _firstChild1; // 第一个孩子结点
    struct Node* _pNextBrother; // 指向其下一个兄弟结点
    DataType _data; // 结点中的数据域
};
1
2
3
4
5
6
7

물론, 위의 방법에 국한되지 않고 부모 표현, 자식 표현, 자식 부모 표현, 자식 형제 표현 등도 있습니다.여기서 우리는 가장 일반적으로 사용되는 것들을 간략하게 이해하겠습니다남동생 대표

3. 이진 트리 개념

이진 트리는 유한한 노드 집합입니다. 이 집합에는 두 가지 상황이 있을 수 있습니다.

1. 빈 나무
2. 루트 노드와 왼쪽 하위 트리 및 오른쪽 하위 트리라고 하는 두 개의 이진 트리로 구성됩니다(하위 트리는 빈 트리일 수 있음).

그림에서 두 가지 결론을 도출할 수 있습니다.:

1. 이진 트리에는 차수가 2보다 큰 노드가 없습니다.

2. 이진 트리의 하위 트리는 왼쪽 하위 트리와 오른쪽 하위 트리로 나눌 수 있고 순서는 바뀔 수 없으므로 이진 트리는 순서 트리입니다.

알아채다: 모든 이진 트리의 경우 다음과 같은 상황으로 구성됩니다(빈 나무 상황은 잊기 가장 쉽다)

3.1 현실의 이진트리 (보려면 여러번 절해야함)

4. 특수 이진 트리

• 완전 이진 트리 : 이진 트리는 각 계층의 노드 수가 최대에 도달하면 완전 이진 트리입니다. 즉, 이진트리의 수준은 K이고, 총 노드 수는 2이다.^케이-1이면 완전 이진 트리입니다.
• 완전 이진 트리 : 완전 이진 트리는 매우 효율적인 데이터 구조입니다. 완전 이진 트리는 완전 이진 트리에서 파생됩니다. 높이 K와 n개 노드를 갖는 이진 트리의 경우, 각 노드가 높이 K를 갖는 전체 이진 트리에서 1부터 n까지 번호가 매겨진 노드와 일대일로 대응하는 경우에만 완전 이진 트리라고 합니다.

간략하게 요약하자면:

• 전체 이진 트리의 모든 수준이 가득 찼습니다.

• 완전한 이진 트리의 높이가 n이면 첫 번째 n-1 수준은 가득 차 있지만 마지막 수준은 가득 차지 않을 수 있습니다.하지만 왼쪽에서 오른쪽으로 연속되어야 합니다.

• 완전 이진 트리는 매우 효율적인 데이터 구조이고, 완전 이진 트리는 완전 이진 트리의 특별한 유형입니다.

• 완전 이진 트리는 완전 이진 트리의 필요충분조건입니다.

4.1 완전 이진 트리에 속하지 않는 상황

이것은 왼쪽에서 오른쪽으로 연속되지 않는 일반적인 이진 트리입니다.

5. 이진 트리의 저장 구조

이진 트리는 일반적으로 두 가지 구조로 저장될 수 있습니다. 하나는 순차 구조이고 다른 하나는 체인 구조입니다.

5.1 순차적 저장

순차 구조 저장은 배열을 사용하여 저장하는 것입니다.일반적으로 배열은 완전한 이진 트리를 나타내는 데에만 적합합니다. , 바이너리 트리가 가득 차지 않으면 공간 낭비가 발생하기 때문입니다. 실제로는 힙만 저장을 위해 배열을 사용합니다. 이진 트리의 순차 저장은 물리적으로는 배열이고 논리적으로는 이진 트리입니다. 다음 질문을 해결하려면 물리적 배열과 논리적 이진 트리의 조합을 사용하여 문제를 해결해야 합니다.

5.2 부모 노드와 자식 노드 사이의 정규 첨자 관계(중요)

• leftchild = parent * 2 + 1;

• rightchild = paretn * 2 +2;

• parent = (child - 1) / 2;(왼쪽 자식과 오른쪽 자식을 구분하지 않음)

• 세 번째 사항에 대해서는 개인적인 추론을 바탕으로leftchild아래 첨자는 다음과 같이 분할됩니다.leftchild- 1그리고1,을 위한leftchild-1~을 위한parent아래 첨자를 두 번,(child - 1) / 2운영자는leftchild그대로 꺼내세요1부분적으로 2로 나눈 정수는 0이고,leftchild -1그 일부는 다음과 같이 볼 수 있다.leftchild,그리고rightchild与leftchild相差1,왜냐하면rightchild = leftchild - 1그리고 위를 통해서leftchild - 1 ~= leftchild, 라고 추론할 수 있다.rightchild = leftchild(在进行/2运算，取整数情况下)

5.3 체인 보관

이진 트리의 연결 저장 구조는 연결 리스트를 사용하여 이진 트리를 표현하는 것을 의미합니다. 즉, 체인을 사용하여 요소의 논리적 관계를 나타냅니다. 일반적인 방법은 연결된 목록의 각 노드가 데이터 필드와 왼쪽 및 오른쪽 포인터 필드의 세 가지 필드로 구성된다는 것입니다. 왼쪽 및 오른쪽 포인터는 왼쪽 자식과 오른쪽 자식이 있는 링크 지점의 저장 주소를 제공하는 데 사용됩니다. 노드의 위치는 각각 다릅니다.체인 구조는 이진 체인과 삼중 체인으로 구분됩니다. 현재 우리 연구에서는 이진 체인을 일반적으로 사용하지만 나중에 레드-블랙 트리와 같은 고차 데이터 구조를 배울 때 삼중 체인이 사용됩니다.

typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{
        struct BinTreeNode* _pLeft; // 指向当前节点左孩子
    struct BinTreeNode* _pRight; // 指向当前节点右孩子
    BTDataType _data; // 当前节点值域
}
// 三叉链
struct BinaryTreeNode
{
    struct BinTreeNode* _pParent; // 指向当前节点的双亲
    struct BinTreeNode* _pLeft; // 指向当前节点左孩子
    struct BinTreeNode* _pRight; // 指向当前节点右孩子
    BTDataType _data; // 当前节点值域
}；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

5.4 요약

순차 구조 저장소는 배열을 통해 저장됩니다.일반적으로 배열은 완전한 이진 트리에만 적합하고, 불완전한 이진 트리는 배열 구조 저장에 적합하지 않습니다. . 하지만 실제로 배열은 힙을 사용할 때만 저장용으로 사용되며, 대부분 체인 구조를 통해 저장됩니다.

그 이유는:

1. 먼저, 이진 트리는 자신만의 특별한 논리 구조를 가지고 있다는 점을 알아야 합니다. 이는 다른 데이터 구조와 다르며 많은 공간과 논리를 소비하기 때문에 힙 데이터를 추가, 삭제, 확인 및 수정하는 데 적합합니다. 더 복잡합니다.이렇게 복잡한 구조를 이용해 데이터를 저장한다면 가치가 떨어지는 것은 아니다. , 처음부터 데이터를 저장하려면 순차 테이블을 사용하는 것이 좋습니다. 동시에 일반적으로 이진 트리의 구조는 재귀적이므로 비재귀적으로 구현하는 것이 더 까다롭습니다.
2. 일반적인 이진 트리의 저장 요소 밀도는 매우 낮을 수 있으며 연속 저장 구조는 많은 공간 낭비를 초래합니다.
3. 힙은 트리에서 노드의 위치를 ​​결정하는 "힙 속성"에 따라 정렬됩니다(아래 힙 소개에서 설명).

---

이상이 이 글의 내용입니다. 읽어주신 모든 분들께 감사드립니다. 다음은 기본 데이터 구조에 대한 Dian Xiaoer의 노트입니다. 기본 데이터 구조를 학습하는 데 도움이 되기를 바랍니다.