이진 트리의 구현과 순회

＃순회의 종류 3개

순회의 기준은 트리노드를 언제 방문하느냐에 있다.

즉 루트 노드를 방문하는 시점에 따라 서 중위, 후위, 전위 순회로 나뉘어 진다.

1단계 왼쪽 서브트리의 순회

2단계 루트노드의 방문

3단계 오른쪽 서브트리의 순회

- 전위 순회(Preorder Traversal)

- 중위 순회(Inorder Traversal)

- 후위 순회(Postorder Traversal)

＃이진트리 구현

h

cpp

#include"Tree.h"
 
TreeNode::TreeNode()
{
    m_data = 0;
    m_level = 0;
    mp_lift = NULL;
    mp_right = NULL;
}
 
TreeNode::~TreeNode()
{
    if (mp_lift != NULL) delete mp_lift;
    if (mp_right != NULL) delete mp_right;
}
 
void TreeNode::MakeLiftSubTree(int _index)
{
    TreeNode* pNode = new TreeNode();
    pNode->m_level = this->m_level + 1;
    pNode->m_data = _index;
    this->mp_lift = pNode;
}
 
void TreeNode::MakeRightSubTree(int _index)
{
    TreeNode* pNode = new TreeNode();    
    pNode->m_level = this->m_level + 1;
    pNode->m_data = _index;
    this->mp_right = pNode;
}
 
void TreeNode::SetData(int _index)
{
    m_data = _index;
}
 
int TreeNode::GetData()
{
    return m_data;
}
 
TreeNode* TreeNode::GetLiftSubTree()
{
    return mp_lift;
}
 
TreeNode* TreeNode::GetRightSubTree()
{
    return mp_right;
}
 
void TreeNode::PreorderTraverse()
{
    if (this == NULL) return;
    cout << m_data << endl;
    this->mp_lift->InorderTraverse();
    this->mp_right->InorderTraverse();
}
 
void TreeNode::InorderTraverse()
{
    if (this == NULL) return;
    this->mp_lift->InorderTraverse();
    cout << m_data << endl;
    this->mp_right->InorderTraverse();
}
 
void TreeNode::PostorderTraverse()
{
    if (this == NULL) return;
    this->mp_lift->InorderTraverse();
    this->mp_right->InorderTraverse();
    cout << m_data << endl;
}

사용해보기

level 그림

1번 트리의 순회 결과

전위 순회 결과

중위 순회 결과

후위 순회 결과

2번 트리의 순회 결과

전위 순회 결과

중위 순회 결과

후위 순회 결과