알고리즘 과제 #1 (이진 트리 높이 구하기)

문제 :이진트리의 높이 구하기

이진트리의 높이를 구하는 알고리즘을 작성하시오

위의 예에서 이진트리의 높이는 6이다

입력 형식

입력 파일의 이름은 input.txt이다. 여러 개의 테스트 데이터가 입력될 수 있다. 첫째 줄에는 테스트 데이터의 개수가 입력된다. 둘째 줄에는 첫 번째 데이터의  노드의 개수를 나타내는 정수  이 주어진다. 다음 개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. 노드들의 번호는 1부터 까지로 주어진다. 자식이 없는 경우에는 자식 노드의 번호가 -1로 주어진다. 루트 노드의 번호는 1이다. 그 다음 줄부터 나머지 데이터가 같은 방식으로 주어진다.  

출력 형식

데이터마다 한줄 씩 이진트리의 높이를 순서대로 출력한다.

  

입력 예

2            // 데이터의 수    19           // 첫 번째 데이터의 노드의 수 1 2 3        // 첫 번째 이진 트리  2 4 5 3 6 7 4 8 -1 5 9 10 6 11 12 7 13 -1 8 -1 -1 9 14 15 10 -1 -1 11 16 -1 12 -1 -1 13 17 -1 14 -1 -1 15 18 -1 16 -1 -1 17 -1 19 18 -1 -1  19 -1 -1  3           // 두 번째 데이터의 노드의 수 1 2 3       // 두 번째 이진 트리  2 -1 -1 3 -1 -1

출력 예

6 2

문제 해결

1) 알고리즘의 도형화

2) 메모리 분석 - 배열을 이용한 트리구성

3) 구현 소스 코드

