#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
struct pnode{ //구조체 선언
char data; //테이터 수식
int num; //트리구조의 번지
struct pnode *left; //왼쪽 노드의 포인터 변수
struct pnode *right; //오른쪽 노드의 포인터 변수
};
typedef struct pnode NODE; //이름을 노드로 정의한다.
NODE *insert(NODE *p, int num, char x) //삽입 함수
{ //포인터 변수와 번지와 데이터를 받음
NODE *temp1; //포인터 선언
NODE *temp2;
if(p==NULL) //포인터 p에 데이터가 없을 경우
{
p=(NODE *)malloc(sizeof(NODE)); //포인터 생성b
if(p==NULL)
{ //생성을 실패했을 경우 에러발생
printf("에러\n");
exit(0);
}
p->num=num; //번지를 구조체에 대입
p->data=x; //계수를 구조체에 대입
p->left=NULL; //왼쪽을 NULL지정
p->right=NULL; //오른쪽을 NULL지정
}
else //포인터 p에 데이터가 있을 경우
{
temp1 = p; //temp1에 p의 주소를 대입
while (temp1 != NULL) //temp1이 NULL 아닐때까지 반복
{
temp2 = temp1; //temp2에 temp1의 주소를 대입
if(temp1->num > num)//temp1의 번지가 입력받은 번지보다 작을 경우
{
temp1=temp1->left; //왼쪽 노드로 이동
}
else //temp1의 번지가 입력받은 번지보다 클 경우
{
temp1 =temp1->right; //오른쪽 노드로 이동
}
} //반복문의 종료되면 더 이상 하위 노드는 없다
if(temp2->num > num)//temp2의 번지가 입력받은 번지보다 작을 경우
{ //왼쪽으로 노드 생성
temp2->left = (NODE *)malloc(sizeof(NODE));
temp2 = temp2->left;
if(temp2 == NULL){ //노드 생성 실패시 에러 발생
printf("에러\n");
exit(0);
}
temp2 -> num = num; //temp2에 번지 대입
temp2 -> data = x; //tmep2에 데이터 대입
temp2 -> left = NULL; //temp2의 왼쪽과 오른쪽을 NULL 입력
temp2 -> right = NULL;
}
else{ //temp2의 번지가 입력받은 번지보다 클 경우
temp2->right = (NODE *)malloc(sizeof(NODE));
//오른쪽으로 노드 생성
temp2 =temp2 ->right;
if(temp2 == NULL){ //노드 생성 실패시 에러 발생
printf("에러\n");
exit(0);
}
temp2 -> num = num; //temp2에 번지 대입
temp2 -> data = x; //temp2에 데이터 대입
temp2 -> left = NULL; //temp2의 왼쪽과 오른쪽을 NULL입력
temp2 -> right = NULL;
}
}
return (p); //리턴 포인터 p
}
NODE *searching(NODE* p, int num, NODE **parent) //검색 함수
{
NODE* current; //노드 포인터 선언
current = p; //current에 입력받은 포인터 p의 주소 대입
*parent = NULL; //이중포인터 parent을 NULL 지정
if(current == NULL) //current가 NULL이면 에러
return(NULL); //리턴 NULL을 해줌
while(current != NULL){ //current가 NULL아닐때까지 반복
if(current->num ==num) //current의 번지가 입력 받은 번지와 같을 경우
return(current); //리턴 current
else{ //번지가 다를 경우
*parent = current; //부모포인터를 current로 지정 후
if(num < current->num) //입력 받은 번지 값보다 current의 번지 같이 클 경우
current = current->left; //current는 왼쪽 지정
else //작을 경우
current = current->right; //current는 오른쪽 지정
}
}
return(NULL);
}
NODE *deletion(NODE* p, int num) //삭제 함수
{
NODE* current, *parent, *temp; //포인터 선언
current = searching(p, num, &parent); //검색 함수를 호출
if(current == NULL) //검색되어 리턴된 값이 NULL이면 에러
{
printf("데이터번지가 없습니다.\n");
return(p);
}
else //검색된 값이 NULL 아니면
{
if(current == p) //검색된 값이 루트와 같을 경우
{
temp = current ->left; //temp에 검색된 값의 왼쪽을 대입하고
parent = current ->right; //parent에 검색된 값의 오른쪽을 대입한다.
p = temp; //p에 temp를 대입
while(temp ->right != NULL) //temp의 오른쪽 같이 NULL아닐 때까지 반복
temp = temp ->right; //temp에 temp 오른쪽 노드값을 대입
temp ->right = parent; //반복문이 끝나면 temp의 오른쪽 노드에 parent의 값을 대입
free(current); //current를 포인터를 해제한다.
return(p);
}
if(current ->left != NULL && current ->right !=NULL)
{ //검색된 값이 루트는 아니지만 양쪽다 노드를 가지고 있을 경우
if(parent ->left == current) //부모 노드의 왼쪽노드와 검색된 값이 같은 경우
{
temp = current ->left; //temp에 검색된 값의 왼쪽노드를 대입
parent ->left = current ->left; //parent의 왼쪽 노드에 검색된 왼쪽 노드를 대입
while(temp ->right != NULL) //temp의 오른쪽 노드가 NULL아닐 때까지 반복
temp = temp->right; //temp에 temp의 오른쪽 노드를 대입
temp->right = current ->right;
//반복이 끝나면 temp의 오른쪽 노드에 검색된 노드의 오른쪽 노드를 대입
current ->left=NULL; //검색된 왼쪽 노드에 NULL을 대입
current ->right=NULL; //검색된 오른쪽 노드에 NULL을 대입
}
else //부모 노드의 오른쪽노드와 검색된 값이 같은 경우
{
temp = current ->right; //temp에 검색된 값의 오른쪽노드를 대입
parent ->right = current ->right;//parent의 오른쪽 노드에 검색된 오른쪽 노드를 대입
while(temp ->left != NULL) //temp의 왼쪽 노드가 NULL아닐 때까지 반복
temp = temp->left; //temp에 temp의 오른족 노드를 대입
temp->left = current ->left;
//반복이 끝나면 temp의 왼쪽 노드에 검색된 노드의 왼쪽 노드를 대입
current ->left=NULL; //검색된 왼쪽 노드에 NULL을 대입
current ->right=NULL; //검색된 오른쪽 노드에 NULL을 대입
}
free(current); //current를 포인터를 해제한다.
return(p);
}
if(current->left == NULL && current ->right != NULL)
{ //검색된 값이 루트는 아니지만 왼쪽에는 NULL이고 오른쪽은 값을 가지고 있을 경우
if(parent ->left ==current) //부모 노드의 왼쪽노드와 검색된 겂이같은 경우
parent ->left = current ->right;//부모의 왼쪽노드와 검색된 노드의 오른쪽 노드 대입
else //부모 노드의 오른쪽 노드와 검색된 값이 같은 경우
parent ->right = current ->right;//부모의 오른쪽노드와 검색된 노드의 오른쪽 노드 대입
current ->right = NULL; //검색된 노드의 오른쪽 노드에 NULL 대입
free(current); //currenat를 포인터를 해제한다.
return(p);
}
if(current ->left != NULL && current ->right ==NULL)
{ //검색된 값이 루트는 아니지만 왼쪽에는 값이 있고 오른쪽에는 값이 NULL일 경우
if(parent ->left == current) //부모노드의 왼쪽 값이 검색된 값과 같을 경우
parent ->left = current ->left;//부모노드의 왼쪽 노드에 검색된 노드의 왼쪽 값을 대입
else //부모노드의 오른쪽 값이 검색된 값과 같을 경우
parent->right = current ->left;//부모노드의 오른쪽 노드에 검색된 노드의 왼쪽 값을 대입
current ->left = NULL; //검색된 노드의 왼쪽 값에 NULL을 대입
free(current); //current를 포인터를 해제한다.
return(p);
}
if(current ->left == NULL && current ->right == NULL)
{ //검색된 값이 루트는 아니지만 왼쪽과 오른쪽 모두 NULL인 경우
if(parent ->left == current) //부모 노드의 왼쪽 노드와 검색된 값이 같은 경우
parent ->left = NULL; //부모 노드의 왼쪽 값을 NULL로 해준다.
else //부모 노드의 오른쪽 노드와 검색된 값이 같은 경우
parent ->right = NULL; //부모 노드의 오른쪽 값을 NULL로 해준다.
free(current); //current를 포인터를 해제한다.
return(p);
}
}
return (p);
}
void preOrder(NODE *ptr){ //전위 운행법 함수
if(ptr){ //재귀적으로 호출
printf("%c ",ptr->data); //루트노드부터 출력후 왼쪽 노드부터 출력
preOrder(ptr->left); //왼쪽 서브 트리를 모두 방문
preOrder(ptr->right); //오른쪽 서브 트리들은 방문
} //모든 노드에 재귀적으로 적용 모든 노드를 한번씩 방문
}
void inOrder(NODE *ptr){ //중위 운행법 함수
if(ptr){ //재귀적으로 호출
inOrder(ptr->left); //먼저 왼쪽 서브 트리를 모두 방문
printf("%c ",ptr->data); //왼쪽 방문이 끝난 노드부터 출력
inOrder(ptr->right); //오른쪽 서브 트리들을 방문
} //모든 노드에 재귀적으로 적용 모든 노드를 한번씩 방문
}
void postOrder(NODE *ptr){ //후위 운행법 함수
if(ptr){ //재귀적으로 호출
postOrder(ptr->left); //왼쪽 서브트리를 모두 방문
postOrder(ptr->right); //오른쪽 서브트리를 모두 방문
printf("%c ",ptr->data); //자식노드가 없거나 출력된 상태이면 출력
} //모든 노드에 재귀적으로 적용 모든 노드를 한번식 방문
}
void printTree(NODE *point) //운행법을 호출 하는 함수
{
printf("\n전위 운행법으로 출력 >> ");
preOrder(point); //전위 운행법 호출
printf("\n");
printf("중위 운행법으로 출력 >> ");
inOrder(point); //중위 운행법 호출
printf("\n");
printf("후위 운행법으로 출력 >> ");
postOrder(point); //후위 운행법 호출
printf("\n");
}
void main(){ //메인 함수
int i, j, del, num; //각종 변수 선언
int k=2;
char x, yn, ny;
NODE *point = NULL;
printf("컴퓨터정보학과 2006270191 정 훈 승\n");
printf("포화 이진 트리의 원하는 레벨을 입력하세요! >> ");
scanf("%d",&j); //레벨을 입력을 받는다.
for(i=2;i<=j;i++){ //레벨 값에 맞는 포화 이진 트리의 노드를 계산
k = k * 2; //2의 k승에 빼기 1을 하면
} k = k - 1; //포화 이진 트리의 총 노드가 나온다.
for (i=1; i<=k;i++){ //총 노드수 만큼 입력을 받는다.
printf("%d번째 부터 번지와 데이터값순으로 입력하세요! >> ",i);
scanf("%d %s",&num, &x); //입력은 번지와 데이터값을 받는다.
point = insert (point, num, x); //삽입 함수를 호출한다.
}
printTree(point); //삽입 함수가 완료하면 운행법을 호출 한다.
printf("삭제를 원하시면 y 종료를 원하시면 n? >> ");
scanf("%s", &yn); //삭제 여부를 물어본다.
if(yn == 'y') //삭제를 원할 경우
{
do
{
printf("삭제할 번지를 입력하세요! >>");
scanf("%d", &del); //삭제할 번지를 입력 받는다
point = deletion(point, del); //입력받은 번지로 삭제 함수를 호출
printf("더 삭제 하실꺼면 y, 그만 삭제를 원하시면 n? >> ");
scanf("%s", &ny); //더 삭제를 원할 경우 계속 반복
if(ny == 'n') //그만 삭제를 원할경우 반복이 종료
{
break;
}
}while(1); //삭제를 원하면 무한 반복
}
else{
exit(0); //처음 삭제를 원하지 않을 경우 종료
}
printTree(point); //만약 삭제를 한번이라도 했으면 운행법 호출
}
// 참 쉽죠? ^^ 재밌게 공부하세요
