/*
 http://sosal.tistory.com/
 * made by so_Sal
 */

이진트리를 짜봤습니당.
워낙 유명한 자료구조라
인터넷에서 쉽게 구조체나 생성함수, 삭제함수 등을 구할 수 있었지만
레벨에 따른 트리를 생성할 수 있도록 만들어놓은
함수는 안보이더라구요, 그래서 간단하게 만들어봤습니다 ㅎㅎ
각 노드의 value는 char형태로 이루어져있는데,
default parameter를 통해 자동으로 B부터 CDE~~~쭉쭉
만들어지게 해놨습니다.
숫자를 원하신다면 class의 value 자료형을 바꾸고,
default parameter값만 바꿔주시면 되겠죠?

#include<iostream>
using namespace std;


class node{
private:
    char value;
public:
    node(char val){
        value=val;
    }
    char getValue(){
        return value;
    }
    node* left;
    node* right;
    ~node(){
        delete this;
    }
};

node* CreateNode(char value);      // 노드생성함수
void CreateTree(node* root,int depth,char val='A'); //자동 트리생성 함수
void DeleteNode(node* delNode);   // 노드삭제함수
void DestroyTree(node* root);        // 트리 삭제함수
void PrintTree(node* Node);          // 노드 출력함수 (전위식)

int main(){
    node* root = CreateNode('A');    // root 노드를 생성한 후
    CreateTree(root,3);                    // 레벨3의 트리를 생성
    PrintTree(root);
  
    return 0;
}

node* CreateNode(char value){
    node* newNode = new node(value);   // 생성 후
    newNode->left = NULL;                     // 각 value 초기화
    newNode->right = NULL;

    return newNode;
}

void CreateTree(node* root,int depth,char val){
   
    if(depth==0)
        return;

    root->left=CreateNode(val+1);               //재귀형식으로 val 값을 바꿔가면서
    root->right=CreateNode(val+2);             //각 노드의 값을 삽입, 생성
    val+=2;

    CreateTree(root->left,depth-1,val);
    CreateTree(root->right,depth-1,val);     // 재귀~

    return;
}

void PrintTree(node* Node){
    if(Node == NULL)
        return;

    cout<<Node->getValue()<<endl;   // 전위식 출력
    PrintTree(Node->left);                   
    PrintTree(Node->right);            // 재귀
   
    return;
}

void DeleteNode(node* delNode){
    delete delNode;
    return;
}

void DestroyTree(node* root){
    DestroyTree(root->left);
    DestroyTree(root->right);
    DeleteNode(root);
    return;
}


소멸자 함수에 delete this를 이용해서
객체를 삭제했기 때문에 위 소스에서는
DestroyTree 함수를 사용할 필요가 없습니다.~~

참고자료 : 뇌를 자극하는 알고리즘

Posted by sosal sosal

댓글을 달아 주세요