본문으로 건너뛰기
黯羽轻扬매일 조금씩

이진 트리 (Binary Tree) 관련 알고리즘 구현

무료2015-03-17#Math#二叉树

본고는 주로 이진 트리 관련 알고리즘의 C 언어 구현에 대해 논의하며, 트리 생성, 3 가지 방식 순회 (재귀 및 비재귀), 잎 노드 출력, 트리 깊이 계산, 트리 형태 출력, 계층별 들여쓰기 출력, 계층순 출력, 루트에서 지정 노드까지의 경로 계산을 포함한다

no_mkd

시작하며:

이진 트리는 비교적 간단한 데이터 구조이며, 그 관련 알고리즘을 이해하고 숙련되게 습득하는 것은 복잡한 데이터 구조의 학습에 크게 유익합니다

일. 이진 트리의 생성

[이론이 싫은 분은 여기를 클릭하여 스킵>>]

소위 이진 트리 생성이란, 실제로는 컴퓨터에 이 특수한 데이터 구조를 저장하게 하는 것입니다 (어디가 특수한가? 우리가 사용자 정의했다는 점입니다)

먼저, 컴퓨터 내부 저장은 선형적이지만, 우리의 트리 구조는 계층적이며, 컴퓨터는 분명히 이해할 수 없습니다. 컴퓨터가 받아들일 수 있는 원시 데이터 타입은 우리의 요구를 충족시킬 수 없습니다

따라서 계층 관계를 나타내기 위해 데이터 구조를 사용자 정의할 수밖에 없습니다

실제로는 구조 + 연산을 정의해야 합니다. 구조는 연산을 위해 봉사하는 것입니다. 예를 들어, 표 구매 과정을 시뮬레이션할 때 기존 데이터 구조는 우리의 요구를 충족시킬 수 없습니다 (배열에 대해 말하지 마십시오...). 필요한 연산은 다음과 같을 수 있습니다:

1. 표 구매 줄의 가장 앞에 서 있는 사람 획득; 2. 표를 구매한 사람을 줄에서 제거; 3. 첫 번째 사람이 표를 구매한 후, 그 뒤의 모든 사람들이 "자발적"으로 앞으로 이동

이 세 가지 연산을 명확히 하고, 연산에 따라 구조를 정의한 후, 마지막으로 큐 (배열/연결 리스트 + 해당 함수) 를 얻었습니다

이진 트리도 이와 같으며, 컴퓨터가 보는 것은 구조 + 연산입니다. 구조는 Node 집합 (이진 연결 리스트) 이고, 연산은 생성, 순회, 검색 등의 함수입니다

노드:

struct bt
{
	char data;
	struct bt *left;
	struct bt *right;
};

노드는 양동과 같으며, 두 손이 있습니다 (양동에는 데이터가 담겨 있고, 두 손을 뻗어 좌우 두 자식을 잡습니다)

연산:

//createBT();
//printBT();
//deleteNode(Node node);
//...

-위 내용은 이진 트리에 대한 이해이며, 아래는 이진 트리 생성의 구체적인 구현입니다-

이진 트리 생성 과정은 실제로 순회 과정입니다 (여기서는 재귀 방식을 지칭합니다). 이진 트리의 어떤 순회 방식도 트리 구조를 선형화할 수 있음을 압니다 (간단히 말하면 한 세트의 순회 결과가 하나의 이진 트리를 유일하게 나타낼 수 있습니다). 따라서 순회 결과에 따라 이진 트리를 복원할 수 있습니다

선위 순회로 재귀적으로 트리를 구축하는 구체적인 사고:

1. 현재 루트 노드의 데이터 읽기; 2. 공백이면 현재 루트를 공백으로 설정, 아니면 새 노드를 신청하여 데이터 저장; 3. 현재 루트 노드의 왼쪽 포인터와 오른쪽 포인터로 재귀 호출하여 좌우 서브트리 생성

언어로 설명하면 이해하기 어려울 수 있으므로, 코드를 아래에示합니다:

struct bt
{
	char data;
	struct bt *left;
	struct bt *right;
};

void createBT(struct bt ** root)
{
char c;
c=getchar();
if(c == ' ')*root=NULL;//공백이면 공백으로 설정
else
{
*root=(struct bt *)malloc(sizeof(struct bt));//새 노드 신청
(*root)->data=c;//데이터 저장
createBT(&((*root)->left));//현재 노드의 왼쪽 서브트리 구축
createBT(&((*root)->right));//현재 노드의 오른쪽 서브트리 구축
}
}

예를 들어, 이진 트리 a(b, c) 를 구축하려면, 그 선위 순회 결과 ab××c××를 입력하면 됩니다 (×는 공백을 나타냄). 나머지 두 가지 트리 구축 방식도 이와 유사하며, 자세히 설명하지 않습니다. 비재귀적인 트리 구축 방법은 아래의 비재귀 순회를 참조하십시오. 매우 유사합니다

