# 이진 나무

아래와 같은 하나의 줄기에 두개의 가지만 있는 나무 모양의 프랙탈을 이진 나무(Binary Tree)라 한다. 쉽게 짐작할 수 있듯이 많은 자연의 성장 과정이 위와 유사한 구조로 되어 있다. 나무와 하천의 흐름이 가장 쉽게 찾아 볼 수 있는 예이다.

![](/files/-M3x20Hez7PS2-7q4UOH)

## 알고리즘

위의 차수가 3 인 이진 나무를 유심히 관찰하자. 구조가 완벽한 재귀적(순환적) 구조이다. 줄기에서 가지를 쳐 나가는 작업을 0 차 가지(잎)에 도달할 때까지 재귀적으로 반복하면 된다. 기본적인 알고리즘은 잡혔다. 이어서는 어떻게 가지를 쳐 나갈 것인가를 결정한다.

![](/files/-M3x20Hg3uYSn3YjepzS)

1. 길이가 length 인 `a` 가지를 그린다.
2. 왼쪽으로 30 도 회전하여 길이가 length\*0.8 인 `b` 가지를 그린다.
3. 오른쪽으로 60 도 회전하여 길이가 length\*0.8 인 `c` 가지를 그린다.
4. 3 번 과정을 마친 후 왼쪽으로 30 도 회전하여 진행 방향을 원래대로 환원시킨다.

예를 들어 차수 n = 3 인 경우 위와 같은 처리를 n 을 1 씩 줄여 나가면서 n = 0 이 될때까지 재귀적으로 반복시키면 위의 오른쪽의 나무가 그려진다. 이 때 주의할 점은 예를 들어 `b` 가지를 그린 후에는 선을 그리는 시작 위치를 `b` 가지의 시작점인 `CP` 로 환원시켜야 한다는 점이다. 그래야 위 알고리즘은 `c` 가지를 정확히 그린다. 이를 위해서 거북이 그래픽 클래스에 현재 거북이의 위치를 저장하는 스택을 포함하였다. 아래 부분은 거북이 클래스에 새로 추가된 함수의 코드이다.

```cpp
// Header File

typedef stack<Point3D> pstack;

class Turtle
{
private:
    ...
    pstack PointStack; //위치를 저장할 스택
    ...
public:
    ... 
    void MarkCurrentPoint(void); //현재의 위치에 점을 그린다.
    void Push(void); //현재의 위치를 저장한다.
    void Pop(void); //저장한 위치로 돌아간다.
};
```

```cpp
// Source File

Turtle::Turtle(void)
{
    //스택 포인터 모두 제거
    while(PointStack.size())
    {
        PointStack.pop();
    }
    ...
}

void Turtle::SetStartPoint(float x, float y, float z)
{
    //스택 포인터 모두 제거
    while(PointStack.size())
    {
        PointStack.pop();
    }
    ... 
} 

void Turtle::MarkCurrentPoint(void)
{
    glPointSize(5.0f);
    glBegin(GL_POINTS);
        glColor3f(1.0f, 0.0f, 0.0f);
        glVertex3f(PointList[PointList.size()-1].x, PointList[PointList.size()-1].y, PointList[PointList.size()-1].z);
        glColor3f(1.0f, 1.0f, 1.0f);
    glEnd();
}

void Turtle::Push(void)
{
    int index = PointList.size()-1;
    Point3D pt(PointList[index].x, PointList[index].y, PointList[index].z);

    //포인트 리스트에 저장되어 있는 마지막 점을 push 한다.
    PointStack.push(pt);
}

void Turtle::Pop(void)
{
    if(PointStack.size())
    {
        Point3D pt(PointStack.top());
        PointStack.pop();
        PointList.push_back(pt);
    }
}
```

위의 알고리즘을 코드로 표현하면 아래와 같다.

```cpp
void RenderWindow::BinaryTree(int n, float length)
{
    turtle.Forward(length);
    if(n>0)
    {
        turtle.Push(); //CP 저장
        turtle.Left(30); BinaryTree(n-1, length*0.8);
        turtle.Pop(); //CP 로 이동
        turtle.Right(60); BinaryTree(n-1, length*0.8);
        turtle.Left(30);
    }
}
```

아래는 이진나무를 표현한 프로그램 결과와 전체 코드이다. 오른쪽 그림은 열매를 맺은 나무이다. n==0 일때 현재의 점을 표시하면 된다.

| ![](/files/-M3x20Hi74OXfUol5iY-) | ![](/files/-M3x20HkPDCW_g6Pq_Vp) |
| :------------------------------: | :------------------------------: |

```cpp
#include "lib\egl.h"
#include "turtle.h"

using namespace egl;

class RenderWindow : public Window
{
private:
    Turtle turtle;
public:
    void BinaryTree(int n, float length);
    virtual void RenderGLScene(void);
};

void RenderWindow::BinaryTree(int n, float length)
{
    turtle.Forward(length);

    //열매를 그린다.
    if(n==0)
    {
        turtle.MarkCurrentPoint();
    }

    if(n>0)
    {
        turtle.Push();
        turtle.Left(30); BinaryTree(n-1, length*0.8);
        turtle.Pop();
        turtle.Right(60); BinaryTree(n-1, length*0.8);
        turtle.Left(30);
    }
}

void RenderWindow::RenderGLScene(void)
{
    Window::RenderGLScene();

    glTranslatef(0.0f, 0.0f, -7.0f);

    turtle.SetStartPoint(0.0f, -2.0f, 0.0f);
    turtle.Left(90);

    BinaryTree(12, 1.0f);
}

int APIENTRY WinMain(HINSTANCE hInstance, HINSTANCE hPrevInstance, LPSTR lpCmdLine, int nShowCmd)
{
    RenderWindow app;
    if(!app.Create(FALSE, "Fractal - Binary Tree"))
        return EXIT_FAILURE;
    return app.Run();
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://sungcheol-kim.gitbook.io/fractal-graphics-with-opengl/chapter9.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.