Inorder 이진트리

소개

완벽한 소스 프로그램입니다.

목차

■ 문제개요

■ 문제분석 및 해결방법

■ 소스코드 및 주석

■ 실행화면

■ 느낀점

본문내용

■ 문제개요
Inorder Tree를 이용하여 사칙연산을 할 수 있는 프로그램을 작성하라. 수식을 입력받을때에는 변수를 쓰지 말고 한꺼번에 모든 수를 입력 받으며, 수식에 괄호는 쓰지 않는다.


■ 문제분석 및 해결방법
트리에서 수행하려고 하는 연산에는 여러 가지가 있는데 그 중에 하나는 트리순회이다. 다시말해 트리에 있는 모든 노드를 한번씩만 방문하는 것이다. 한 노드가 방문될 때 어떤연산이 그 노드에 대해 순회된다. 완전한 순외는 트리에 있는 노드의 선형 순서를 생성한다. 각 노드를 방문하는 순서에 따라 생성된 이 선형 순서는 친숙하고 용이하다. 이진트리를 순회할때는 각 노드와 그 서브트리를 똑같은 방법으로 취급하는 것이 바람직하다. 만일 L, V, R이 한노드에서 각각 왼쪽으로 이동, 노드방문, 오른쪽으로 이동하는 것을 나타내면 LVR, LRV, VLR, VRL, RVL, RLV로 나타낼수 있다. L과 R에 대한 V의 상대적인 위치에 따라 이 세가지를 각각 전위순회, 중위순회, 후위순회라고 한다.
중위순회는 먼저 더 이상 진행할수 없을 때까지 왼쪽 방향으로 이동하여 내려간다. 그리고 그 노드를 방문하고 오른쪽 자식노드로 이동한뒤 계속한다. 오른쪽으로 이동할수 없을깨는 한노드 뒤고 돌아간다. 이렇게 각 노드를 돌고난뒤 그 결과값을 스택에 저장한다. 스택에는 인식한 상수와 연산자를 저장하며, 이렇게 저정한 값들은 나중에 후위식으로 추력되어 결과값이 출력된다.



■ 소스코드 및 주석
⓵ main.cpp
#include <iostream>
#include "tree.h"
using namespace std;

int main()
{
Stack song;
char InFix[30];
char post[30];
node *tree = new node;

참고자료

· 없음