이. 순회

순회는 구현 방식에서 재귀와 비재귀 두 가지 방식이 있습니다. 소위 비재귀는 실제로 재귀에서 변환된 것입니다 (수동으로 스택 유지). 오버헤드 (메모리/시간) 면에서는 비재귀가 더 나을 수 있습니다. 결국 운영체제의 스택에서 유지되는 정보가 더 많고, 현장의 저장과 복원 오버헤드가 더 크기 때문입니다

순회 순서에는 3 가지 방식이 있습니다: 1. 선위 순회 (루트 - 좌 - 우); 2. 중위 순회 (좌 - 루트 - 우); 3. 후위 순회 (좌 - 우 - 루트)

예를 들어, 이진 트리 a(b, c(d, e)) 의 3 가지 순회 결과는 각각: 1.abcde; 2.badce; 3.bdeca 입니다

-아래에 후위 순회의 재귀와 비재귀 구현을 보겠습니다. 나머지는 이와 유사합니다-

후위 순회 재귀:

void postOrder(struct bt * root)
{
	if(root == NULL)return;
	else
	{
		postOrder(root->left);
		postOrder(root->right);
		putchar(root->data);
	}
}

후위 순회 비재귀:

void postOrder(struct st* root)
{
	struct st* stack[100];//노드 스택 선언
	int top=-1;//스택_top 인덱스
	struct bt* p=root;//현재 노드 (present)
	struct bt* q=NULL;//이전에 처리한 노드
	while(p!=NULL||top!=-1)
	{
		for(;p!=NULL;p=p->left)stack[++top]=p;//왼쪽 서브트리 순회
		if(top!=-1)
		{
			p=stack[top];
			if(p->right==NULL||p->right==q)//오른쪽 자식이 없거나, 오른쪽 자식이 이미 순회됨
			{
				putchar(p->data);//루트 노드 출력
				q=p;
				p=stack[top];
				top--;
				p=NULL;
			}
			else p=p->right;//오른쪽 서브트리 순회
		}
	}
}

더 명확하게 설명하기 위해, 위에서는 직접 스택 연산을 구현했습니다. 물론, 더 규범적인做法는 스택을 독립적인 데이터 구조로 캡슐화하고, 우리의 함수에서 스택이 제공하는 연산 함수를 호출하여 관련 연산을 수행하는 것입니다

삼. 잎 노드 출력

특정 노드를 검색하는 일련의 연산은 모두 순회를 기반으로 하며, 잎 노드 출력도 하나의 예입니다. 잎 노드가 만족하는 조건은 좌우 자식이 모두 공백인 것입니다. 순회에 이러한 판단 조건을 추가하기만 하면 됩니다

//여기서는 선위 순회 채택
void printLeaves(struct bt* root)
{
	if(root == NULL)return;
	else
	{
		if(root->left == NULL&&root->right == NULL)putchar(root->data);
		else
		{
			printLeaves(root->left);
			printLeaves(root->right);
		}
	}
}

이와 유사한 연산으로는, 이진 트리에서 일정 조건을 만족하는 노드 출력, 지정 노드 삭제, 지정 위치에 노드 (서브트리) 추가... 등이 있습니다. 모두 순회를 기반으로 몇 가지 추가 연산을 수행하는 것입니다

사. 트리 깊이 계산

트리 깊이를 계산하는 데는 여러 가지 방식이 있습니다. 예를 들어: 1. 각각 루트 아래 좌우 서브트리의 높이를 계산하여, 그 중 큰 것을 트리 깊이로 함; 2. 최대 재귀 깊이를 트리 깊이로 함...

우리는 첫 번째 방식을 채택합니다. 더 명확합니다

int btDepth(struct bt* root)
{
	int rd,ld;
	if(root==NULL)return 0;//공백 트리 깊이는 0
	else
	{
		ld=1+btDepth(root->left);//재귀적으로 층 진행, 깊이 1 추가
		rd=1+btDepth(root->right);//재귀적으로 층 진행, 깊이 1 추가
		return ld > rd ? ld : rd;//최대값 반환
	}
}

오. 트리 형태 출력

소위 트리 형태 출력이란, 자연 표현의 이진 트리를 반시계 방향으로 90 도 회전시키는 것입니다. 실제로는 여전히 순회 과정에서 재귀 층수를 기록하여, 이에 따라 출력 결과를 확정합니다

