[자료구조] 이진트리(Binary Tree) - 2

 

이진 트리의 경우도 배열과 리스트 2가지 방법으로 구현이 가능하다.

 

트리가 완성된 이후에는 매우 자주 탐색이 이루어 진다. 그래서 배열로 구성 해볼 만 하다.

배열을 기반으로 이진 트리를 구현하려면 노드에 고유의 노드 번호를 부여해야 한다.

이 번호들은 데이터가 저장되어야 할 배열의 인덱스 값이다.

 

인덱스가 0인 배열의 요소를 사용하지 않는 이유는

개인 차가 있겠지만 구현의 편의와 실수를 줄이기 위해서 일반적으로 사용하지 않는다.

 

다음은 연결리스트 기반의 구현방법이다.

그림만 봐도 단번에 이해가 될 만큼 쉽게 표현 가능하다.

그림에 나온대로 구성하면 되므로 별 다른 설명은 필요 하지 않을 것 같다..

 

 

만약에.. 연결리스트로 이진 트리를 구현 했다고 했을시.

"삭제는 어떻게 하겠는가?"

 

둘 이상의 노드로 이루어져 있는 서브트리를 완전히 삭제하려면 서브트리를 구성하는 모든 노드를 돌아야 된다.

이렇게 모든 노드를 거치는 것을 순회라 하는데 이 이진 트리의 순회는 별도의 방법이 필요하다.

이진 트리의 대표적인 순회는 세가지 방법이 있다.

전위 순회(Preorder Traversal)	루트 노드를 먼저돈다
중위 순회(Inorder Traversal)	루트 노드를 중간에 돈다
후위 순회(Postorder Traversal)	루트 노드를 마지막에 돈다.

 

"루트 노드를 언제 방문하느냐" 로 이렇게 나뉘어 진다.

루트 노드를 중간에 방문하기 때문에 이 방식의 순회는 중위 순회이다.

 

루트 노드를 제일 먼저 방문하는 방식이므로 전위 순회이다.

 

루트노드를 마지막에 방문하게 되므로 이러한 방식의 순회를 가리켜 후위 순회라 한다.

 

이것들을 이용해 이진 트리를 구성해 보았다.

 

BinaryTreeNode.h

#pragma once   #include "NodeManager.h"   class CNode { public:           CNode();         virtual ~CNode();           void m_SetData( );          private:       friend class CNodeManager;       int m_nData;       CNode *m_Left;     CNode *m_Right;   };

BinaryTreeNode.cpp

#include <iostream>   #include "BinaryTreeNode.h"   CNode::CNode() {     std::cout<<"NODE 생성"<<std::endl;       this->m_Left = NULL;     this->m_Right = NULL;       this->m_SetData( ); }   CNode::~CNode() {     std::cout<<"NODE 소멸자"<<std::endl; }   void CNode::m_SetData( ) {     std::cout<<"저장할 정수를 입력해 주세요"<<std::endl;     std::cin>>this->m_nData; }

NodeManager.h

#pragma once   #include "BinaryTreeNode.h"   enum eMenu {     eAdd = 1,     eDel,     ePrint,     eExit, };   enum eLine {     eLeft = 1,     eRight, };   enum ePrint {     ePreorder = 1,        //전위 순회     eInorder,            //중위 순회     ePostorder,            //후위 순회 };   static const int nNONE = 0;   class CNodeManager { public:       CNodeManager();     ~CNodeManager();       friend class CNode;           void m_Start( );         void m_MakeNode( CNode *Node = NULL , int nAddLine = nNONE );           void m_DelNode( CNode **Node , int nAddLine = nNONE );         void m_Print( CNode *RouteNode );           void m_PreorderTraversal( CNode *RouteNode );                //전위 순회         void m_InorderTraversal( CNode *RouteNode );                //중위 순회         void m_PostorderTraversal( CNode *RouteNode );            //후위 순회   private:       CNode *BinaryTree; };

NodeManager.cpp

