트 리 구조 (데이터 구조)
트 리 구 조 는 선형 구조 와 구별 되 는 또 다른 빅 데이터 구조 로
와 를 가진다.나 무 는 n (n > = 0) 개의 결점 으로 구 성 된 유한 집합 이다.n = 0 의 나 무 를 빈 나무 라 고 합 니 다.n! =0 시, 나무의 결점 도 는 다음 과 같은 조건 을 만족 시 켜 야 합 니 다.
: 우 리 는 한 결점 이 가 진 자녀 수 를 이 결점 의 도 라 고 부 르 고 나무 중의 모든 결점 도의 최대 치 를 나무의 도 라 고 부른다. : 0 이 라 고 불 리 는 결점 은 단말기 결점 이나 잎 결점 이다. : 0 이 라 고 부 르 지 않 는 결점 은 비 단말기 결점 이나 지점 이다. : 나무 에 두 개의 결점 을 연결 하 는 선분 을 나뭇가지 라 고 한다. : 나무 에서 결점 Ki 부터 나 뭇 가 지 를 따라 위 에서 아래로 결점 kj 에 도달 할 수 있다 면 ki 에서 kj 까지 경로 가 존재 한다 고 합 니 다. 경로 의 길 이 는 지나 간 나뭇가지 수 와 같 습 니 다. : 뿌리 부터 정의 합 니 다. 뿌리 노드 는 1 층 이 고 뿌리의 자녀 노드 는 2 층 을 구성 합 니 다. 이런 식 으로 유추 합 니 다. 만약 에 특정한 노드 kj 가 i 층 에 있 으 면 자녀 는 i + 1 층 에 있 습 니 다. : 나무의 결점 의 최대 층 차 는 나무의 깊이 나 높이 라 고 한다. : 만약 에 나무 에 임의의 결점 이 있 는 나무 가 모두 왼쪽 에서 오른쪽으로 순서 가 있 는 것 으로 보고 임의로 교환 할 수 없 으 면 이 나 무 를 질서 있 는 나무 라 고 부 르 고 그렇지 않 으 면 무질서 한 나무 라 고 부른다. : m (m > = 0) 개의 서로 교차 하지 않 는 나무 로 구 성 된 집합 을 숲 이 라 고 한다. 숲 과 나무의 개념 은 매우 비슷 하 다. 한 나무 에 점 이 있 는 나무 로 구 성 된 몇 개 는 하나의 숲 이 고 숲 속 의 모든 나무 에 하나의 공 통 된 뿌리 를 더 하면 숲 은 하나의 나무 가 된다.6.3 나무의 저장 구조
자주 사용 하 는 나무의 저장 구 조 는 세 가지 가 있 는데 그것 이 바로 부모 표현법, 아이 표현법, 아이 형제 표현법 이다.
6.3.1 양친 표현법
나무 에 서 는 뿌리 노드 에 부모 가 없 는 것 을 제외 하고 모든 노드 의 부모 가 유일 하 게 확정 되 어 있 습 니 다. 따라서 나무 에 저 장 된 노드 는 두 가지 정 보 를 포함해 야 합 니 다. 노드 의 값 data 와 노드 간 의 상호 관 계 를 나타 내 는 속성 - 이 노드 의 부모 parent.
트 리 의 모든 노드 를 1 차원 배열 에 저장 할 수 있 습 니 다.
#define MAXSIZE 100
typedef char datatype;
typedef struct node
{
datatype data;
int parent;
}node;
typedef struct tree
{
node treelist[MAXSIZE];
int length ,root;
}tree;
6.3.2 아이 표현 법
아이 표현법 으로 한 그루 의 나 무 를 표시 할 때, 나무의 각 결점 은 자신의 값 을 저장 하 는 것 외 에 도 모든 자녀의 위 치 를 지적 해 야 한다. 각 결점 은 보통 두 개의 영역 을 포함한다. 하 나 는 원소 의 값 영역 data 이 고, 다른 하 나 는 지침 그룹 이다. 배열 의 모든 요 소 는 이 결점 자녀 를 가리 키 는 지침 이다. 하나의 m 도의 수 는 지침 그룹의 크기 가 m 이다.。
아이 표현법 은 또 세 가지 로 나 뉜 다.
#define m 3
typedef char datatype;
typedef struct node{
datatype data;
struct node *child[m];
}node ,*tree;
tree root;
2. 배열 방식 의 아이 표현 법
편리 함 을 찾기 위해 서 트 리 의 모든 노드 를 1 차원 배열 에 저장 할 수 있 습 니 다.
#define m 3
#define MAXSIZE 20 /* */
typedef char datatype;
typedef struct node{
datatype data;
int child[m];
}treenode;
treenode tree[MAXSIZE]; /* */
int root; /* */
int length; /* */
3. 링크 방식 의 아이 표현 법
모든 노드 의 자녀 를 배열 하여 하나의 단일 체인 표를 형성 하면 n 개의 노드 는 n 개의 단일 체인 표를 형성 하고 n 개의 단일 체인 표 의 머리 지침 은 하나의 선형 표를 구성 하여 찾기 편 의 를 위해 배열 방식 으로 저장 할 수 있다.
#define MAXSIZE 50
typedef char datatype;
typedef struct cnode{
/* */
int child;
struct chnode *next;
}chnode,*chpoint;
typedef struct{
/* ， */
datatype data;
chpoint firstchild;
}node;
typedef struct {
/* */
node treelist [MAXSIZE];
int length ,root;
}tree;
6.3.3 아이 형제 표현법
즉, 트 리 의 모든 노드 를 저장 할 때 이 노드 값 영역 을 포함 하 는 것 외 에 도 두 개의 포인터 필드 firstchild 와 rightsibling 을 설정 하여 각각 이 노드 의 첫 번 째 키 여자 와 오른쪽 형 제 를 가리 키 는 이 진 링크 방식 으로 저장 하기 때문에 이 방법 은 이 진 트 리 표현 법 이 라 고도 부른다.
6.4 나무의 옮 겨 다 니 기
트 리 의 옮 겨 다 니 는 것 은 특정한 순서에 따라 트 리 의 모든 노드 를 방문 하고 모든 노드 는 한 번 만 방문 하 는 것 입 니 다.
나무의 옮 겨 다 니 는 것 은 항상 세 가지 로 나 뉜 다.
1. 나무의 앞 순 서 를 옮 겨 다 닌 다.
void preorder(tree p)
{
int i;
if(p!=NULL)
{
printf("%c",p->data);
for(i=0;i<m;i++)
preorder(p->child[i]);
}
}
2. 나무의 뒷 순 서 를 옮 겨 다 닌 다.
void postorder(tree p)
{
int i;
if(p!=NULL)
{
for(i=0;i<m;i++) /* */
postorder(p->child[i]);
printf("%c",p->data); /* */
}
}
3. 나무의 앞 순 서 를 옮 겨 다 니 며 3 도 트 리 를 만 듭 니 다.
루트 주소 되 돌리 기
tree createtree()
{
int i;
char ch;
tree t;
if((ch=getchar())=='#')
t=NULL;
else
{
t=(tree)malloc(sizeof(node));
t->data=ch;
for(i=0;i<m;++i)
t->child[i]=createtree();
}
return t;
}
4. 나무의 층 차 를 옮 겨 다 닌 다.
대열 (선진 선 출) 사상: 먼저 1 층 결점 을 방문 하고 자녀 가 있 으 면 자녀 를 대열 에 넣 고, 2 층 결점 을 방문 할 때 갓 가입 한 결점 을 대열 에 낸다. 그리고 2 층 결점 의 자녀 를 대열 에 묶는다... 상기 과정 을 반복 한다. (대열 의 모든 요 소 는 줄 을 서서 방문 을 기다 리 는 결점 이다)
사상: 나무의 층 차 를 옮 겨 다 니 는 과정 에서 특정한 층 의 모든 노드 의 자녀 노드 에 대해 다음 층 의 모든 노드 를 구성 합 니 다. 그 다음 에 방문 해 야 할 것 은 바로 그들 입 니 다. 나무의 층 차 를 옮 겨 다 니 는 과정 에서 먼저 뿌리 노드 를 방문 하기 때문에 초기 대기 열 에는 뿌리 노드 만 포함 되 어 있 습 니 다. 대기 열 이 비어 있 지 않 으 면 노드 가 방문 되 지 않 았 다 는 것 을 의미 합 니 다.
void levelorder(tree t)
{
tree queue[100]; /* */
int f,r,i; /*f ，r 、 */
tree p;
f=0;r=1;queue[0]=t;
while(f<t) /* */
{
p=queue[f];
f++;
printf("%c",p->data);
for(i=0;i<m;++i)
if(p->child[i])
{
queue[r]=p->child[i];
++r;
}
}
}
6.5 나무의 선형 표시
6.5.1 나무의 괄호 표시
j 를 트 리 의 결점 으로 설정 합 니 다. j 가 부여 한 정수 lev (j) 가 다음 과 같은 두 가지 조건 을 만족 시 키 면:
밤 한 개:
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