#include <iostream> #include <fstream> using namespace std; /* 프로그램 작성자 : americano@korea.ac.kr 개발 날짜 : 2012-3-19 */ //노드선언 typedef class treeRecord{ public: int data; //노드의 데이터 int height; //트리 안에서 노드의 높이 treeRecord* LChild; //왼쪽 자식 treeRecord* RChild; //오른쪽 자식 treeRecord(){ data = -1; //기본 데이터는 -1값으로 초기화 height = 0;//기본 노드의 높이는 0으로 초기화 treeRecord* LChild = NULL; // 왼쪽자식은 아무것도 가리키지 않음 treeRecord* RChild = NULL; // 오른쪽자식은 아무것도 가리키지 않음 } }Node; typedef Node* Nptr; //클래스선언 class Tree{ public: //함수선언 Tree(){ index = 0; //트리의 노드 개수는 0으로 초기화 searchnode = NULL; // 입력 에러를 막기위한 노드변수 } ~Tree(){} void print_height(){ //트리의 높이를 출력해주는 함수 cout<<maxHeight<<endl; } //search 함수 //root의 주소와 data값을 받아 트리안에서 data값을 가지고 있는 node가 있는지 탐색해주는 함수 //searchnode 의 변수에 찾은 노드주소를 입력함 void search(Nptr T, int data){ if(T->data==-1){ //root의 데이터가 없을 시(최초입력) searchnode = NULL; return; } else if(T->data == data){ //node를 찾을 시 데이터를 가지고 있는 노드를 searchnode에 입력 searchnode = T; return; } if(T->LChild != NULL && searchnode==NULL){ //왼쪽자식으로 이동, 노드를 찾으면 실행되지않음 search(T->LChild, data); } if(T->RChild != NULL && searchnode==NULL){ //오른쪽자식으로 이동, 노드를 찾으면 실행되지않음 search(T->RChild, data); } return; } void insert(Nptr root, int current, int left, int right){ searchnode = NULL; // 삽입할 위치를 찾을 때 사용하는 포인터 초기화 search(root,current); // 삽입할 위치 탐색 if(searchnode==NULL && root->height != 0){ // 처음 삽입이 아닌데 찾으려는 노드가 없을 경우 cout<<"input.txt file is wrong"<<endl; //오류보고 return; // 함수종료 } else if(searchnode==NULL && root->height ==0){ //처음 삽입이라서 찾으려는 노드가 없을 경우 if(current != -1){ // 노드번호는 -1이면 안된다. root->data = current; //노드값 입력 root->height = 1; // 높이를 1로 초기화 index++; // 노드 갯수 증가 maxHeight = root->height; //최대높이를 루트의 높이로 설정 searchnode = root; // 트리에 첫 노드가 입력 되었으므로 그다음의 자식입력을 위해 포인터를 root로 변경 } } if(left != -1){ //왼쪽자식 노드값이 -1이 아닐 경우에만 입력 (root+index)->data = left; //노드값입력 searchnode->LChild = (root+index); //부모노드와 왼쪽자식노드를 연결해줌 (root+index)->height = (searchnode->height+1); //왼쪽자식노드의높이를 부모노드의 높이+1로 설정 (root+index)->LChild = NULL; //새로 생긴 왼쪽자식의 노드의 자식포인터들을 NULL로 초기화 (root+index)->RChild = NULL; if(maxHeight< (root+index)->height) //최대높이가 증가했을 경우 확인하고 높이가 변했을 경우 값 변경 maxHeight = (root+index)->height; index++; //노드개수 증가 } if(right != -1){ //왼쪽자식 노드입력과 동일 (root+index)->data = right; searchnode->RChild = (root+index); (root+index)->height = (searchnode->height+1); (root+index)->LChild = NULL; (root+index)->RChild = NULL; if(maxHeight< (root+index)->height) maxHeight = (root+index)->height; index++; } } private: int maxHeight; //최대높이변수 int index; //노드갯수 Nptr searchnode; //탐색을 위해 사용되는 노드포인터 //함수선언 }; int main(){ ifstream fin; //입력스트림설정 int number_data; //트리의 갯수 int number_node; //그 트리의 노드 갯수 int current, right, left; //부모노드, 자식노드 fin.open("input.txt"); //입력파일은 input.txt파일 if(fin.fail()){ //만약 값을 받아오지 못했을 경우 cout<<"This progrm can't open the file"<<endl; return 0; //에러메세지 출력 후 프로그램종료 } fin>>number_data; // 트리의 갯수를 받아옴 for(int i=0; i<number_data; i++){ //만약 트리의 갯수가 0일경우 실행안됨 Tree tree; //트리 생성 fin>>number_node; // 노드의 갯수를 받아옴 Nptr node = new Node[number_node]; // 노드의 갯수만큼 배열을 동적할당함 for(int j=0; j<number_node; j++){ //노드의 갯수만큼 트리에 삽입 fin>>current>>left>>right; //한줄을 받아옴 tree.insert(node, current, left, right); //부모노드와 자식노드를 트리에 삽입 } tree.print_height(); //트리의 높이 출력 delete [] node; //동적할당 해제 } return 0; }

4) 소스코드 설명

- 소스 개요

    - 노드 클래스 : class treeRecord{}

    - 트리 클래스 : class Tree{}

    - 메인 함수 : int main(){}

- 알고리즘 분석

    - 노드 클래스 : class treeRecord{}

설명 : 트리구조에 포함되는 노드를 만들 때 쓰이는 클래스입니다. 클래스는 4개의 변수와 1개의 생성자, 0개의 함수를 가지고 있습니다. 

    - 변수 :

int data // 노드의 번호 값을 가지는 변수

int height // 트리에서 그 노드가 가지는 높이

treeRecord* LChild // 노드의 왼쪽 자식을 가리키는 클래스포인터

treeRecord* RChild // 노드의 오른쪽 자식을 가리키는 클래스포인터

    - 생성자: treeRecord(){}

노드번호(data) 값은 기본적으로 -1로 초기화 됩니다. -1을 가지면 이 노드는 없는 것으로 간주됩니다. 높이(height)는 0으로 초기화되어 트리에 노드가 삽입될 시 높이가 설정되게 됩니다. 각각의 자식을 가리키는 포인터는 NULL로 초기화됩니다.

    - 트리 클래스 : class Tree{}

설명 :  트리를 만드는 클래스입니다. 클래스는 3개의 변수와 1개의 생성자, 3개의 함수를 가지고 있습니다. 