//depth 는 재귀 깊이를 나타내며, 초기값은 0
void btOutput(struct bt* root,int depth)
{
	int k;
	if(root==NULL)return;
	else
	{
		btOutput(root->right,depth+1);//오른쪽 서브트리 순회
		for(k=0;k<depth;k++)
			printf(" ");//재귀 층수가 몇인지에 따라, 몇 개의 공백 출력 (몇 칸 들여쓰기)
		putchar(root->data);printf("\n");
		btOutput(root->left,depth+1);//왼쪽 서브트리 순회
	}
}
//"우 - 중 - 좌" 순회 순서는 "역중위" 순회라고 불리며, 이 순서를 채택하는 것은 출력 규칙 (반시계 방향 90 도) 에 부합시키기 위함입니다

육. 계층별 들여쓰기 출력

계층별 들여쓰기 출력은 코드 에디터의 자동 들여쓰기와 같습니다. 루트 노드에서 시작하여 층별로 들여쓰기하며, 위의 코드를 약간 수정하면 구현할 수 있습니다

//k 는 여전히 재귀 깊이를 나타내며, 초기값은 0
void indOutput(struct bt* root,int k)
{
	int i;
	if(root!=NULL)
	{
		for(i=1;i<=k;i++)
			putchar(' ');
		putchar(root->data);putchar('\n');
		indOutput(root->left,k+1);
		indOutput(root->right,k+1);
	}
	else return;
}
//계층별 들여쓰기 출력과 트리 형태 출력의 유일한 차이점은 순회 방식이 다르다는 것으로, 전자는 선위 순회, 후자는 역중위 순회입니다

칠. 계층순 출력

계층순 출력은 앞에서 언급한 두 가지 출력 방식과 비슷해 보이지만, 실제로는 큰 차이가 있습니다. 적어도, 우리는 어떤 순회 과정도 이 목표를 달성하기 위해 단순히 적용할 수 없습니다. 따라서, 큐를 유지하여 순회 순서를 제어할 수밖에 없습니다

void layerPrint(struct bt* root)
{
	struct bt* queue[100];//노드 큐 선언
	struct bt* p;//현재 노드
	int amount=0,head,tail,j,k;//큐 관련 속성 (요소 총수, 큐 헤드, 큐 테일 인덱스)
	queue[0]=root;
	head=0;
	tail=1;
	amount++;
	while(1)
	{
		j=0;
		for(k=0;k<amount;k++)
		{
			p=queue[head++];//큐 헤드 요소 가져오기
			if(p->left!=NULL)
			{
				queue[tail++]=p->left;//있으면 왼쪽 자식 기록
				j++;
			}
			if(p->right!=NULL)
			{
				queue[tail++]=p->right;//있으면 오른쪽 자식 기록
				j++;
			}
			putchar(p->data);//현재 노드 값 출력
		}
		amount=j;//카운터 업데이트
		if(amount==0)break;
	}
}

팔. 루트에서 지정 노드까지의 경로 계산

경로를 기록하려면, 물론 재귀 방식은 적합하지 않습니다. 여기서는 후위 순회의 비재귀 구현을 채택합니다. 왜 후위 순회를 선택할까요?

이 순회 방식에서, 어떤 순간의 스택 내 기존 노드가 바로 루트 노드에서 현재 노드까지의 경로이기 때문입니다 (스택 바닥에서 스택_top 까지). 엄밀히 말하면, 이때 큐를 사용하여 경로를 저장해야 합니다. 스택은 스택 바닥에서 스택_top 까지의 출栈 연산을 지원하지 않기 때문입니다 (이러한 작은 세부 사항은 생략하겠습니다...)

//파라미터 c 는 지정 노드 값
void printPath(struct bt* root,char c)
{
	struct st* stack[100];//노드 스택 선언
	int top=-1;//스택_top 인덱스
	int i;
	struct bt* p=root;//현재 노드
	struct bt* q=NULL;//이전에 처리한 노드
	while(p!=NULL||top!=-1)
	{
		for(;p!=NULL;p=p->left)stack[++top]=p;//왼쪽 서브트리 순회
		if(top!=-1)
		{
			p=stack[top];//스택_top 요소 가져오기
			if(p->right==NULL||p->right==q)//현재 노드에 오른쪽 자식이 없거나 오른쪽 자식이 방금 액세스됨
			{
				if(p->data==c)//찾으면 경로 출력
				{
					for(i=0;i<=top;i++)
					{
						p=stack[i];
						putchar(p->data);
					}
					printf("\n");
					//여기서는 루프를 벗어나지 않음. 유일하지 않은 노드 값이 존재할 수 있으므로, 트리 전체를 순회하여 모든 경로 찾기
				}
				q=p;
				p=stack[top];
				top--;
				p=NULL;
			}
			else p=p->right;//오른쪽 서브트리 순회
		}
	}
}

구. 전체 소스 코드 및 스크린샷 예시

