자 & 알/자료구조
[자료구조] 재귀를 이용한 트리운행/스택을 이용한 트리운행
에드윈H
2021. 4. 1. 13:52
[자료구조]트리(Tree) 특징 / 운행 3가지 / C++
트리는 이름처럼 나무와 같은 자료구조이다. 뿌리를 가지고 뻗어져 나뭇가지에서 잎들이 있는 모습을 거꾸로 뒤집으면 자료구조에서의 트리가 된다. 게임에서의 트리 게임 개발을 할때의 트리
hyo-ue4study.tistory.com
#include<iostream>
#include<stack>
#include<algorithm>
using namespace std;
class Node {
public:
Node()
: mData(0)
, mLeft(nullptr)
, mRight(nullptr)
, mRoot(nullptr)
{}
Node(int data)
: mData(data)
, mLeft(nullptr)
, mRight(nullptr)
, mRoot(nullptr)
{}
void PrintData()
{
cout << mData << "/";
}
Node* mLeft;
Node* mRight;
Node* mRoot;
private:
int mData;
};
void PostOrder(Node* node)
{
if (node == nullptr)
{
return;
}
PostOrder(node->mLeft);
PostOrder(node->mRight);
node->PrintData();
}
void PostOrderStack(Node* node)
{
if (node == nullptr)
{
return;
}
cout << "스택 : ";
stack<Node*> st;
Node* tempNode = node;
Node* doneNode = nullptr;
while (1)
{
if (tempNode != nullptr && tempNode != doneNode)
{
st.push(tempNode);
do
{
if (tempNode->mRight != nullptr)
{
st.push(tempNode->mRight);
}
if (tempNode->mLeft != nullptr)
{
st.push(tempNode->mLeft);
}
tempNode = tempNode->mLeft;
} while (tempNode != nullptr);
}
if (!st.empty())
{
tempNode = st.top();
st.pop();
//예외 처리
if (tempNode->mLeft != NULL && tempNode->mRight == NULL && tempNode->mLeft != doneNode)
{
if (tempNode != nullptr)
st.push(tempNode);
tempNode = tempNode->mLeft;
}
if (tempNode->mRight == NULL || tempNode->mRight == doneNode)
{
//노드 데이터 출력
tempNode->PrintData();
//완료 노드로 지정
doneNode = tempNode;
}
}
else
break;
}
cout << endl;
}
//중위 운행
void InOrder(Node* node)
{
if (node == nullptr)
{
return;
}
InOrder(node->mLeft);
node->PrintData();
InOrder(node->mRight);
}
void InOrderStack(Node* node)
{
cout << "스택 : ";
if (node == nullptr)
{
return;
}
stack<Node*> st;
Node* temp = node;
while (1) {
while (temp != nullptr)//제일 좌측 노드로
{
st.push(temp);
temp = temp->mLeft;
}
if (!st.empty())
{
temp = st.top();
st.pop();
temp->PrintData();
temp = temp->mRight;
}
else
{
break;
}
}
cout << endl;
}
//전위 운행
void PreOrder(Node* node)
{
if (node == nullptr)
{
return;
}
node->PrintData();
PreOrder(node->mLeft);
PreOrder(node->mRight);
}
void PreOrderStack(Node* node)
{
if (node == nullptr)
{
return;
}
stack<Node*> st;
cout << "스택 : ";
st.push(node);
while (!st.empty())
{
Node* curNode = st.top();
curNode->PrintData();
st.pop();
if (curNode->mRight != nullptr)
st.push(curNode->mRight);
if (curNode->mLeft != nullptr)
st.push(curNode->mLeft);
}
cout << endl;
}
int main()
{
Node* root = new Node(0);
Node* node1 = new Node(1);
Node* node2 = new Node(2);
Node* node3 = new Node(3);
Node* node4 = new Node(4);
root->mLeft = node1;
root->mRight = node2;
node1->mLeft = node3;
node1->mRight = node4;
cout << "전위 운행 : " << endl;
cout << "재귀 : ";
PreOrder(root);
cout << endl;
PreOrderStack(root);
cout << "------------" << endl;
cout << "중위 운행 : " << endl;
cout << "재귀 : ";
InOrder(root);
cout << endl;
InOrderStack(root);
cout << "------------" << endl;
cout << "후위 운행 : " << endl;
cout << "재귀 : ";
PostOrder(root);
cout << endl;
PostOrderStack(root);
cout << "------------" << endl;
return 0;
}
입력 된 트리 구성
결과