#include <iostream>   #include "NodeManager.h"   CNodeManager::CNodeManager( ) {     std::cout<<"CNodeManager 생성자"<<std::endl;     BinaryTree = NULL; }   CNodeManager::~CNodeManager( ) {     std::cout<<"CNodeManager 소멸자"<<std::endl; }   void CNodeManager::m_Start( ) {     int nChoiceMenu = 0;     while(true)     {         std::cout<<"1. 삽입 , 2. 삭제 3. 출력 4. 종료"<<std::endl;         std::cin>>nChoiceMenu;         switch (nChoiceMenu)         {         case eAdd:             this->m_MakeNode( BinaryTree );             break;         case eDel:             this->m_DelNode(&BinaryTree );             break;           case ePrint:             this->m_Print( BinaryTree );             break;           case eExit:             this->m_DelNode(&BinaryTree );             return;             break;         default:             std::cout<<"잘못 선택하였습니다."<<std::endl;             break;         }     }   }   void CNodeManager::m_MakeNode( CNode *Node , int nAddLine ) {     if( NULL == BinaryTree )     {         BinaryTree = new CNode;     }     else     {         std::cout<<"1. 왼쪽 , 2. 오른쪽"<<std::endl;         std::cin>>nAddLine;           switch (nAddLine)         {         case eLeft:             if( NULL == Node->m_Left )             {                 Node->m_Left = new CNode;             }             else             {                 std::cout<<"해당 노드에 데이터가 있어서 왼쪽으로 이동"<<std::endl;                 m_MakeNode( Node->m_Left , nAddLine);             }             break;           case eRight:             if( NULL == Node->m_Right )             {                 Node->m_Right =new CNode;             }             else             {                 std::cout<<"해당 노드에 데이터가 있어서 오른쪽으로 이동"<<std::endl;                 m_MakeNode( Node->m_Right , nAddLine);             }             break;           default:             std::cout<<"잘못 선택하였습니다."<<std::endl;             break;         }       } } void CNodeManager::m_DelNode( CNode **Node , int nAddLine ) {     if( NULL == (*Node) )     {//노드가 아예 없을때         std::cout<<"노드가 비었습니다."<<std::endl;     }     else     {         m_DelNode( &(*Node)->m_Left );         m_DelNode( &(*Node)->m_Right );         std::cout<<"데이터 : "<<(*Node)->m_nData<<"삭제"<<std::endl;         delete (*Node);         (*Node) = NULL;     }   }   void CNodeManager::m_Print( CNode *RouteNode ) {     int nPrintMode = 0;     std::cout<<"순회 방법을 선택해 주세요"<<std::endl;     std::cout<<"1. 전위 순회, 2.중위 순회 3,후위 순회"<<std::endl;     std::cin>>nPrintMode;       switch (nPrintMode)     {     case ePreorder:         m_PreorderTraversal(RouteNode );         break;     case eInorder:     m_InorderTraversal(RouteNode );         break;     case ePostorder:         m_PostorderTraversal(RouteNode );         break;     default:         std::cout<<"잘못 선택하였습니다."<<std::endl;         break;     } }   void CNodeManager::m_PreorderTraversal( CNode *RouteNode )    //전위 순회 {     if( NULL == RouteNode )     {         return;     }     else     {    //루트노드를 먼저 방문하는 방식의 순회         std::cout<<"데이터 : "<<RouteNode->m_nData<<std::endl;         this->m_PreorderTraversal( RouteNode->m_Left );         this->m_PreorderTraversal( RouteNode->m_Right );     } }   void CNodeManager::m_InorderTraversal( CNode *RouteNode )    //중위순회 {     if( NULL == RouteNode )     {         return;     }     else     {    //루트노드를 중간에 방문하는 방식의 순회         this->m_InorderTraversal( RouteNode->m_Left );         std::cout<<"데이터 : "<<RouteNode->m_nData<<std::endl;         this->m_InorderTraversal( RouteNode->m_Right );     } }   void CNodeManager::m_PostorderTraversal( CNode *RouteNode )    //후위 순회 {     if( NULL == RouteNode )     {         return;     }     else     {    //루트노드를 마지막에 방문하는 방식의 순회         this->m_PostorderTraversal( RouteNode->m_Left );         this->m_PostorderTraversal( RouteNode->m_Right );         std::cout<<"데이터 : "<<RouteNode->m_nData<<std::endl;     } }

main.cpp

#include <iostream>   #include "NodeManager.h"   int main() {     CNodeManager NodeManager;       NodeManager.m_Start();       return 0; }

 

출력결과