[자료구조] 연결 이진트리 구현

 

 

연결 이진트리 구현

• TreeNodemake (id, s, TreeNode* tree): 이 함수는 새로운 노드를 동적 할당하고, 트리의 왼쪽 또는 오른쪽 자식 노드로 추가합니다. s 값에 따라 'L'이면 왼쪽 자식, 'R'이면 오른쪽 자식에 추가됩니다.
• leftChild (TreeNode* v)와 rightChild (TreeNode* v): 각각 트리에서 특정 노드의 왼쪽 자식과 오른쪽 자식을 반환하는 함수입니다.
• TreeBuild (TreeNode* root, int n): 이 함수는 트리의 루트를 기준으로 나머지 노드들을 입력받아 트리를 완성합니다. 입력받은 각 노드에 대해 왼쪽 자식과 오른쪽 자식 노드를 추가해줍니다.
• findID (TreeNode* v, int id): 이 함수는 재귀적으로 트리의 노드를 탐색하여, 주어진 id와 일치하는 노드를 반환합니다. 트리의 왼쪽부터 순차적으로 탐색하며, 찾으면 해당 노드를 반환하고, 없으면 NULL을 반환합니다.
• print (TreeNode* v, char* s): 이 함수는 주어진 경로 문자열을 따라 트리에서 이동하면서 각 노드를 출력하는 함수입니다. 문자열이 'L'이면 왼쪽으로, 'R'이면 오른쪽으로 이동하며, 이동 경로에 있는 모든 노드의 id를 출력합니다.node, list 만들기

트리 구조체

#define _CRT_SECURE_NO_WARNINGS

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

typedef struct node { // 노드
	struct node* left;
	struct node* right;
	int id;
}TreeNode;

함수 구현

TreeNode* TreeNodemake(int id, char s, TreeNode* TreeNode); //TreeNode를 만드는 함수
TreeNode* leftChild(TreeNode* v); //왼쪽 자식 반환
TreeNode* rightChild(TreeNode* v); // 오른쪽 자식 반환
TreeNode* TreeBuild(TreeNode* v, int n); // 트리를 만드는 함수
TreeNode* findID(TreeNode* v, int id); // 찾고자하는 id의 TreeNode 반환
void print(TreeNode* v, char *s); // 출력 함수​

main 함수 

int main()
{
	int n;
	int root_id, root_left, root_right;

	scanf("%d", &n); // 노드의 개수 n
	TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
		
	scanf("%d %d %d", &root_id, &root_left, &root_right); // 처음 root 의 값들을 받음

	root->id = root_id; // root의 id 입력
	TreeNodemake(root_left, 'L', root); // root의 왼쪽 
	TreeNodemake(root_right, 'R', root); // root의 오른쪽

	TreeBuild(root, n); // root를 기반으로 트리를 만듬

	int s; // 탐색 횟수 s
	char str[100]; //최대 100자의 문자열
	scanf("%d", &s);
	getchar();
	for (int i = 0; i < s; i++)
	{
		scanf("%s", str);
		getchar();
		print(root,str);
	}

}​

Node 만들기

TreeNode* TreeNodemake(int id, char s, TreeNode* tree)
{
	TreeNode* v = (TreeNode*)malloc(sizeof(TreeNode)); //새로운 트리 생성하고 동적할당
	v->left = NULL; 
	v->right = NULL;
	v->id = id;

	if (s == 'R') // 만약 s가 R이면
	{
		tree->right = v; // tree의 오른쪽 줄기 v
	}
	else if (s == 'L') // 만약 s가 L 이면
	{
		tree->left = v; // tree의 왼쪽 줄기 v
	}
	return tree; //tree 반환함
}

 

왼쪽 자식, 오른쪽 자식 반환 함수

TreeNode* leftChild(TreeNode* v)
{
		return v->left;
}
TreeNode* rightChild(TreeNode* v)
{
		return v->right;
}​

 

Tree 빌드

TreeNode* TreeBuild(TreeNode* root, int n)
{
	int id, left_id, right_id;
	for (int i = 0; i < n-1; i++) // n-1번 반복 (위에서 루트 한번 만들었으니)
	{
		scanf("%d %d %d",&id, &left_id, &right_id); // id와 왼쪽, 오른쪽 입력 받음
		TreeNode* v = findID(root, id); //id의 위치를 찾아서 v에 대입
		if (left_id != 0) //만약 왼쪽 값이 0이 아니면 ( 뭔가를 추가 해야하면)
		{
			TreeNodemake(left_id, 'L', v); // 왼쪽에 추가함
		}
		v = findID(root, id);
		if (right_id != 0) //만약 오른쪽 값이 0이 아니면 ( 뭔가를 추가 해야하면)
		{
			TreeNodemake(right_id, 'R', v); // 오른쪽에 추가함
		}
	}
	return root; // 다 끝나면 root를 반환 함
}

 

Tree의 ID 찾는 함수

TreeNode* findID(TreeNode* v, int id)
{
	if (v != NULL) //v가 NULL 값이 아니면
	{
		if (v->id == id) //만약 v의 id가 찾는 값이면
			return v; //v 를 반환함
		TreeNode* p = NULL; //노드 p 생성후 NULL 값 대입함
		p = findID(leftChild(v), id); // 재귀함수로 왼쪽 줄기에서 id를 찾음
		if (p != NULL) // 만약 찾으면
			return p; // id를 반환함
		p = findID(rightChild(v), id); // 재귀함수로 오른쪽 줄기에서 id를 찾음
		if (p != NULL) // 만약 찾으면
			return p; // id를 반환함
	}
	return NULL;  //없으면 NULL 값을 반환함
}​

 

출력 함수

void print(TreeNode* v, char* s)
{
	int a = strlen(s);
	printf(" %d", v->id);

	for (int i = 0; i < a; i++)
	{
		if (s[i] == 'R')
		{
			v = v->right;
			printf(" %d", v->id);
		}
		else if (s[i] == 'L')
		{
			v = v->left;
			printf(" %d", v->id);
		}
	}
	printf("\n");
}