[자료구조] 이진트리 구현

2023. 8. 8. 17:08

이진트리 클래스

class BinaryTree
{
public:
    BinaryTree();

private:

    BinaryTree* Left;
    BinaryTree* Right;

    char Ch;
public:
    char GetCh() const
    {
        return Ch;
    }
    BinaryTree* GetLeft() const
    {
        return Left;
    }
    BinaryTree* GetRight() const
    {
        return Right;
    }
    void SetCh(const char& Char)
    {
        Ch = Char;
    }
    void SetLeft(BinaryTree* InTree)
    {
        Left = InTree;
    }
    void SetRight(BinaryTree* InTree)
    {
        Right = InTree;
    }
};

이진트리 전위 순회

void PreOrder(BinaryTree* Tree)
{
    if (Tree == nullptr)
    {
        return;
    }

    std::cout << Tree->GetCh() << " ";
    PreOrder(Tree->GetLeft());
    PreOrder(Tree->GetRight());
}

현재 노드를 방문 -> 왼쪽 서브 트리 방문 -> 오른쪽 서브 트리 방문

이진트리 중위 순회

void InerOrder(BinaryTree* Tree)
{
    if (Tree == nullptr)
    {
        return;
    }

    InerOrder(Tree->GetLeft());
    std::cout << Tree->GetCh() << " ";
    InerOrder(Tree->GetRight());
}

왼쪽 서브 트리 방문 -> 현재 노드를 방문 -> 오른쪽 서브 트리 방문

이진트리 후위 순회

void PostOrder(BinaryTree* Tree)
{
    if (Tree == nullptr)
    {
        return;
    }

    PostOrder(Tree->GetLeft());
    PostOrder(Tree->GetRight());
    std::cout << Tree->GetCh() << " ";
}

왼쪽 서브 트리 방문 -> 오른쪽 서브 트리 방문 -> 현재 노드 방문

이진트리 메인 코드

int main()
{
    BinaryTree* TreeA = new BinaryTree();
    BinaryTree* TreeB = new BinaryTree();
    BinaryTree* TreeC = new BinaryTree();
    BinaryTree* TreeD = new BinaryTree();
    BinaryTree* TreeE = new BinaryTree();
    BinaryTree* TreeF = new BinaryTree();
    BinaryTree* TreeG = new BinaryTree();

    TreeA->SetCh('A');
    TreeB->SetCh('B');
    TreeC->SetCh('C');
    TreeD->SetCh('D');
    TreeE->SetCh('E');
    TreeF->SetCh('F');
    TreeG->SetCh('G');

    TreeA->SetLeft(TreeB);
    TreeA->SetRight(TreeE);
    TreeB->SetLeft(TreeC);
    TreeB->SetRight(TreeD);
    TreeE->SetLeft(TreeF);
    TreeE->SetRight(TreeG);

    PreOrder(TreeA);
    InerOrder(TreeA);
    PostOrder(TreeA);
}

A~G 까지 노드를 생성 후 노드를 각각 연결 시켜 준다.

그럼 위의 그림과 같이 노드 트리가 완성 될 것 이다.

위의 그림을 토대로 전위, 중위, 후위순회를 실행한 결과이다.

gksdydrkfl