Distinct Binary Tree(상이한 이진 트리)

#include <iostream>
#include <stdlib.h>
#include <process.h>
using namespace std;

class Tree      // 프로그램 전체를 제어하는 클래스
{
 private:
  int leftcount;   // 비주얼하게 출력 시 왼쪽 자식을 표현하기 위한 변수
  int rightcount;   // 비주얼하게 출력 시 오른쪽 자식을 표현하기 위한 변수
 public:
  Tree()     // 생성자 함수
  {
   leftcount = rightcount = 0;
  }
  ~Tree()     // 소멸자 함수
  {
  }
  void Input();     // 값을 입력 받는 함수
  void Output(int);    // Tree를 비주얼하게 출력하는 함수
  unsigned long Treecount(int); // 입력 받은 노드로 만들 수 있는 트리 개수를 계산할 함수
};

void main()      // 함수의 시작
{
 Tree *start;
 start = new Tree;
 start->Input();
}

void Tree::Input()    // 명령어 선택창
{
 while(1)
 {
  int i=0;     // 노드 개수를 입력 받을 변수
  cout << "Input node count(exit=0) : ";
  cin >> i;
  if(i <= 0)     // 입력받은 노드의 개수가 0 이하이면
   _exit(1);    // 프로그램 종료
  else
   Output(i);   // 출력함수로 입력 받은 노드개수 전달
 }
}

unsigned long Tree::Treecount(int temp) // 입력 받은 노드로 만들 수 있는 트리 개수를 계산할 함수
{
 unsigned long result=0; // 결과값을 기억할 공간
 if(temp == 0 || temp == 1) // 이 부분만 있어도 알고리즘은 구현된다.
  return 1;    // 하지만 재귀함수를 돌리면 엄청나게 시간이 걸린다.
 else if(temp == 2)   // 그래서 샘플 값들을 많이 넣어 줄 수록 빠른 연산이
  return 2;    // 가능하다. 그래서 양심적으로 노드개수가 3개일 때까지
 else if(temp == 3)   // 넣겠다. 만약에 더 빨른 연산을 원한다면 아래 주석을
  return 5;    // 해제하면 된다.
 else if(temp == 4)
  return 14;
 else if(temp == 5)
  return 42;
 else if(temp == 6)
  return 132;
 else if(temp == 7)
  return 429;
 else
 {
  for(int i=0; i<temp; i++)       // 입력 받은 노드의 개수 만큰 반복
  {
   result += Treecount(i)*Treecount(temp-1-i);  // 재귀함수를 돌면 값을 누적 연산
  }
 }
 return result;
}

void Tree::Output(int totalcount)    // Tree를 비주얼하게 출력하는 함수
{
 unsigned long imsi=totalcount;    // 마지막 부분에 다시 총 노드수를 표현하기 위한 변수.
 // 출력시 나타는 형태에 대한 설명
 cout << "result : " << Treecount(totalcount) << endl;
 cout << "<number> : node number" << endl;
 cout << "/ : left child, ㄱ : right child" << endl;
 while(totalcount > 1)
 {
  for(leftcount=totalcount-1, rightcount=0; leftcount >= 0; leftcount--, rightcount++)
  {
   cout << "\t" << "<total node : " << totalcount << ">" << endl;
   if(leftcount == 0)     // leftchild가 0이면 그쪽은 출력 안함
   {
    cout << "\t" << "            ㄱ" << endl;
    cout << "\t\t    " << "<" << rightcount << ">" << endl;
   }
   else if(rightcount == 0)   // rightchild가 0이면 그쪽은 출력 안함
   {
    cout << "\t" << " /" << endl;
    cout << "       " << "<" << leftcount << ">" << endl;
   }
   else        // leftchild, rightchild 양쪽 다 있을 경우 다 출력
   {
    cout << "\t" << " /          ㄱ" << endl;
    cout << "       " << "<" << leftcount << ">" << "\t    " << "<" << rightcount << ">" << endl;
   }
  }
  totalcount--;
 }
 cout << "result : " << Treecount(imsi) << endl;
}

<그림 설명>
위에 result의 값은 입력한 값, 즉 노드이 개수로 그릴 수 있는 서로다른 트리의 개수를 출력하는 부분이다. <total node : 3>부분은 이 트리의 노드의 총 수가 3개라는 것을 뜻하고 <2>라고 써 있는 부분은 노드 2개로 표현될 수 있는 트리라는 뜻이다. 이 2개로 나타낼 수 있는 트리는 아랫 부분에 표현된다.

즉, 옆에 그림을 설명하자면 노드 3개로 표현 가능한 트리의 수는 총 5개로 모양은 왼쪽 자식이 2개인 경우 2가지, 왼쪽 하나 오른쪽 하나씩 자식을 갖는 경우 1가지, 오른쪽 자식이 2개인 경우 2가지로 총 5가지라는 소리이다.

이 코드는 노드수를 입력 받았을 때 그릴 수 있는 트리의 개수를 구하는 함수이다. 가장 아랫부분 함수를 보면 열~~~~~~~~~~~~~~라 어설프지만 나름(?) 비주얼 화도 시도했었다. 하지만... 이거 뭐... 말이 비주얼이지 그냥 공식을 조금이나 설명에 덧붙인 정도이다. 결론은 뻘짓이라는 소리다. 캬캬캬~ 워낙 간단한 코드다보니 별로 참고는 안되겠지만 조금이나마(?) 블로그를 윤택하기 위해 올려본다. 과연 이것으로 윤택해질지는 의문에 의문이지만... ( -_-)