헬창 개발자

이진 트리를 이용한 연락처 프로그램 : C언어 본문

자료구조

이진 트리를 이용한 연락처 프로그램 : C언어

찬배 2021. 7. 28. 13:33
설계도

코드
#include <stdio.h>
#include<stdlib.h>
#include <string.h>
#define MAX_NAME 20 // name 사이즈 정의
#define MAX_NUMBER 40 // number 사이즈 정의
typedef struct list { // 정보 저장 구조체
    char name[MAX_NAME]; //이름
    char number[MAX_NUMBER]; //전화번호
}list;
typedef struct tree { // 노드 구조체
	list key; //정보 저장 구조체
    struct tree* left; // 링크
    struct tree* right; // 링크
}tree;
void insert(tree** root, list data) { // 삽입 함수
    tree* p = NULL; //부모 노드
    tree* t = *root; // 자식 노드

    while (t != NULL) { // t가 NULL이 아니다 -> 루트가 있으며 탐색이 끝나면 말단이다.
        if (strcmp(data.name,t->key.name)==0) return; // 키 중복 확인
        p = t; // 다음 값을 순회하기 위해 저장
        if (strcmp(data.name, t->key.name) < 0) t = t->left; // 루트 키값 보다 작음, 왼쪽으로 이동
        else t = t->right; // 루트 키값 보다 큼, 오른쪽으로 이동
    }

    tree* newtree = (tree*)malloc(sizeof(tree)); // 새로운 노드 동적할당으로 생성
    newtree->key = data; // 키값 삽입
    newtree->left = newtree->right = NULL; // 링크 초기화
    
    if (p != NULL) { // p는 삽입할곳에 부모 노드를 가리키고 있음
        if (strcmp(data.name, p->key.name) < 0) p->left = newtree; // 키 값을 비교해서 작으면 왼쪽
        else p->right = newtree; // 키 값을 비교해서 크면 오른쪽
    }
    else *root = newtree;  // 다 해당 안되면 처음 생성되는 루트 노드이다.
}
void delete(tree** root, list data) { // 삭제 함수
    tree* p=*root;// 현재 노드(삭제 노드)
    tree* parent=NULL;// 부모 노드
    tree* child;// 자식 노드
    tree* succ;// 후계자 노드1
    tree* succ_parent;// 후계자 노드2
    while ((p!=NULL)&&(strcmp(data.name,p->key.name)!=0)){ // 키 값이 같을때 까지 탐색
        parent = p;
        if (strcmp(data.name, p->key.name) < 0) { // 부모값보다 작음
            p = p->left;
        }
        else {//부모값보다 큼
            p = p->right;
        }
        if (p == NULL) return; // 찾는 값이 없음
    }

    // 단말 노드인경우
    if ((p->right == NULL) && (p->left == NULL)) { // 삭제할 노드의 양쪽 링크가 NULL값을 만족
        if (parent != NULL) { // 삭제할 노드의 부모노드를 가리키고 있어야한다.
            if (parent->left == p) parent->left = NULL; // 부모 노드의 왼쪽이 삭제할 노드면 링크 값을 NULL로 바꿈
            else parent->right = NULL; // 부모 노드의 오른쪽이 삭제할 노드면 링크 값을 NULL로 바꿈
        }
        else root = NULL; // 해당 안되면 전체가 1개의 노드이다.
    }

    // 한개의 자식 노드
    else if ((p->right == NULL) || (p->left == NULL)) { // 삭제 노드가 왼쪽 or 오른쪽이 NULL이다.
        if ((p->right == NULL)) child = p->left; // 삭제 노드 오른쪽이 NULL이면 왼쪽에 있는 노드를 child에 넣어준다.
        else child = p->right; // 삭제 노드 왼쪽이 NULL이면 오른쪽에 있는 노드를 child에 넣어준다.
        if (parent != NULL) {
            if (parent->right == p) parent->right = child; // 부모 노드의 오른쪽이 삭제할 노드이면 자식노드를 부모노드의 오른쪽과 연결
            else parent->left = child; // 부모 노드의 왼쪽이 삭제할 노드이면 자식노드를 부모노드의 완쪽과 연결
        }
        else *root = child; // 삭제 후 값이 자식노드밖에 없으면 루트로 지정
    }

    // 두개의 자식 노드
    else {
        succ_parent = p; // 삭제할 노드를 삽입
        succ = p->right; // 삭제할 노드의 오른쪽 값 삽입
        while (succ->left!=NULL) // 후계자를 찾아서 왼쪽으로 계속 이동
        {
            succ_parent = succ;
            succ = succ->left;
        }
        if (succ_parent->left == succ) succ_parent->left = succ->right; // 후계자 부모 노드의 왼쪽이 후계자 노드가 맞으면 부모노드의 왼쪽을 NULL값으로 바꿈
        else succ_parent->right = succ->right; // 후계자 부모 노드의 오른쪽이 후계자 노드가 맞으면 부모노드의 오른쪽을 NULL값으로 바꿈
        p->key = succ->key; // 삭제할 노드의 키 값에 후계자의 키 값을 삽입
        p = succ; // p는 후계자를 가리킴
    }
    free(p); // 메모리 할당 해제
}
void print(tree* root) { // 트리 출력 함수
    if (root != NULL) { // 중위 순회
        print(root->left);
        printf("\t %s : %s",root->key.name, root->key.number);
        printf("\t\t\t [");
        for (int i = 0; i <= MAX_NAME; i++) {
            if (root->key.name[i] == NULL)break;
            else printf("%d ", root->key.name[i]);
        } printf("]\n");
        print(root->right);
    }

}
tree* search(tree* root, list data) { // 검색 함수

    while (root != NULL) {
        if (strcmp(data.name, root->key.name) == 0) return root; // 키 값 일치하면 root 리턴
        else if (strcmp(data.name, root->key.name) < 0) root = root->left; // 키 값이 작으면 왼쪽으로 이동
        else if (strcmp(data.name, root->key.name) > 0) root = root->right; // 키 값이 크면 오른쪽으로 이동
   }
}
void run() { // 시스템 구동

    list e; // 정보 구조체
    char str; // 스위치문에서 입력 받을 변수
    tree* root = NULL; // 최초 트리
    tree* temp; // 검색 노드를 반환 받을 노드
   
    while (1)
    {
        printf("삽입(i) 탐색(s) 출력(p) 삭제(d)");
        scanf_s("%c", &str,sizeof(str));
        getchar();
        switch (str)
        {
        case 'i':
            printf("친구의 이름:");
            gets(e.name);
            printf("친구의 전화번호:");
            gets(e.number);
            insert(&root, e);
            break;
        case 's':
            printf("검색 할 친구의 이름:");
            gets(e.name);
            temp=search(root, e);
            printf("친구의 전화번호:%s\n",temp->key.number);
            break;
        case 'p':
            printf("출력:");
            print(root);
            break;
        case 'd':
            printf("삭제 할 친구의 이름:");
            gets(e.name);
            delete(&root, e);
            break;
        default:
            printf("다시 입력");
            break;

        }
    }
}
int main() {
    run(); // 시스템 구동 함수 실행
}

 

결과 화면

Comments