메인함수에서 트리모양의 자료구조를 만들 때 쓰이는 클래스입니다. 메인함수에서 트리의 root 주소와 입력할 트리번호들을 아규먼트로 보내면 기존 트리에 노드를 추가합니다. 트리에서 노드를 입력할 때는 삽입함수를 이용합니다. 

- 함수 : 

    - 삽입함수 : void insert(Nptr root, int current, int left, int right){}

삽입함수는 검색함수를 이용합니다. 삽입함수의 알고리즘은 다음과 같습니다.

아규먼트로 트리의 root 주소, 노드번호, 왼쪽자식노드번호, 오른쪽자식번호를 넘겨 받습니다. 기본 개요는 한번의 함수 호출에 노드번호의 위치에 왼쪽과 오른쪽 자식을 만들고 연결하는 방식을 취합니다. 삽입함수는 검색함수를 호출하여 부모노드를 검색하여 현재트리에서 입력 받은 노드번호를 어디에 입력하면 될지 확인합니다. 

처음 입력 시에는 기본 트리를 구성합니다. 그리고 삽입함수는 자식 변수들의 높이도 설정해줍니다. 단 이 때 자식변수의 번호값이 -1일 경우는 아무런 행동도 하지 않습니다. 기본적으로 자식변수 포인터에 NULL 값이 초기화 되어있기 때문에 아무런 행동도 하지 않습니다. 만약 입력받은 노드번호가 트리에 없을 시 함수는 종료됩니다.

삽입함수에서 검색함수를 호출하는데 검색함수의 알고리즘은 다음과 같습니다.

시간복잡도 : 빅오 : O(1)

    - 검색함수 : void search(Nptr T, int data){}

검색함수는 root주소와 찾으려는 노드번호를 아규먼트로 받아 트리의 부모노드위치를 알려주는 함수입니다. 하지만 리턴 방식을 취하는 것이 아닙니다. 트리 클래스 안에는 검색한 위치를 저장하는 노드포인터가 기본적으로 존재합니다. 이 포인터에 주소값을 설정해주면 삽입함수가 가져다가 쓰는 형식입니다. 재귀적 호출을 사용하였습니다.

시간복잡도 : 빅오 : O(n) // 기본트리탐색과 달리 모든 노드를 검색합니다.

    - 출력함수 : void print_height(){}

트리의 높이값을 출력합니다. 

시간복잡도 : 빅오 : O(1)

- 변수 :

    int maxHeight; //최대높이변수

    int index; //노드갯수

    Nptr searchnode; //탐색을위해사용되는노드포인터

- 생성자 : Tree(){}

    - 트리의 높이인 maxHeight와 노드의 개수인 index를 0으로 초기화합니다. 또한 부모노드를 검색해주는 노드포인터 serchnode를 NULL로 초기화합니다.

- 메인 함수 : int void main(){}

설명 :  기본 메인함수입니다. 입력스트림을 설정하여 input.txt파일로부터 데이터를 받습니다. 데이터가 잘못되었을 경우 프로그램은 종료됩니다. 이상이 없다면 2개의 for문으로 프로그램은 구성됩니다. 첫 번째 for문에서는 트리의 개수만큼 루프를 돌며 노드의 개수만큼 배열을 동적할당합니다. 두 번째 for문은 노드의 개수만큼 루프를 돌며 트리를 구성하고 후에 트리의 높이를 출력하며 루프는 종료됩니다.

시간복잡도 : 빅오 : O(n^2)

 

- 시간복잡도 - O(n^2) 

    - 노드 클래스 : class treeRecord{} 

    -> 함수없음

    - 트리 클래스 : class Tree{} 

    -> 삽입함수 : void insert(Nptr root, int current, int left, int right){} :   O(1)

    -> 검색함수 : void search(Nptr T, int data){} : O(n) (모든 노드를 검색합니다.)

    -> 출력함수 : void print_height(){} : O(1)

    - 메인 함수 : int main(){}

    -> O(n^2)

 

- 공간복잡도 - n 

노드의 크기만큼 배열을 생성하고 다음 트리 생성시 기존 트리의 메모리를 해제 한 후 다시 노드의 크기만큼 메모리를 생성합니다.