이진 트리의 연결 저장 구조는 무엇입니까?

이진 트리의 연결 저장 구조는 연결 리스트를 사용하여 이진 트리를 표현하는 것을 의미합니다. 즉, 연결 리스트를 사용하여 요소 간의 논리적 관계를 나타냅니다. 이진 트리의 연결 저장 구조는 일반적으로 이진 연결 목록과 삼중 연결 목록의 두 가지 저장 형식을 갖습니다.

이 튜토리얼의 운영 환경: Windows 7 시스템, c99 버전, Dell G3 컴퓨터.

이진 트리의 연결 저장 구조는 연결 리스트를 사용하여 이진 트리를 나타냅니다. 즉, 연결 리스트를 사용하여 요소 간의 논리적 관계를 나타냅니다. 일반적으로 두 가지 저장 형식이 있습니다.

• 연결된 목록의 각 노드는 세 개의 필드로 구성됩니다. 데이터 필드 외에도 노드의 왼쪽 자식과 오른쪽 자식을 제공하는 데 사용되는 두 개의 포인터 필드가 있습니다. 해당 위치의 저장 주소입니다.

• 연결된 목록의 각 노드는 데이터 필드 외에도 노드의 왼쪽 자식, 오른쪽 자식 및 부모 노드의 저장 주소를 제공하는 데 사용되는 3개의 포인터 필드로 구성됩니다.

이진 트리의 연쇄 저장 구조(C 언어로 자세히 설명)

그림 1 일반 이진 트리의 개략도

그림 1과 같이 일반 이진 트리입니다. 연결되어 있는 경우 저장하려면 트리의 루트 노드에서 시작하여 각 노드와 왼쪽 및 오른쪽 자식을 연결 목록에 저장하기만 하면 됩니다. 따라서 그림 1에 해당하는 체인 저장 구조는 그림 2와 같습니다.

그림 2 이진 트리의 체인 저장 구조의 도식 다이어그램

그림 2에서 볼 수 있듯이 이진 트리의 체인 저장을 사용할 때 노드 구조는 세 부분으로 구성됩니다(그림 3 참조).

• 포인터 왼쪽 하위 노드(Lchild) ;

• 노드에 저장된 데이터(data);

• 오른쪽 하위 노드(Rchild)에 대한 포인터;

그림 3 바이너리 트리 노드 구조

노드 구조를 나타내는 C 언어 코드는

typedef struct BiTNode{
    TElemType data;//数据域
    struct BiTNode *lchild,*rchild;//左右孩子指针
    struct BiTNode *parent;
}BiTNode,*BiTree;

그림 2의 체인 저장 구조에 해당하는 C 언어 코드는

#include <stdio.h>
#include <stdlib.h>
#define TElemType int
typedef struct BiTNode{
    TElemType data;//数据域
    struct BiTNode *lchild,*rchild;//左右孩子指针
}BiTNode,*BiTree;
void CreateBiTree(BiTree *T){
    *T=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->data=1;
    (*T)->lchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->lchild->data=2;
    (*T)->rchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->rchild->data=3;
    (*T)->rchild->lchild=NULL;
    (*T)->rchild->rchild=NULL;
    (*T)->lchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->lchild->lchild->data=4;
    (*T)->lchild->rchild=NULL;
    (*T)->lchild->lchild->lchild=NULL;
    (*T)->lchild->lchild->rchild=NULL;
}
int main() {
    BiTree Tree;
    CreateBiTree(&Tree);
    printf("%d",Tree->lchild->lchild->data);
    return 0;
}

프로그램 출력 결과:

4

실제로는 이진 트리 체인 그림 2에 표시된 것보다 더 많은 저장 구조가 있습니다. 예를 들어, 일부 실제 시나리오에서는 "노드의 부모 노드 찾기" 작업이 수행될 수 있습니다. 이 경우 그림과 같이 각 노드의 부모 노드를 가리키도록 노드 구조에 포인터 필드를 추가할 수 있습니다. 그림 4. :

그림 4 사용자 정의 이진 트리의 연결된 저장 구조

이러한 연결 목록 구조를 일반적으로 삼항 연결 목록이라고 합니다.

그림 4에 표시된 세 갈래 연결 목록을 사용하면 각 노드의 상위 노드를 쉽게 찾을 수 있습니다. 따라서 실제 문제를 해결할 때 적절한 연결 목록 구조를 사용하여 이진 트리를 저장하면 절반의 노력으로 두 배의 결과를 얻을 수 있습니다.

관련 추천: "C 언어 비디오 튜토리얼"

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