소스 코드:

#include<stdio.h>

struct bt
{
char data;
struct bt *left;
struct bt *right;
};


void createBT(struct bt ** root)
{
char c;
c=getchar();
if(c == ' ')*root=NULL;
else
{
*root=(struct bt *)malloc(sizeof(struct bt));
(*root)->data=c;
createBT(&((*root)->left));
createBT(&((*root)->right));
}
}


void preOrder(struct bt * root)
{
if(root == NULL)return;
else
{
putchar(root->data);
preOrder(root->left);
preOrder(root->right);
}
}


void inOrder(struct bt * root)
{
if(root == NULL)return;
else
{
inOrder(root->left);
putchar(root->data);
inOrder(root->right);
}
}


void printLeaves(struct bt* root)
{
if(root == NULL)return;
else
{
if(root->left == NULL&&root->right == NULL)putchar(root->data);
else
{
printLeaves(root->left);
printLeaves(root->right);
}
}
}


int btDepth(struct bt* root)
{
int rd,ld;
if(root==NULL)return 0;
else
{
ld=1+btDepth(root->left);
rd=1+btDepth(root->right);
return ld > rd ? ld : rd;
}
}


void btOutput(struct bt* root,int depth)
{
int k;
if(root==NULL)return;
else
{
btOutput(root->right,depth+1);
for(k=0;k<depth;k++)
printf(" ");
putchar(root->data);printf("\n");
btOutput(root->left,depth+1);
}
}


void postOrder(struct st* root)
{
struct st* stack[100];
int top=-1;
struct bt* p=root;
struct bt* q=NULL;
while(p!=NULL||top!=-1)
{
for(;p!=NULL;p=p->left)stack[++top]=p;
if(top!=-1)
{
p=stack[top];
if(p->right==NULL||p->right==q)
{
putchar(p->data);
q=p;
p=stack[top];
top--;
p=NULL;
}
else p=p->right;
}
}
}


void printPath(struct bt* root,char c)
{
struct st* stack[100];
int top=-1;
int i;
struct bt* p=root;
struct bt* q=NULL;
while(p!=NULL||top!=-1)
{
for(;p!=NULL;p=p->left)stack[++top]=p;
if(top!=-1)
{
p=stack[top];
if(p->right==NULL||p->right==q)
{
if(p->data==c)
{
for(i=0;i<=top;i++)
{
p=stack[i];
putchar(p->data);
}
printf("\n");
}
q=p;
p=stack[top];
top--;
p=NULL;
}
else p=p->right;
}
}
}


void layerPrint(struct bt* root)
{
struct bt* queue[100];
struct bt* p;
int amount=0,head,tail,j,k;
queue[0]=root;
head=0;
tail=1;
amount++;
while(1)
{
j=0;
for(k=0;k<amount;k++)
{
p=queue[head++];
if(p->left!=NULL)
{
queue[tail++]=p->left;
j++;
}
if(p->right!=NULL)
{
queue[tail++]=p->right;
j++;
}
putchar(p->data);
}
amount=j;
if(amount==0)break;
}
}


void indOutput(struct bt* root,int k)
{
int i;
if(root!=NULL)
{
for(i=1;i<=k;i++)
putchar(' ');
putchar(root->data);putchar('\n');
indOutput(root->left,k+1);
indOutput(root->right,k+1);
}
else return;
}


void main()
{
char c;
struct bt * root;
printf("선위 순회 결과를 입력하세요: ");
createBT(&root);
printf("선위 순회 (preOrder)[재귀]: \n");
preOrder(root);
printf("\n중위 순회 (inOrder)[재귀]: \n");
inOrder(root);
printf("\n후위 순회 (postOrder)[비재귀]: \n");
postOrder(root);
printf("\n잎 노드 (leaves): \n");
printLeaves(root);
printf("\n깊이 (depth): \n");
printf("%d\n",btDepth(root));
printf("트리 형태 출력 (tree output): \n");
btOutput(root,0);
printf("들여쓰기 출력 (indentation output): \n");
indOutput(root,0);
printf("목표 노드를 입력하세요 (target node): ");
getchar();
c=getchar();
printf("경로 (path): \n");
printPath(root,c);
printf("계층 출력 (layerPrint): \n");
layerPrint(root);
printf("\n");
}

스크린샷 예시:

비교적 복잡한 이진 트리:

그 선위 순회 결과는: ABD××EG×××C×FH××I×× (×는 공백을 나타내며, 입력할 때 ×를 공백으로 바꿔야 합니다)

D 를 H 로 바꿔서 다시 시도 (중복 요소가 존재하므로, H 로 가는 두 개의 경로가 있어야 합니다)

댓글

아직 댓글이 없습니다

댓글 작성